Monotonic queue:Keep things in order in a technical interview

Tags: , ,

What is a monotonic queue?
MQ is a data structure that keeps it’s elements either entirely in non-increasing, or entirely in non-decreasing order. One way to think of how can the monotonic queue technique be applied is to imagine how you can benefit from using increasing or decreasing sequence and what could you calculate having that sequence.

Monotonic queues are very useful in problems where we want to find the greater/min/max till a particular window. Let’s take an example and how a monotonic queue is used.

Find next greater number in an array

Given an array of integers, we have to find the next greater element on the right for each integer in the array. If there is no integer on the right which is greater then put -1 for it. For example, A = [ 30, 40, 20, 30, 50 ], result should be [ 40, 50, 30, 50, -1].

We can easily solve this problem in O(n2) complexity.

package AlgorithmsAndMe;

import java.util.Arrays;

public class NextGreaterElement {
    public int[] findNextGreater(int [] A){
        int [] res = new int[A.length];
        Arrays.fill(res, -1);

        for(int i=0; i<A.length; i++){
            for(int j=i+1; j<A.length; j++){
                //Go on till we find the greater element
                if(A[j] > A[i]){
                    res[i] = A[j];
                    break;
                }
            }
        }
        return res;
    }
}

In the inner loop, we stop as soon as we find the greater element for the index. It may happen that we are stopping at the same index again and again for all the indices. Can we save the processing of the inner loop?

We store all the indices for which greater integer is still not known. For each new index currIndex we process, check if there is an index ind in the list where A[ind] < A[currIndex], then the A[currIndex] is the next greater integer for ind. Take it from the list, mark the A[currIndex] as the greater element for it, and check for remaining on the list.
If there is no index on the list such that A[ind] < A[currIndex], we can push currIndex on to the list. It looks like O(n2) solution as well, but if you flush the smaller elements as soon as a greater element is seen, the queue is monotonically decreasing order. So, once you find an index ind such that A[ind] < A[currIndex], you can safely assume that all the indices before it are also greater than A[currIndex].

If the queue is monotonically decreasing and the comparison starts with the last index pushed on the queue and goes down, a stack is a very good data structure to use as a monotonic queue.

    public int[] findNextGreaterMono(int [] A){
        int [] res = new int[A.length];
        Arrays.fill(res, -1);

        Stack<Integer> s = new Stack<>();
        for(int i=0; i<A.length; i++){
            while(!s.isEmpty() && A[s.peek()] < A[i]){
                res[s.pop()] = A[i];
            }
            s.push(i);
        }
        return res;
    }

Can you solve the problem is you were asked to solve it for the next smaller number? What will be the order of the monotonic queue, increasing or decreasing?

Maximum rectangle in a histogram

Another commonly asked problem in interviews depending on monotonic queues is maximum rectangle in a histogram.

For a rectangle, we need a left boundary and a right boundary. How can we find these two boundaries, actually solves the problem.

A bar cannot be part of a rectangle which consists of a bar with a lower height than itself.

We go through each one of the bars and see if we should calculate the area of it now. If no, then we keep it in the queue to process later.
If the height of the current bar currBar is less than what is at the end of the queue lets barTail, these two bars cannot be in the same rectangle. We should calculate the area of the rectangle with the height of barTail, where right boundary is the currBar index.
Where is the left boundary then? If we keep our queue in increasing order (which in turn automatically done due to right boundary condition), we can be sure that that the bar in the queue last to one in the queue is left boundary.

Where is the monotonic queue here? Well, all the bars are stored in a queue in increasing order, if the new bar has a height lower than the last element of the queue, we remove the bar from the queue and calculate the area with the height of that bar. We go till we find a bar with a smaller height than the current bar and then store the current bar on to the queue. All we are doing here is maintaining a monotonically increasing queue. In an implementation, we can use a stack as well given that we access bars only in one direction.

private int maxAreaUsingStack(int[] heights){
 
        Stack<Integer> s = new Stack<>();
 
        int maxArea = 0;
        for(int i=0; i<=heights.length; i++){
            //Handling the last case
            int h = i == heights.length ? 0 : heights[i];
            /*If current height is less than peek, 
              calculate the area of rectangle with bar at the 
              top of the stack.
            */
            while(!s.empty() && h < heights[s.peek()]){
                int top = s.pop();
                //In case we reached at the end of the histogram.
                int leftLimit = s.isEmpty() ? -1 : s.peek();
                int width = i-leftLimit-1;
 
                int area = width * heights[top];
                maxArea = Integer.max(area, maxArea);
            }
            //Push onto the monotonically increasing stack
            s.push(i);
        }
        return maxArea;
    }

Shortest Unsorted Continuous Subarray

This problem is taken from leetcode and goes like :

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too. You need to find the shortest such subarray and output its length.

Input: [2, 6, 4, 8, 10, 9, 15] Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

We want again to find the left and right boundaries. What if we keep a monotonically increasing queue and put the elements onto it. If the element at the end of the queue is less than the new incoming element, remove it from the queue. Keep going till we find an element in the queue which is less than the incoming element. At the same time, keep track of what is the first index in the queue, because that will be the left-most boundary for the unsorted array.

Now, go from the end of the array and maintain a monotonically decreasing queue. If the new incoming element is greater than the element at the rear of the queue, remove the element from the queue. Keep removing elements from the queue until we find an element greater than the incoming number. Keep track of the maximum index which is in the queue that will be our right boundary.

Now, we know the left and right boundaries, we can easily find the length of the array which is unsorted.

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        
        Stack<Integer> s = new Stack<>();
        Stack<Integer> s1 = new Stack<>();
        
        int rightBound = 0;
        int leftBound = nums.length-1;
         
        /*
            Find the left most index of unsorted array
        */
        for(int i=0; i<nums.length; i++){
            while(!s.isEmpty() && nums[i] < nums[s.peek()]){
                leftBound = Math.min(leftBound, s.pop());
            }
            s.push(i);
        }
        
        /*
            Find the right most index of unsorted array
        */
        for(int i=nums.length-1; i>=0; i--){
            while(!s1.isEmpty() && nums[i] > nums[s1.peek()]){
                rightBound = Math.max(rightBound, s1.pop());
            }
            s1.push(i);
        }
        
        return rightBound - leftBound <= 0 
               ? 0 : rightBound - leftBound + 1; 
    }
}

Other problems you can solve with monotonic queues are :
1. Online Stock Span

class StockSpanner {
    Stack<Integer> s;
    List<Integer> prices;
    
    public StockSpanner() {
        s = new Stack<>();  
        prices = new ArrayList<>();
    }
    
    public int next(int price) {
        //Maintaining the monotonic decreasing
        while(!s.isEmpty() && price >= prices.get(s.peek())){
            s.pop();            
        }
        int lowerIndex = s.isEmpty() ? -1 : s.peek();
        int val = prices.size() - lowerIndex;
        
        prices.add(price);
        s.push(prices.size()-1);
        
        return val;
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

2 Trapping Rain Water

 public int trap(int[] height) {
        int water  = 0;
        
        Stack<Integer> s = new Stack<>();
        int minHeight = 0;
        int prev = 0;
        
        for(int i=0; i < height.length; i++){
            /* If the new height is greater than previous
                we can store some water in between, 
                we are keeping the monotonically decreasing queue
            */
            while(!s.isEmpty() && height[i] > height[s.peek()]){
                prev = s.pop();
                
                if(!s.isEmpty()){
                    minHeight = Math.min(height[i], height[s.peek()]);
                    water = water + ((minHeight - height[prev]) * (i - s.peek() -1));
                }
            }
            s.push(i);
        }
        
        return water;
    }

3. Sliding Window Maximum

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int [] res = new int [nums.length-k + 1];
        Arrays.fill(res, -1);
        Deque<Integer> dq = new ArrayDeque();
        
        for(int i=0; i<nums.length;i++){
            
            //Maintain a monotonic decreasing queue.
            while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]){
                dq.removeLast();
            }
            dq.addLast(i);
            
            //Only if there are more than K elements in window.
            if(i >= k-1){
                //Remove element which are outside of window
                 while(!dq.isEmpty() && dq.peekFirst() + k <= i){
                    dq.removeFirst();
                }
                //The first element is max (monotonic decreasing queue)
                res[i-k+1] = nums[dq.peekFirst()];
            }
        }
        return res;
    }
}

4.Shortest Subarray with Sum at Least K

class Solution {
    public int shortestSubarray(int[] A, int K) {
        
       long[] prefixSum = new long[A.length + 1];
        
       for(int i=0; i<A.length; i++){
           prefixSum[i+1] = prefixSum[i] + (long) A[i];
       }
    
       int ans = A.length + 1;
        
       Deque<Integer> dq = new ArrayDeque<>();
        
        for(int i=0; i<prefixSum.length; i++){
            while(!dq.isEmpty() && prefixSum[dq.peekLast()] >= prefixSum[i]){
                dq.pollLast();
            }
            while(!dq.isEmpty() && prefixSum[dq.peekFirst()] + K <= prefixSum[i]){
                ans = Math.min(ans, i - dq.pollFirst());
            }
            
            dq.offerLast(i);
        }
        
        return ans == A.length + 1 ? -1 : ans;
    }
}

Do you see a pattern in all the solutions above? Yes, because that's how monotonic queues are used to solve problems. If you are preparing for an interview and need some help with preparations, please book a free session or reach out to us.

Reference: Deque