Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

28. Trapping Rain Water

HardDay 8 of 60Two Pointers

You are given n non-negative integers that describe an elevation map, where each bar has width 1 and height[i] is the height of bar i. After it rains, water collects in the dips between taller bars. Return the total units of water that stay trapped.

Example 1
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Water sits above index 2 (1 unit), indices 4 to 6 (1 + 2 + 1 units) and index 9 (1 unit).
Example 2
Input: height = [4,2,0,3,2,5]
Output: 9
Constraints
  • 1 <= height.length <= 2 * 10^4
  • 0 <= height[i] <= 10^5
Hints
Frequently asked at: Amazon, Google, Goldman Sachs, Microsoft, Bloomberg, Flipkart
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min