Solving the "Trapping Rain Water" Problem on Leet Code

Question

42. Trapping Rain Water

Type: Hard
Liked by: 29K
Disliked by: 412

Companies that asked this Question
Companies: No of times Asked

Amazon 14
Bloomberg 5
Adobe 4
Apple 4
Goldman Sachs 3
Yandex 3
EPAM Systems 2
Microsoft 16
Google 9
Uber 4
MakeMyTrip 3
Facebook 2
eBay 2
Salesforce 2
Intel 8
Rubrik 8
Qualtrics 7
Tesla 6
Oracle 5
Citadel 5
VMware 4
C3 IoT 4
Snapchat 3
Lyft 3
Visa 3
PayPal 3
ServiceNow 3
Swiggy 3
National Instruments 3
Sapient 3
Zoho 2
Intuit 2
Coupang 2
Yahoo 2
Expedia 2
Twitch 2
Morgan Stanley 2
DE Shaw 2
TikTok 2
Navi 2
Airbnb 1
Zenefits 1
Twitter 1
Wix 1

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 rainwater (blue section) are being trapped.

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

Constraints:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Intuition:

The goal is to calculate the total trapped water between bars with given heights. We achieve this by computing left and right boundaries for each bar and then calculating trapped water based on these boundaries.

Approach:

• Initialize res to 0, lb (left boundaries), and rb (right boundaries) arrays.
• Calculate left boundaries (lb) and right boundaries (rb) for each bar in the input array.
• Iterate through the input array, calculating trapped water for each bar and accumulating it in res.
• Return res as the total trapped water.

Complexity:

Time complexity: O(n) where n is the number of elements in the input array.

Space complexity: O(n) due to the lb and rb arrays used to store boundaries.

Code:

class Solution {
    public int trap(int[] height) {
        int  res = 0;
        int[] lb = new int[height.length];
        int[] rb = new int[height.length];

        lb[0] = height[0];
        for(int i = 1 ; i < height.length -1 ;i++){
            lb[i] = Math.max(height[i],lb[i-1]);
        }

        rb[height.length - 1] = height[height.length - 1 ];
        for(int i = height.length - 2 ; i >= 0;i--){
            rb[i] = Math.max(height[i],rb[i+1]);
        }

        for(int i = 1 ; i < height.length -1 ; i++){
            int tw = Math.min(lb[i],rb[i]) - height[i];
            res = res + tw;
        }

        return res;
    }
}

Happy coding,
shiva