Skip to main content

0042 - Trapping Rain Water (Hard)

https://leetcode.com/problems/trapping-rain-water/

Problem Statement​

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

Approach 1: Dynamic Programming​

Written by @wingkwong
// Time Complexity: O(N)
// Space Complexity: O(N)
// where N is the length of height
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, n = height.size();
        // dp1[i]: the max height of bar from the left till position i
        // dp2[i]: the max height of bar from the right till position i
        vector<int> dp1(n), dp2(n);
        // let's build dp1 first
        dp1[0] = height[0];
        // for each position i,
        // if the current height is greater than the max height, then dp1[i] will be height[i]
        // else dp1[i] will be taking the previous result, i.e. dp1[i - 1]
        for (int i = 1; i < n; i++) dp1[i] = max(dp1[i - 1], height[i]);
        // build dp2 in a similar way
        dp2[n - 1] = height[n - 1];
        // for each position i,
        // if the current height is greater than the max height,
        // then dp2[i] will be height[i]
        // else dp2[i] will be taking the previous result, i.e. dp2[i + 1]
        for (int i = n - 2; i >= 0; i--) dp2[i] = max(dp2[i + 1], height[i]);
        // then iterate the heights and take the minimum of dp1[i] and dp2[i]
        // why minimum? because that is the max height a bar can hold. (water will overflow)
        // then we substract height[i] from the min
        // if min(dp1[i], dp2[i]) is 2 and height[i] is 2, then no water is being trapped
        // if min(dp1[i], dp2[i]) is 2 and height[i] is 0, then 2 units of water are being trapped
        for (int i = 1; i < n - 1; i++) ans += min(dp1[i], dp2[i]) - height[i];
        return ans;
    }
};

Approach 2: Two Pointers​

Written by @wingkwong
// Time Complexity: O(N)
// Space Complexity: O(1)
class Solution {
    public int trap(int[] height) {
        int i = 0, j = height.length - 1, ans = 0, mx = 0, mi = 0;
        // two pointers
        // pointer i from the left
        // pointer j from the right
        while (i <= j) {
            // take the min height
            mi = Math.min(height[i], height[j]);
            // find the max min height
            mx = Math.max(mx, mi);
            // the units of water being tapped is the diffence between max height and min height
            ans += mx - mi;
            // move the pointer i if height[i] is smaller
            if (height[i] < height[j]) i++;
            // else move pointer j
            else j--;
        }
        return ans;
    }
}
Written by @vigneshshiv
// Time Complexity: O(N)
// Space Complexity: O(N)
class Solution {
    public int trap(int[] height) {
        int i = 0, j = height.length - 1;
        int level = 0, water = 0;
        while (i < j) {
            // Get the minium height and change the index depends on height
            int lower = height[height[i] < height[j] ? i++ : j--];
            // Highest peak gives total area to calculate water
            level = Math.max(level, lower);
            // How much water can hold from the recently calculated height
            water += level - lower;
        }
        return water;
    }
}

Approach 3: Monotonic Stack​

Monotonic stacks are generally used for solving questions of the type - next greater element, next smaller element, previous greater element and previous smaller element.

This problem one of the problem of solving with the previous heights with the current height.

  1. Keep adding the index (referenced to height) into stack, if the current height is higher the last added one (Stack Top)

  2. Once we find there's a downward slop, means this is starting position to trap water fill (hold the water). So keep calculating water trap area with the height and the index. Since we need to find the height and width of water area, indices are required to find the width (the same is maintained in the stack).

  3. Keep repeating the process until the we reach last or there's no higher height to calculate the water fill (Stack is empty).

Written by @vigneshshiv
// Time Complexity: O(N)
// Space Complexity: O(N)
class Solution {
    public int trap(int[] height) {
        int water = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                int j = stack.pop();
                if (!stack.isEmpty()) {
                    int h = Math.min(height[stack.peek()], height[i]) - height[j];
                    int w = i - (stack.peek() + 1);
                    water += (h * w);
                }
            }
            stack.push(i);
        }
        return water;
    }
}