## 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

## Top comments (0)