LeetCode - Trapping Rain Water

DUY HUYNH -

Description: https://leetcode.com/problems/trapping-rain-water/description/

To solve this problem, the main observation is that at each index i, the amount of water that can be trapped depends on the the highest bars to its left and right elements, minus its own height.

Key insights:

  • Water level at index_i = min(maxLeft, maxRight) - height[i]
  • Two-pointer technique optimizes space complexity from %O(N)% to %O(1)%

Algorithm steps:

  1. Initialize two pointers (left, right) at array ends
  2. Track max heights seen from left and right
  3. Process smaller height side first:
    • If current height > max_seen, update max
    • Else add trapped water (max - current_height)
  4. Move pointer inward and repeat

Here are interactive visualizations for two example test cases:

Why it works:

  • When height[left] < height[right], right bar guarantees water can be trapped based on left_max
  • Similarly for right side when height[right] <= height[left]
  • Always process the smaller side since it determines water level

Complexity:

  • Time: %O(N)%
  • Auxiliary space: %O(1)%

You can find the full source code solution at https://github.com/vndee/dsa-python/blob/main/linear_iteration/trapping_rain_water.py. Please consider subscribing to my blog to stay updated with more algorithm tutorials and coding insights.