Maximum Difference Between Two Elements 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. 

Note: We exclude the last element in the outer loop because we need at least two elements for calculating the max difference.

Solution steps

• We initialize 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 code C++

int maxDifferenceArray(int A[], int n)
{
    int maxDiff = -1;
    for (int i = 0; i < n - 1; i = i + 1)
    {
        for (int j = i + 1; j < n; j = j + 1)
        {
            if (A[j] > A[i])
                maxDiff = max(maxDiff, A[j] - A[i]);
        }
   }
   return maxDiff;
}

Solution code Python

def maxDifferenceArray(A, n):
    maxDiff = -1
    for i in range(n - 1):
        for j in range(i + 1, n):
            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

Can we solve this problem using the divide and conquer approach or by solving smaller sub-problems? Let's think! 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 code C++

int findMin(int A[], int low, int high)
{
    int min = A[low];
    for(int i = low + 1; i <= high; i = i + 1)
    {
        if(A[i] < min)
            min = A[i];
    }
    return min;
}

int findMax(int A[], int low, int high)
{
    int max = A[low];
    for(int i = low + 1; i <= high; i = i + 1)
    {
        if(A[i] > max)
            max = A[i];
   }
   return max;
}

int maxDifferenceArray(int A[], int l, int r)
{
    if (l >= r)
        return -1;
    int maxDiff = -1;
    int mid = l + (r - l)/2;
    int leftMaxDiff = maxDifferenceArray(A, l, mid);
    int rightMaxDiff = maxDifferenceArray(A, mid + 1, r);
    int minLeft = findMin(A, l, mid);
    int maxRight = findMax(A, mid + 1, r);
    maxDiff = max(max(leftMaxDiff, rightMaxDiff), maxRight - minLeft);
    return maxDiff;
}

Solution code Python

def findMin(A, low, high):
    min = A[low]
    for i in range(low + 1, high + 1):
        if A[i] < min:
            min = A[i]
    return min

def findMax(A, low, high):
    max = A[low]
    for i in range(low + 1, high + 1):
        if A[i] > max:
            max = A[i]
    return max

def maxDifferenceArray(A, l, r):
    if l >= r:
        return -1
    maxDiff = -1
    mid = l + (r - l) // 2
    leftMaxDiff = maxDifferenceArray(A, l, mid)
    rightMaxDiff = maxDifferenceArray(A, mid + 1, r)
    minLeft = findMin(A, l, mid)
    maxRight = findMax(A, mid + 1, r)
    maxDiff = max(max(leftMaxDiff, rightMaxDiff), maxRight - minLeft)
    return maxDiff

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.

Therefore, 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 maximum 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].

for(int i = 0; i < n - 1; i = i + 1)
    diff[i] = A[i + 1] - A[i]

• 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 code C++

int maxSubarraySum(int diff[], int n)
{
    int maxSumSoFar = diff[0];
    int maxSumEndingHere = diff[0];
    for(int i = 1; i < n; i = i + 1)
    {
        maxSumEndingHere = max(maxSumEndingHere + diff[i], diff[i]);
        if(maxSumSoFar < maxSumEndingHere)
            maxSumSoFar = maxSumEndingHere;
    }
    return maxSumSoFar;
}

int maxDifferenceArray(int A[], int n)
{
    int diff[n - 1];
    for (int i = 0; i < n - 1; i = i + 1)
        diff[i] = A[i + 1] - A[i];
    if (maxSubarraySum(diff, n - 1) > 0)
        return maxSubarraySum(diff, n - 1);
    else     
        return -1;
}

Solution code Python

def maxSubarraySum(diff, n):
    maxSumSoFar = diff[0]
    maxSumEndingHere = diff[0]
    for i in range(1, n):
        maxSumEndingHere = max(maxSumEndingHere + diff[i], diff[i])
        if maxSumSoFar < maxSumEndingHere:
            maxSumSoFar = maxSumEndingHere
    return maxSumSoFar

def maxDifferenceArray(A, n):
    diff = [A[i + 1] - A[i] for i in range(n - 1)]
    if maxSubarraySum(diff, n - 1) > 0:
        return maxSubarraySum(diff, n - 1)
    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

In this method, instead of taking the difference between each element with every other element, we take the difference with the smallest element found so far. So we need to keep track of two things: 1) The maximum difference found so far and 2) The minimum element visited so far.

Solution steps

• We traverse the array from left to right and maintain two variables: minElement to store the smallest element found so far and maxDiff to store the maximum difference so far.
• At each step of the iteration, we keep updating minElement and maxDiff.
• By the end of the loop, we return the value of maxDiff.

Solution code C++

int maxDifferenceArray(int A[], int n)
{
    int minElement = A[0];
    int maxDiff = -1;
    for(int i = 1; i < n; i = i + 1)
    {
        if((A[i] - minElement) > maxDiff)
            maxDiff = A[i] - minElement;
        if(A[i] < minElement)
            minElement = A[i];
    }
    return maxDiff;
}

Solution code Python

def maxDifferenceArray(A, n):
    minElement = A[0]
    maxDiff = -1
    for i in range(1, n):
        if (A[i] - minElement) > maxDiff:
            maxDiff = A[i] - minElement
        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)

Suggested coding problems to explore

• Find product of array except self
• Find equilibrium Index of an array
• Rain water trapping problem
• Remove duplicate Elements from sorted array
• Maximum Subarray Sum
• Find Majority Element
• Maximum Sum Subarray of Size K
• Maximum Product Subarray
• Best Time to Buy and Sell Stock

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!