Coding Algorithms — Monotonic Stacks and Queues
In this post we are going to look one of the interesting modifications to stacks and queues. In monotonic stacks and queues, at any point in time, the elements in the stack/queue are in either increasing or decreasing order.
Lets look at few problems to understand the pattern of problems that can be solved with Monotonic stacks/queues.
Note that most of these problems can also be solved with dynamic programming or other techniques, but it is in fact much easier to solve using monotonic stacks/queues once you understand the technique.
Few patterns are:
- Finding the previous/next smaller/greater number.
- Sliding window minimum/maximum
Problem 1:
Given an array “nums”, return an array “arr”, such that arr[i] is the index of the next greater element of nums[i] i.e. smallest index j > i s.t. nums[j] > nums[i]. If there are no greater element then set arr[i] =-1.
Example:
nums=[5,1,4,2,3,6,7,5,8]
arr =[5,2,5,4,5,6,8,8,-1]Solution:
One solution is to use a AVL Tree to insert the elements from the end. For index i, search the next greater element in the AVL Tree, update arr[i] and then add nums[i] to the tree.
Time complexity is O(N*logN).
But we can solve it in O(N) time by noting that if we maintain a stack with monotonically decreasing numbers from the end.
Thus if we insert numbers from the end of the array into the stack, then for index i, pop all elements from the stack until the element at the top of the stack (at index j) is greater than nums[i] or it is empty.
We can prove that this strategy works by proving that no element between indices i and j can be the next greater element for any index < i. Because if that is so, then the algorithm will give incorrect result as we have removed that index from the stack.
Assuming that there is an index k s.t. i < k < j and an index p s.t. p < i and nums[k] ≤ nums[i] and nums[k] > nums[p], then the next greater element of nums[p] is nums[i] because nums[p] < nums[k] ≤ nums[i] and p < i < k.
Thus it is never possible that the next greater element for any index is not present in the stack unless the element at index i is the maximum seen so far.
Time and space complexity is O(N).
Problem 2:
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7Solution:
One solution is to use Max Heap.
Insert the first K elements into Max Heap, then the first output is the root of the Max Heap. Along with the value of the element also add the index in the heap.
At index i, while the index of the element at root of the heap is ≤ i-k, remove and ignore those elements as these are outside the sliding window. Else if the index of root is > i-k, then the sliding window max at index i is the value of the max heap root.
Time complexity here is O(N*logN).
We can solve this problem in O(N) using a monotonic double ended queue.
Add and remove elements from the double ended queue in such a way that the elements are in decreasing order from the start and the solution for the current window is the element at index 0 in the queue.
We need double ended queue because with a stack, while inserting the element at index i, we first remove all elements smaller than nums[i] from the top of stack. But the bottom of the stack might contain elements outside the sliding window size k. Thus we also need to prune the bottom of the stack so that the first element is within the current sliding window range.
Hence this looks more like a double ended queue.
Time and space complexity is O(N).
Problem 3:
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.Solution:
The bar at index i, forms a rectangle with all consecutive bars to the left and right with height ≥ heights[i], i.e. find the smallest index j, j < i s.t. heights[j] < heights[i] and smallest index k, k > i s.t. heights[k] < heights[i].
i.e. our range of interest is (j+1) to (k-1).
Then the width of the maximal rectangle at index i is (k-j-1) and maximal area is (k-j-1)*heights[i].
Time and space complexity is O(N).
Problem 4:
Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1.
A subarray is a contiguous part of an array.
Example:
Input: nums = [2,-1,2], k = 3
Output: 3Solution:
If all the numbers were +ve, it would be simply using a monotonic double ended queue. Insert the prefix sums into the queue which is in increasing order.
If the difference between q[end]-q[start] ≥ K, then the sum of numbers from start+1 to end in nums is ≥ K. Remove numbers from the start of the queue until q[end]-q[start] < K.
With the addition of negative numbers, we need to make a slight change.
When nums[i] < 0 i.e. prefix_sum[i] < prefix_sum[i-1], in order to maintain an increasing order in the queue, remove all numbers from the end of queue where q[end] ≥ prefix_sum[i] i.e. we club negative number with positives so that we get a positive number eventually.
Time and space complexity is O(N).
Problem 5:
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.
Example:
Input: arr = [3,1,2,4]
Output: 17
Explanation:
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.Solution:
For each index i, find the index j < i for the previous smaller number and index k > i for the next smaller number. Then all subarrays in the range [j+1, k-1] covering index i, have nums[i] as the minimum value.
For e.g. if the array is [2, 1, 4, 5, 3, 7, 9, 8, 2, 6]
Then for index 4 i.e. value is 3, j = 1 and k=8, all sub-arrays having index 4 as the minimum value are:
[3], [3,7], [3,7,9], [3,7,9,8]
[5,3], [5,3,7], [5,3,7,9], [5,3,7,9,8]
[4,5,3], [4,5,3,7], [4,5,3,7,9], [4,5,3,7,9,8]
Time and space complexity O(N).
Problem 6:
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.Solution:
Note that this problem can be solved similar to largest rectangle in histogram (Problem 3 above).
The idea is to consider each row at a time as the base of the histogram.
The height of a rectangle at i-th row and j-th index is the maximum number of consecutive 1’s going upwards along the column j from cell (i, j). This can be computed using dynamic programming where dp[i][j] = dp[i-1][j]+1 if matrix[i][j]=1.
Then at each row, we run the largest rectangle algorithm to find the largest rectangle of all 1’s ending at that row.
Time and space complexity is O(N²).
Problem 7:
Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example:
Input: s = "bcabc"
Output: "abc"Solution:
This can be solved using a monotonic stack. Maintain the last index for each character in an array.
Let the character at the top of the stack be T.
For a character at index i, if its not already included in the stack and T > s[i] and the last position of T is greater than index i i.e. T also occurs later in the string, then remove T from stack.
Time and space complexity is O(N).
Problem 8:
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < kand nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
Example:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].Solution:
For each index i, pre-compute the index of the minimum value upto index i-1 and the previous greater element using a monotonous stack (see above).
Then for an index k, find the index j which is previous greater element of index k and then find the index i=min_index[j].
Then if nums[i] < nums[k] < nums[j] we have got our triplet.
Note that nums[k] < nums[j] holds true due to the fact that nums[j] is the previous greater element of nums[k].
Time and space complexity is O(N).
Problem 9:
A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.
Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.
Example:
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.Solution:
For nums[0] if nums[-1] ≥ nums[0] then we have found the solution which is Len(nums)-1. But of nums[-1] < nums[0], then we have to check whether the previous greater element of the last element is ≥ nums[0] and so on.
Thus for nums[0] we start searching from the end and moving towards the previous greater element from the current element until we find an index j s.t. nums[j] ≥ nums[0]. The width is j.
For nums[1], note that if nums[1] ≥ nums[0] then the index k at which nums[k] ≥ nums[1] is ≤ j because if k > j then for nums[0] index k would have been the solution and not index j.
But if index k ≤ j is the solution then the width will decrease and there is no use is searching index k because width k-1 < j.
But if nums[1] < nums[0] then it is possible that index k ≥ j and width might increase.
Thus firstly we insert the increasing order of elements from the end of the array into stack using the previous greater element everytime to advance.
Then starting from i=0…Len(nums)-1, we continue to find the element at the end of the stack which is ≥ nums[i]. Also we only search in decreasing order from start else the width will decrease and there is no use.
Time and space complexity is O(N).
Problem 10:
There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.
A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).
Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.
Example:
Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.Solution:
This problem is relatively simple if you recognize that for an index i, it can see all elements from i+1 onwards with only increasing order of heights until the next greater (equal to) element.
i.e.
i+1, next_greater[i+1], next_greater[next_greater[i+1]], … and so on.
This can be efficiently computed by using a monotonous stack, since before inserting i into the stack, it contains all elements from i+1 in increasing order.
To maintain the increasing order after inserting i, pop all elements from stack where nums[stack[-1]] < nums[i].
Time and space complexity is O(N).
Problem 11:
Given an integer array arr, remove a subarray (can be empty) from arrsuch that the remaining elements in arr are non-decreasing.
Return the length of the shortest subarray to remove.
A subarray is a contiguous subsequence of the array.
Example:
Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].Solution:
Insert the elements from the end of array into a monotonous stack of decreasing order. But if we find an element arr[i] > arr[stack[-1]] then terminate the insertion flow.
Basically the stack contains the longest sorted order at the end of the array.
Starting from index i, check if arr[stack[-1]] ≥ arr[i], then move to i+1, else pop from stack until we have arr[stack[-1]] ≥ arr[i]. For i+1, if arr[i+1] < arr[i], then we break.
Time and space complexity is O(N).
Problem 12:
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example:
Input: nums = [1,2,3]
Output: 4
Explanation: The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.Solution:
For an index i, find the index j < i of previous smaller element and index k > i of next smaller element. Subarrays between j+1 to k-1 that have index i included has nums[i] as the minimum value, thus each such subarray contributes -nums[i] to the overall sum.
Similarly find the index p < i of previous greater element and index q> i of next greater element. Subarrays between p+1 to q-1 that have index i included has nums[i] as the maximum value, thus each such subarray contributes nums[i] to the overall sum.
Time and space complexity is O(N).
Problem 13:
You are given a string s, an integer k, a letter letter, and an integer repetition.
Return the lexicographically smallest subsequence of s of length k that has the letter letter appear at least repetition times. The test cases are generated so that the letter appears in s at least repetitiontimes.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
A string a is lexicographically smaller than a string b if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b.
Example:
Input: s = "leet", k = 3, letter = "e", repetition = 1
Output: "eet"
Explanation: There are four subsequences of length 3 that have the letter 'e' appear at least 1 time:
- "lee" (from "leet")
- "let" (from "leet")
- "let" (from "leet")
- "eet" (from "leet")
The lexicographically smallest subsequence among them is "eet".Solution:
Idea is to maintain a monotonous stack with increasing order of characters.
For an index i, pop from the stack if s[stack[-1]] > s[i] but we also have to take care of the length of the final string and the number of repetitions of “letter”.
Thus we only remove an element from stack if after removing we can still form a string of length k with the remaining characters from index i onwards and also the number of occurrences of letter in stack + number of occurrences of letter index i onwards is ≥ repetition.
Finally the stack would have ≥ k elements and letter occurring ≥ repetition times. The elements would be the smallest possible across all possible subsequence of length ≥ k.
In order to return only a subsequence of length k, we select maximum of k-repetition number of non-letter characters from the start of stack and fill the rest of the positions with letter.
Time and space complexity is O(N).
Problem 14:
You are given an array of integers nums (0-indexed) and an integer k.
The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.
Return the maximum possible score of a good subarray.
Example:
Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.Solution:
For an index i, find the index j < i of previous smaller element and index k > i of next smaller element. Subarrays between j+1 to k-1 that have index i included has nums[i] as the minimum value.
Thus nums[i] contributes a score of nums[i]*(k-j-1).
Time and space complexity of O(N)
