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 a 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.
Input: A = [1, 4, 9, 5, 3, 7], Output: 8
Explanation: Maximum difference is between 9 and 1.
Input : A = [9, 8, 1, 6, 3, 2], Output : 5
Explanation: Maximum difference is between 6 and 1.
The basic idea is to explore each pair (A[j], A[i]) and find the maximum difference, where 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 an 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.
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 a constant number of extra variables, so space complexity = O(1).
Can we solve this problem using the divide and conquer approach or using the solution of the smaller sub-problems? Let's think!
Suppose we divided the array into two equal parts and calculated the max difference of the left and right parts recursively. Then the max diff of the overall array will be the maximum of these three possibilities :
So, the 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 the merge sort or divide conquer solution of the maximum sub-array sum. (Think!)
Divide part: Divide the array into two equal halves, mid = l + (r - l)/2
Conquer part: Recursively solve the smaller sub-problems.
Combine part: We calculate the max diff crossing the 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: low≥high would be the base case which is a scenario of the single element. The idea is simple: for calculating the max difference, we need at least two elements in the array.
Time and space complexity analysis
For a recursive solution, we need to write down the recurrence relation to calculate the time complexity. Suppose T(n) is the time complexity of finding the max difference for input size n.
So T(n) = Time complexity of the divide part + Time complexity of the conquer part + Time complexity of the 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 the recursion tree method or master theorem. Hence, Time complexity = O(nlogn)
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 = height of the recursion tree = O(logn). Space complexity: O(logn) (Think!)
The main idea behind this algorithm is to go through the difference between adjacent elements and store all differences in an auxiliary array of size n-1. Now, this problem gets transformed into finding the maximum sum subarray of this difference array. How? Think!
Suppose for some j and i, we can write A[j] - A[i] in terms of sum of the difference between adjacent elements from i to j. 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 the differences from index i to j)
So from the above observations, if we store the differences of the adjacent elements in an extra array diff, then we can easily calculate the 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. Think!
We run a loop from 0 to n-2 to store the differences in diff[n-1].
for(int i = 0; i < n - 1; i = i + 1) diff[i] = A[i + 1] - A[i]
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.
In this method, instead of taking the difference of 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:
Time and space complexity analysis
We are running a single loop n-1 times and doing O(1) operations at each iteration of the loop. So the time complexity = (n-1) * O(1) = O(n). Space complexity = O(1), as we are using a constant number of extra variables.
Enjoy learning, Enjoy algorithms!
Given the root of a BST and an integer k, write a program to find the kth largest value among all the nodes' values in the tree. This is an excellent problem to learn problem-solving using inorder traversal and data structure augmentation (storing extra information inside BST nodes for solving a problem).
Level order traversal accesses nodes in level by level order. This is also called breadth-first search traversal or BFS traversal. Here we start from the root node and process it, then process all the nodes at the first level, then process all the nodes at the second level, and so on. In other words, we explore all nodes at the current level before moving on to the nodes at the next level.
Given an array that includes both positive and negative numbers, write a program to find the first missing positive integer. This is one of the best searching problems for learning step-by-step optimization using various approaches. An in-place hashing solution uses the same input array to process values and generate correct output.
The least frequently used (LFU) is a cache algorithm used to manage memory within a computer. In this method, the system keeps track of the number of times a block is referenced in memory, and when the cache is full, our system removes the item with the lowest reference frequency.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.