Partner – Moderne – NPI EA (cat=Spring Boot)
announcement - icon

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Course – Black Friday 2026 – NPI EA – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – before_post_content
announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

1. Introduction

In this tutorial, we’ll explore different approaches to finding the maximum difference between any two elements in an array of integers in Java. We’ll demonstrate the problem using an example array with ten random integers ranging from -10 to 10. First, we’ll go over the problem and its challenges to understand common pitfalls. We’ll then explore different algorithms to solve this problem, starting from a naive approach and gradually moving toward more optimized solutions.

2. Problem Definition

Finding the maximum difference between two elements in an array has numerous practical applications. For instance, in Data Analysis we’ll need to identify the largest difference between data points, while in Stock Price Analysis we’d need to calculate the maximum profit between buy and sell prices. In Game Development, as well, we’ll need to compute the maximum distance between different points (e.g., player positions or scores).

Given an array of integers, our task is to identify the elements with the largest absolute difference, as well as their corresponding indices, and the values those indices point to. We’ll explore several methods for solving this problem, each with different time and space complexity.

3. Brute Force Approach

The brute-force approach is the simplest and most intuitive. We compare every possible pair of elements to calculate their difference. This method has a time complexity of O(n^2), making it inefficient for large arrays:

public static int[] findMaxDifferenceBruteForce(int[] list) {
    int maxDifference = Integer.MIN_VALUE;
    int minIndex = 0, maxIndex = 0;

    for (int i = 0; i < list.length - 1; i++) {
        for (int j = i + 1; j < list.length; j++) {
            int difference = Math.abs(list[j] - list[i]);
            if (difference > maxDifference) {
                maxDifference = difference;
                minIndex = i;
                maxIndex = j;
            }
        }
    }
    int[] result = new int[] { minIndex, maxIndex, list[minIndex], list[maxIndex], maxDifference };
    return result;
}

This approach checks every pair of elements, making it simple to implement but inefficient. Even though it displays a space complexity of O(1), for larger arrays, the O(n^2) time complexity makes it impractical. The method iterates over all pairs of elements to identify the maximum difference.

We’ll test our approach with an array, as follows:

@Test
public void givenAnArray_whenUsingBruteForce_thenReturnCorrectMaxDifferenceInformation() {
    int[] list = {3, -10, 7, 1, 5, -3, 10, -2, 6, 0};
    int[] result = MaxDifferenceBruteForce.findMaxDifferenceBruteForce(list);
    assertArrayEquals(new int[]{1, 6, -10, 10, 20}, result);
}

4. TreeSet (Balanced Tree) Approach

A more advanced approach is to use a TreeSet to maintain a dynamically sorted collection of elements. This allows us to quickly retrieve the minimum and maximum elements during traversal:

public static int[] findMaxDifferenceTreeSet(int[] list) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int num : list) {
        set.add(num);
    }

    int minValue = set.first();
    int maxValue = set.last();
    int minIndex = 0;
    int maxIndex = list.length - 1;

    for (int i = 0; i < list.length; i++) {
        if (list[i] == minValue) {
            minIndex = i;
        } else if (list[i] == maxValue) {
            maxIndex = i;
        }
    }

    int maxDifference = Math.abs(maxValue - minValue);
    int[] result = new int[] { minIndex, maxIndex, list[minIndex], list[maxIndex], maxDifference };
    return result;
}

Using a TreeSet allows for dynamic updates and efficient retrieval of the minimum and maximum values in O(n*log(n)) time. Nevertheless, this solution needs to store the entire array, thus offering a space complexity of O(n).

We run the same test case on our TreeSet implementation, as well:

@Test
public void givenAnArray_whenUsingTreeSet_thenReturnCorrectMaxDifferenceInformation() {
    int[] list = {3, -10, 7, 1, 5, -3, 10, -2, 6, 0};
    int[] result = MaxDifferenceTreeSet.findMaxDifferenceTreeSet(list);
    assertArrayEquals(new int[]{1, 6, -10, 10, 20}, result);
}

5. Optimized Single Pass Approach

To improve efficiency, we can traverse the array once while tracking the minimum and update the maximum difference if the current difference is greater. This reduces the time complexity to O(n) while still keeping the space complexity to O(1):

public static int[] findMaxDifferenceOptimized(int[] list) {
    int minElement = list[0];
    int maxElement = list[0];
    int minIndex = 0;
    int maxIndex = 0;

    for (int i = 1; i < list.length; i++) {
        if (list[i] < minElement) {
            minElement = list[i];
            minIndex = i;
        }
        if (list[i] > maxElement) {
            maxElement = list[i];
            maxIndex = i;
        }
    }

    int maxDifference = Math.abs(maxElement - minElement);
    int[] result = new int[] { minIndex, maxIndex, list[minIndex], list[maxIndex], maxDifference };
    return result;
}

This approach is much more efficient. It iterates over the array once, updating the minimum element and calculating the maximum difference dynamically. This method yields the same result as the brute-force approach but with a time complexity of O(n), making it suitable for large arrays.

We test the correctness of our implementation by running a test with the same inputs and expecting the same outputs, as for the brute force approach:

@Test
public void givenAnArray_whenUsingOptimizedOnePass_thenReturnCorrectMaxDifferenceInformation() {
    int[] list = {3, -10, 7, 1, 5, -3, 10, -2, 6, 0};
    int[] result = MaxDifferenceOptimized.findMaxDifferenceOptimized(list);
    assertArrayEquals(new int[]{1, 6, -10, 10, 20}, result);
}

6. Common Pitfalls

Here are some pitfalls that may arise in this problem:

  • Handling multiple pairs with the same maximum difference: Each of the presented approaches returns only a single pair of indices with the maximum difference, though there may be multiple valid pairs.
  • Input constraints: In cases where input values have known constraints, early termination could be achieved by stopping once we encounter the maximum possible difference.
  • Negative Values and Absolute Differences: Although we address this one, it’s worth mentioning that when both maximum and minimum elements are negative, the difference must be calculated in absolute terms to ensure correctness.

7. Conclusion

In this tutorial, we explored multiple approaches to finding the maximum difference between two elements in an array. We began with a brute-force solution, which was simple but inefficient, and progressed to more optimized methods.

The optimized single-pass approach is the most efficient for this problem, providing a time complexity of O(n) and minimal space usage. We also explored the TreeSet approach, which offers flexibility at the cost of performance in terms of both space and time complexity.

The code backing this article is available on GitHub. Once you're logged in as a Baeldung Pro Member, start learning and coding on the project.
Partner – Moderne – NPI EA (tag=Refactoring)
announcement - icon

Modern Java teams move fast — but codebases don’t always keep up. Frameworks change, dependencies drift, and tech debt builds until it starts to drag on delivery. OpenRewrite was built to fix that: an open-source refactoring engine that automates repetitive code changes while keeping developer intent intact.

The monthly training series, led by the creators and maintainers of OpenRewrite at Moderne, walks through real-world migrations and modernization patterns. Whether you’re new to recipes or ready to write your own, you’ll learn practical ways to refactor safely and at scale.

If you’ve ever wished refactoring felt as natural — and as fast — as writing code, this is a good place to start.

Course – Black Friday 2026 – NPI EA – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW

Course – Black Friday 2026 – NPI – main – after_post_content

announcement - icon

Yes, we're now running our Black Friday Sale. All Courses are 33% off until 1st December, 2026 at 17:00 Romania time:

>> EXPLORE ACCESS NOW