mafeshsho8lmafeshsho8l
Get Started
All coding questions

Trapping Rain Water

hard
Blind 75NeetCode 150arraystwo-pointersdynamic-programming

Problem

Given a list of non-negative bar heights forming an elevation map, compute how many units of water are trapped after rain. Water sits in the dips between taller bars.

Examples

Input: heights = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Six units pool in the valleys.
Input: heights = [4, 2, 0, 3, 2, 5]
Output: 9
Water collects in the central dips.

Constraints

  • • 1 <= heights.length <= 2 * 10^4
  • • 0 <= heights[i] <= 10^5
Hints(tap to reveal)
  • 1. Water above a bar is bounded by the tallest bars on each side.
  • 2. Two pointers can track the running max from both ends.
Optimal approach(spoiler)
  1. Use two pointers and track the highest bar seen from the left and from the right.
  2. Advance the side with the smaller running maximum.
  3. Water trapped at that position is its running max minus its own height.
  4. Accumulate this across the array.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor