Maximum Difference in an Array

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

Key takeaway: An excellent coding problem to learn problem-solving using divide and conquer, transform and conquer and 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: Maximum difference is between 9 and 1.

Example 2

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

Explanation: Maximum difference is between 6 and 1.

Example 3

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

Explanation: Input elements are in decreasing order i.e. 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 outer loop and find difference with every element from j = i + 1 to n - 1 using inner loop. We also keep track of the maximum difference where the larger element appears after the smaller element. Note: We exclude last element in outer loop because we need at least two elements for calculating the max difference.

Solution steps

  • We initialize a variable maxDiff to track maximum difference.
  • Now we run 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 nested loops, we return maxDiff.

Solution pseudocode

int maxDifference(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
}

Time and space complexity analysis

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

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

Divide and conquer approach similar to merge sort

Solution idea

Can we solve this problem using divide and conquer approach or using the solution of smaller sub-problems? Let's think! Suppose we divided array into two equal parts and recursively calculated the max difference of left and right parts. Then the maximum difference of overall array will be the maximum of these three possibilities:

  • Maximum difference of the left part (Subproblem 1)
  • Maximum difference of the right part (Subproblem 2)
  • Maximum difference crossing the left and right part. This is a situation when smallest value is from the left part and largest value is from the right part (Think!)

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

Solution steps

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

Conquer part: Recursively solve smaller sub-problems.

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

Combine part: Calculate max diff crossing left and right parts.

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

So, 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 the single element. We return -1 in this situation because we need at least two array elements to calculate the max difference.

Solution pseudocode

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

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
}

Time and space complexity analysis

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

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

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

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

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

This recurrence looks similar to the merge sort recurrence, so we can solve it using recursion tree method or master theorem. Time complexity = O(nlogn)

For the space complexity of recursive program, we need to calculate the size of the recursion call stack. The size of recursion call stack = The height of 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 difference between adjacent elements and store all differences in an auxiliary array of size n - 1. After this, problem gets transformed into finding the maximum sum subarray of this difference array. How? Think!

Suppose for some j and i, we write A[j] - A[i] in terms of 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 diff[] array. Note: The size of difference array would be n - 1. Think!

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 calculate and return the maximum subarray sum of diff[] array. We can find this value in O(n) time and O(1) space. Refer to the finding max subarray sum blog.

Solution pseudocode

int maxDifference(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]
    int maxDiff = maxSubarraySum(diff, n - 1)
    return maxDiff
}

int maxSubarraySum(int diff[], int size)
{
    int maxSum_so_far = diff[0]
    int maxSum_endingHere = diff[0]
    for(i = 1; i < size; i = i + 1)
    {
        maxSum_endingHere = max(maxSum_endingHere + diff[i], diff[i])
        if(maxSum_so_far < maxSum_endingHere)
            maxSum_so_far = maxSum_endingHere
    }
    return maxSum_so_far
}

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 diff[] array of size n - 1.

Efficient in-place approach  using single loop

Solution idea

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

Solution steps

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

Solution pseudocode

int maxDifference(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
}

Time and space complexity analysis

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

Critical ideas to think!

  • In divide and conquer approach, why are we considering the three different cases? Why space complexity is O(logn)?
  • What would be the best and worst-case scenario of all the above approaches?
  • In the transform and conquer approach, why are we calculating the max subarray sum of the diff[] array? Can we modify this approach to solve problem using constant extra space?
  • How above solutions work in case of repeating elements? Do we need to modify the code?
  • Can we solve this problem using some 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 single scan: Time = O(n), space = O(1)

Suggested coding problems to explore

Enjoy learning, Enjoy algorithms!

Share feedback with us

More blogs to explore

Our weekly newsletter

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.