Water Area

Tags

Water Area

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given an array of non-negative integers representing an elevation map where each element's value is the height of a bar (with width 1), compute how much water can be trapped after raining. This is the classic "trapping rain water" problem.

Intuition

Water above any position is determined by the minimum of the tallest bars on its left and right, minus its own height. Formally, the water at index i is max(0, min(maxLeft[i], maxRight[i]) - height[i]). The bottleneck is always the shorter of the two surrounding walls.

We can precompute the maximum height to the left and right of each position, then calculate the water at each position in a final pass. Alternatively, a two-pointer approach achieves the same result in a single pass with O(1) space.

Approach

Precomputation Approach

  1. Build maxLeft array: maxLeft[i] = max height in heights[0..i].
  2. Build maxRight array: maxRight[i] = max height in heights[i..n-1].
  3. For each index i, water = max(0, min(maxLeft[i], maxRight[i]) - heights[i]).
  4. Sum all water values.

Two-Pointer Approach

  1. Initialize left = 0, right = n - 1, maxLeft = 0, maxRight = 0, water = 0.
  2. While left < right:
    • If heights[left] < heights[right]: process left side, update maxLeft, accumulate water if applicable, move left forward.
    • Else: process right side, update maxRight, accumulate water if applicable, move right inward.
  3. Return water.

Pseudocode

function waterArea(heights):
    n = length(heights)
    if n == 0:
        return 0

    maxLeft = array of size n
    maxRight = array of size n

    maxLeft[0] = heights[0]
    for i from 1 to n - 1:
        maxLeft[i] = max(maxLeft[i - 1], heights[i])

    maxRight[n - 1] = heights[n - 1]
    for i from n - 2 down to 0:
        maxRight[i] = max(maxRight[i + 1], heights[i])

    water = 0
    for i from 0 to n - 1:
        water += max(0, min(maxLeft[i], maxRight[i]) - heights[i])

    return water

Time & Space Complexity

  • Precomputation Approach:
    • Time: O(n). Three linear passes.
    • Space: O(n) for the two auxiliary arrays.
  • Two-Pointer Approach:
    • Time: O(n). Single pass.
    • Space: O(1).

Key Insights

  • Water at each position is bounded by the shorter of the tallest walls on either side. This is the core insight.
  • The two-pointer approach works because we always process the side with the shorter maximum. The water level at that side is guaranteed to be determined by that shorter maximum, regardless of what lies between.
  • Bars at the edges (index 0 and n-1) can never hold water since there is no wall on one side.
  • This problem can also be solved using a stack-based approach that processes horizontal layers of water.

Edge Cases

  • Empty array: return 0.
  • Array with fewer than 3 elements: no water can be trapped (need at least two walls and a gap).
  • Flat array (all same height): no water trapped.
  • Strictly increasing or decreasing array: no water trapped.
  • Single peak (mountain shape): water is trapped on neither side.
  • Valley shape (high-low-high): water fills the valley.

Linked mentions