Trapping rain water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after rain. For example,

Input: [0,1,0,2,1,0,1,3,2,1,2,1] 
Output: 6

trapping rain water

Basic thought

We know water stays at the highest level it is able to, and it always maintains the same flat surface. Using this, we can infer that we need to find holes in the elevation where water would be able to rest at a level. To calculate how much water these holes would need to store, we can see that we need to have elevations on both sides, and we also need to track how much space a particular hole would be able to trap the water. Fig below is an example of a hole which holds 4 units of water.

trap water

Upon further breakdown of these holes, we can notice that we do not need to track the entire hole to find the capacity it holds, but we can parse each unit of the hole individually. Thus, the amount of water in each unit of the hole is

min(leftHeight, rightHeight) - currentUnitHeight.

What remains now is to calculate the leftHeight and the rightHeight. We could parse through them individually to find these out, but we can see a general pattern here: The highest elevation to the left inclusive of the current unit will become the leftHeight, and the highest elevation to the right inclusive of the current unit will become the rightHeight. The problem has been greatly simplified into maintaining track of highest heights on both sides of every unit.

Brute force solution

From our observations in the previous section, the simplest brute force approach is to calculate the highest elevation on both sides of every unit, and sum them up together. Each unit takes O(n) time with this approach, and there are n units to calculate in total. Thus, this approach will take O(n2) time.

Show me the brute force implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        ans = 0
        for i in range(len(height)):
            left_max = 0
            right_max = 0
            for j in range(i + 1):
                left_max = max(left_max, height[j])
            for j in range(i, len(height)):
                right_max = max(right_max, height[j])
            ans += min(left_max, right_max) - height[i]
        return ans

Dynamic Programming approach

As we can see from the brute force solution, we calculate the leftHeight and the rightHeight multiple times for the same node, i.e. the problem has overlapping subproblems. Thus a dynamic programming approach should optimize the brute force approach further. We can store the leftHeight and rightHeight elements till each index we have iterated, and thus the water storage calculation for each unit will now take O(1) time. Overall, this approach passes over the array thrice, and thus has a runtime of O(n) with a space complexity of O(n).

Show me the dynamic programming implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        ans = 0
        left_max = [0] * len(height)
        right_max = [0] * len(height)
        left_max[0] = height[0]
        right_max[-1] = height[-1]
        for i in range(1, len(height)):
            left_max[i] = max(height[i], left_max[i - 1])
        for i in reversed(range(len(height) - 1)):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, len(height) - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

Stacks

Since we need to keep track of the highest elevations up to a point, stacks are a good approach to perform this operation in one pass of the array. The basic idea is since we need to store the largest elevations in the stack, as we iterate through the array, we can find the amount of water stored till the currentHeight is higher than elements of the stack and move on to the next value, i.e. water stored will always be of a hole shape, thus we can find the amount of water that can be stored between two high values. This operation passes over the array once, and each element can only have two operations maximum: Pushing and popping from the stack, thus its time complexity is O(n). The space complexity will be O(n), in case the entire array is stored on the stack.

Show me the stack implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3: return 0 ans = 0 stack = [] for i in range(len(height)): while len(stack) > 0 and height[i] > height[stack[-1]]:
                top = stack.pop()
                if len(stack) == 0:
                    break
                # Distance between the larger value still in the 
                #stack with a hole the height of the top element 
                #and the current element
                distance = i - stack[-1] - 1
                # Water that can be stored is smaller 
                # heights between these bounds, and the height 
                # of the intermediate region between top of the stack 
                # and current index
                curr_height = min(height[i], height[stack[-1]]) - height[top]
                ans += distance * curr_height
            stack.append(i)
        return ans

Simple Optimization

Another way to approach the problem is that since we need to find the maximum elevations on either side to calculate the current water stored, we can calculate the global maximum in one pass, and once we have the index for the same, we can iterate to it and from it to the rest of the array knowing that we have one bounded measurement which is the highest elevation in the array. The time complexity for this operation is O(n), but there are two passes over the array(once to calculate global maximum, and once to calculate the water amount). The space complexity is O(1).

Show me the implementation

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) < 3:
            return 0
        ans = 0
        gMax = 0 # Global Max
        for i in range(len(height)):
            gMax = i if height[gMax] < height[i] else gMax
        lMax = 0 # Left max yet
        for i in range(1, gMax):
            lMax = i if height[lMax] <= height[i] else lMax
            ans += max(0, height[lMax] - height[i])
        lMax = len(height) - 1 # Right max yet
        for i in reversed(range(gMax, len(height) - 1)):
            lMax = i if height[lMax] <= height[i] else lMax
            ans += max(0, height[lMax] - height[i])
        return ans

This article is contributed by Khushman Patel

Monotonic queue:Keep things in order in a technical interview

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