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.

jump game leetcode

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.

Prime Course Trailer

Related Banners

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

Code :

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription