## DEV Community # Solving the "Trapping Rain Water" Problem on Leet Code

## 42. Trapping Rain Water

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

Amazon 14
Bloomberg 5
Apple 4
Goldman Sachs 3
Yandex 3
EPAM Systems 2
Microsoft 16
Uber 4
MakeMyTrip 3
eBay 2
Salesforce 2
Intel 8
Rubrik 8
Qualtrics 7
Tesla 6
Oracle 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
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 = height;
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