Trapping Rain Water Leetcode Solution

Difficulty Level Hard
Frequently asked in Accolite Adobe Airbnb Amazon Apple Bloomberg ByteDance Cisco Citadel Databricks DE Shaw eBay Expedia Facebook Flipkart Goldman Sachs Google Grab Intel Intuit lyft Microsoft Morgan Stanley Oracle PayPal Publicis Sapient Qualtrics Rubrik ServiceNow Snapchat Swiggy Tesla Twitch Twitter Uber Visa VMware Yahoo Zenefits Zoho
Array Dynamic Programming Stack tiktok Two Pointers Walmart Global techViews 5428

Problem Statement

The Trapping Rain Water LeetCode Solution – “Trapping Rain Water” states that given an array of heights which represents an elevation map where the width of each bar is 1. We need to find the amount of water trapped after rain.

Example:

Trapping Rain Water Leetcode Solution

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

Explanation:

  • Check the above diagram for a better understanding.
  • The Blue section denotes the amount of water trapped.
Input:  height = [4,2,0,3,2,5]
Output: 9

Explanation:

  • A total of 9 units of water are trapped.

Approach

Idea:

  1. The main idea to solve this problem is to use dynamic programming.
  2. We need to find the amount of water trapped after rain.
  3. We’ll find the amount of water trapped above for each 1 unit bar and sum up all water trapped for each bar.
  4. Now, for each bar there exists two cases:
    1. Consider, that every bar on either side has a height less than or equal to the current height of the bar.
    2. Consider, that there exists at least 1 bar on either side, which has a height strictly greater than the current height of the bar.
  5. For the first case, we must say that there won’t be any water trapped above the current bar since the current bar has a greater height than all the bars on either side.
  6. For the second case, the amount of water trapped is equal to min(H1, H2) – H, where H1 is the maximum height of the bars present on the left side, H2 is the maximum height of the bars present on the right side and H is the current height of the bar.
  7. Compute Maximum Prefix and Suffix Sum, which helps to find the amount of water trapped above each bar in constant time.
  8. Now, for each bar, add the answer min(H1, H2) – H, where H1 and H2 can be easily obtained from prefix and suffix sum respectively.

Code

Trapping Rain Water C++ Solution:

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pref(height.begin(),height.end());
        vector<int> suff(height.begin(),height.end());
        for(int i=1;i<n;i++){
            pref[i] = max(pref[i],pref[i-1]);
        }
        for(int i=n-2;i>=0;i--){
            suff[i] = max(suff[i],suff[i+1]);
        }
        int ans = 0;
        for(int i=1;i<n-1;i++){
            ans += max(0,min(pref[i-1],suff[i+1])-height[i]);
        }
        return ans;
    }
};

Trapping Rain Water Java Solution:

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] pref = new int[n];
        int[] suff = new int[n];
        for(int i=0;i<n;i++){
            pref[i] = height[i];
            if(i>0){
                pref[i] = Math.max(pref[i],pref[i-1]);
            }
        }
        for(int i=n-1;i>=0;i--){
            suff[i] = height[i];
            if(i+1<n){
                suff[i] = Math.max(suff[i],suff[i+1]);
            }
        }
        int ans = 0;
        for(int i=1;i<n-1;i++){
            ans += Math.max(0,Math.min(pref[i-1],suff[i+1])-height[i]);
        }
        return ans;
    }
}

Complexity Analysis for Trapping Rain Water Leetcode Solution

Time Complexity

The time complexity of the above code is O(N) since we traverse the entire input array at most 3 times.

Space Complexity

The space complexity of the above code is O(N). We’re using an extra array of size N to store prefix and suffix maximum heights.

Translate »