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.
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.
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.
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
}
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).
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:
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!)
Divide part: Divide array into two equal halves, mid = l + (r - l)/2
Conquer part: Recursively solve smaller sub-problems.
Combine part: Calculate max diff crossing left and right parts.
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.
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
}
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
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:
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!)
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!
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]
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 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.
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.
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
}
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.
Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.