# 42. Trapping Rain Water Leetcode Solution

## Trapping Rain Water Leetcode Problem :

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.

## Trapping Rain Water Leetcode Solution :

### Constraints :

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

### Example 1:

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

Approach :

Iterate from left to right with two pointers.
When we come across height[end] >= height[start], fill the pool with water, while keeping track of ‘occupied area’ (i.e. elevations from steps in between).

At the same time, use a hash-set to keep track of the indices already filled. Because we can’t hash a pair<int,int>, we use a basic hashing function (start*20000 + end), since those are the size constraints, and we know the result of the hash fits within an int32 data type.

Then iterate from right to left. There must be a second sweep from right to left because we could have cases where there’s a huge ‘wall’ on the left and the left->right sweep wouldn’t conclude those pools to be fillable.

We do the same thing, but everytime the right->left sweep detects something fillable, check if that pool has already been filled by O(1) search on the hashset. If not, add to the accumulated fill area.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others