โ† OYO questions

Water tapping problem

Filed under OYO

Free read 1 of 3

Use two pointers starting at both ends of the array.

The question

Given an array of non-negative integers representing an elevation map, compute how much water it can trap after raining.

Constraints

  • Array length up to 10^5
  • Elements are non-negative
  • O(n) time complexity required

Examples

Input
[0,1,0,2,1,0,1,3,2,1,2,1]
Output
6
Why
The elevation map traps 6 units of water.

Approach

  1. Use two pointers starting at both ends of the array.

Solution

O(n) time, O(1) space

Python
def trap(height):
    l, r = 0, len(height) - 1
    l_max, r_max = 0, 0
    water = 0
    while l < r:
        if height[l] < height[r]:
            l_max = max(l_max, height[l])
            water += l_max - height[l]
            l += 1
        else:
            r_max = max(r_max, height[r])
            water += r_max - height[r]
            r -= 1
    return water

Tips

  • What they are testing: Test with flat arrays and strictly increasing/decreasing arrays.
  • Common mistake: Using a brute force O(n^2) approach by finding max left and right for every element.

Related OYO questions

Collected from public candidate posts and coding forums. Updated Nov 2026.