Maximum Difference in an Array

Difficulty: Medium; Asked-in: Facebook, Microsoft, Amazon, Hike, SAP Labs.

Key takeaway: This is an excellent coding problem to learn problem-solving using divide and conquer, transform and conquer, and a single loop.

Let’s understand the problem

Given an array A[] of integers, write a program to find the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i.

Example 1

Input: A[] = [1, 4, 9, 5, 3, 7], Output: 8.

Explanation: The maximum difference is between 9 and 1.

Example 2

Input: A[] = [9, 8, 1, 6, 3, 2], Output: 5.

Explanation: The maximum difference is between 6 and 1.

Example 3

Input: A[] = [9, 8, 6, 3, 2], Output: -1.

Explanation: The input elements are in decreasing order, meaning no larger element appears after the smaller element.

Discussed solution approaches

Brute force approach using nested loops
Using divide and conquer approach similar to merge sort
Using transform and conquer approach: Transforming problem into max subarray sum problem using extra space
Efficient in-place approach using single loop

Brute force approach using nested loops

Solution idea

The basic idea is to explore each pair (A[j], A[i]) and find the maximum difference for all A[j] > A[i] and j > i. How do we implement this? Let's think!

We can use two nested loops where we pick each element from i = 0 to n - 2 using the outer loop and find the difference with every element from j = i + 1 to n - 1 using the inner loop. We also keep track of the maximum difference where the larger element appears after the smaller element.

Solution steps

We initialise a variable maxDiff to track the maximum difference.
Now we run the outer loop from i = 0 to n - 2.
For every element A[i], we run an inner loop from i + 1 to n - 1. Whenever we find A[j] > A[i], we update maxDiff with max(A[j] - A[i], maxDiff).
By the end of the nested loops, we return maxDiff.

Solution pseudocode

maxDifferenceArray(A, n)
    maxDiff = -1
    // Consider every pair where j is after i
    for i from 0 to n - 2
        for j from i + 1 to n - 1
            if A[j] > A[i]
                maxDiff = max(maxDiff, A[j] - A[i])

    return maxDiff

Time and space complexity analysis

We are running nested loops and exploring each unique pair (A[j], A[i]). So the total number of loop iterations is equal to the total count of unique pairs, which is nC2 = n(n - 1)/2. At each iteration, we perform an O(1) operation. So the time complexity is n(n - 1)/2 * O(1) = O(n^2).

We are using a constant number of extra variables, so the space complexity is O(1).

Divide and conquer approach similar to merge sort

Solution idea

Suppose we divide the array into two equal parts and recursively calculate the maximum difference between the left and right parts. Then the maximum difference of the overall array will be the maximum of these three possibilities:

The maximum difference of the left part (Subproblem 1).
The maximum difference of the right part (Subproblem 2).
Maximum difference crossing the left and right parts. This situation occurs when the smallest value is from the left part and the largest value is from the right part.

So the overall max difference = max (max difference of the left part, max difference of the right part, max difference crossing the left and right parts). This idea looks similar to merge sort or the divide and conquer solution of the maximum subarray sum.

Solution steps

Divide part: Divide the array into two equal halves, mid = l + (r - l)/2.

Conquer part: Recursively solves smaller sub-problems.

leftMaxDiff = maxDifferenceArray(A[], l, mid)
rightMaxDiff = maxDifferenceArray(A[], mid + 1, r)

Combine part: Calculate the max difference crossing the left and right parts.

Find the minimum from the left part, i.e., minLeft = findMin(A[], l, mid).
Find the maximum from the right part, i.e., maxRight = findMax(A[], mid + 1, r).
So, the max difference crossing the left and right parts = maxRight - minLeft.

So, the overall max difference will be the maximum of leftMaxDiff, rightMaxDiff, and maxRight - minLeft, i.e., maxDiff = max(leftMaxDiff, rightMaxDiff, maxRight - minLeft).

Base case: l ≥ r would be the base case, which is the scenario of a single element. We return -1 in this situation because we need at least two array elements to calculate the max difference.

Solution pseudocode

findMin(A, low, high)
    minValue = A[low]
    for i from low + 1 to high
        if A[i] < minValue
            minValue = A[i]

    return minValue


findMax(A, low, high)
    maxValue = A[low]
    for i from low + 1 to high
        if A[i] > maxValue
            maxValue = A[i]

    return maxValue

maxDifferenceArray(A, l, r)
    if l >= r
        return -1
    mid = l + (r - l) / 2
    // Find the best difference entirely within each half
    leftMaxDiff = maxDifferenceArray(A, l, mid)
    rightMaxDiff = maxDifferenceArray(A, mid + 1, r)
    // Find the best difference that starts in the left half
    // and ends in the right half
    minLeft = findMin(A, l, mid)
    maxRight = findMax(A, mid + 1, r)
    crossDiff = maxRight - minLeft
    return max(leftMaxDiff, rightMaxDiff, crossDiff)

Time and space complexity analysis

For the analysis of the recursive solution, we need to write down a recurrence relation to calculate the time complexity. Suppose T(n) is the time complexity of finding the max difference for an input size of n. T(n) = Time complexity of divide part + Time complexity of conquer part + Time complexity of combine part.

The time complexity of the divide part = O(1).
The time complexity of the conquer part = 2T(n/2), because we are recursively solving two sub-problems, each of size n/2.
The time complexity of the combine part = Time complexity of finding the minimum in the left part + Time complexity of finding the maximum in the right part + Time complexity of calculating the max difference = O(n) + O(n) + O(1) = O(n).

After adding all three time complexities, we get the recurrence relation for the overall time complexity.

T(n) = O(1) + 2T(n/2) + O(n) = 2T(n/2) + cn. In more general words:

T(n) = c, if n = 1.
T(n) = 2T(n/2) + cn, if n > 1.

This recurrence looks similar to the merge-sort recurrence, so we can solve it using the recursion tree method or the master theorem. The time complexity = O(nlogn). Note: To better understand this analysis, explore the analysis of recursion blog.

For the space complexity of the recursive program, we need to calculate the size of the recursion call stack. The size of the recursion call stack = The height of the recursion tree = O(logn). So space complexity = O(logn) (Think!).

Using transform and conquer approach: Transforming problem into max subarray sum problem

Solution idea

The main idea behind this algorithm is to go through the differences between adjacent elements and store all the differences in an auxiliary array of size n-1. After this, the problem gets transformed into finding the maximum sum subarray of this difference array. How? Let's see.

Suppose we have A[j] - A[i], for some indices j and i. We can write A[j] - A[i] in terms of the sum of the difference between adjacent elements. Here are the steps:

=> A[j] - A[i] = (A[j] - A[j-1]) + (A[j-1] - A[j-2]) + ...... + (A[i+1] - A[i])

So, max (A[j] - A[i]) = max [(A[j] - A[j-1]) + (A[j-1] - A[j-2]) + ..... + (A[i+1] - A[i])]

=> max (A[j] - A[i]) = max [diff(j, j-1) + diff(j-1, j-2) + ..... + diff(i+1, i)]

In other words, max (A[j] - A[i]) = Max subarray sum of differences from index i to j.

So, if we store the differences of adjacent elements in an extra array diff[], we can easily calculate max (A[j] - A[i]) by finding the max subarray sum of the diff[] array. Note: The size of the difference array would be n-1.

Solution steps

We declare an extra memory diff[n - 1] of size n - 1 to store differences of adjacent elements.
We run a loop from 0 to n - 2 and store differences of adjacent elements in diff[n - 1].
Now, we can calculate the maximum subarray sum of the diff[] array in O(n) time and O(1) space and return the result.

Note: In this problem, we need to find max(A[j] - A[i]) when A[j] > A[i]. So the value of the max difference is either positive or -1. To handle this situation, we check the maximum subarray sum of the diff[] array. If the max subarray sum is +ve, then we return that value. Otherwise, we return -1. Think!

Solution pseudocode

maxSubarraySum(diff, n)
    maxSumSoFar = diff[0]
    maxSumEndingHere = diff[0]

    for i from 1 to n - 1
        maxSumEndingHere = max(maxSumEndingHere + diff[i], diff[i])
        if maxSumSoFar < maxSumEndingHere
            maxSumSoFar = maxSumEndingHere

    return maxSumSoFar


maxDifferenceArray(A, n)
    diff = array of size n - 1
    // Store the difference between each pair of adjacent elements
    for i from 0 to n - 2
        diff[i] = A[i + 1] - A[i]

    maxDiff = maxSubarraySum(diff, n - 1)
    if maxDiff > 0
        return maxDiff
    else
        return -1

Time and space complexity analysis

Time complexity = Time complexity of storing values in the diff[] array + Time complexity of finding max subarray sum of the diff[] array = O(n) + O(n) = O(n). Space complexity = O(n), for storing the differences in the diff[] array of size n - 1.

An efficient in-place approach using a single loop

Solution idea

Instead of comparing every pair of elements, we can compare each element with the smallest element that appeared before it. This idea will work because max difference between A[j] and some previous value A[i] will be maximum when A[i] is the minimum value from 0 to j -1.

We track two values as we scan from left to right:

minElement: the smallest value seen so far.
maxDiff: the largest valid difference found so far.

For each element, we first calculate its difference from minElement and update maxDiff if this difference is larger. Then update minElement if the current element is smaller.

After scanning the array, we return maxDiff. If no positive difference exists, it remains -1.

Solution pseudocode

maxDifferenceArray(A, n)
    minElement = A[0]
    maxDiff = -1
    // Scan the array, keeping the smallest value seen so far
    for i from 1 to n - 1
        difference = A[i] - minElement

        if difference > maxDiff
            maxDiff = difference

        if A[i] < minElement
            minElement = A[i]

    return maxDiff

Time and space complexity analysis

We are running a single loop n - 1 time and doing O(1) operations at each iteration. So the time complexity is (n - 1) * O(1) = O(n). The space complexity is O(1), as we are using a constant number of extra variables.

Critical ideas to think about!

In the divide and conquer approach, why are we considering the three different cases? And why is the space complexity O(log n)?
What would be the best and worst-case scenario for all of the above approaches?
In the transform and conquer approach, why are we calculating the maximum subarray sum of the diff[] array? Can we modify this approach to solve the problem using constant extra space?
How do the above solutions work in the case of repeating elements? Do we need to modify the code?
Can we solve this problem using a different approach?

Comparisons of time and space complexities

Using two nested loops: Time = O(n^2), Space = O(1)
Using divide and conquer: Time = O(nlogn), Space = O(logn)
Using transform and conquer: Time = O(n), Space = O(n)
Using a single scan: Time = O(n), Space = O(1)

Maximum Difference Between Two Elements in an Array

Let’s understand the problem

Example 1

Example 2

Example 3

Discussed solution approaches

Brute force approach using nested loops

Solution idea

Solution steps

Solution pseudocode

Time and space complexity analysis

Divide and conquer approach similar to merge sort

Solution idea

Solution steps

Solution pseudocode

Time and space complexity analysis

Using transform and conquer approach: Transforming problem into max subarray sum problem

Solution idea

Solution steps

Solution pseudocode

Time and space complexity analysis

An efficient in-place approach using a single loop

Solution idea

Solution pseudocode

Time and space complexity analysis

Critical ideas to think about!

Comparisons of time and space complexities

Suggested coding problems to explore

More from EnjoyAlgorithms

Self-paced Courses and Blogs