Trapping Rain Water
Problem Description
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9
DE Shaw Tier 1 — LC 42.
Two approaches:
1. Two pointers O(n) time O(1) space: maintain leftMax, rightMax. Process from whichever side has the smaller max.
2. Monotonic stack O(n): when we see a taller bar, compute water trapped between stack top and current bar.
Talk-track: 'Water at position i is bounded by min(maxLeft, maxRight) - height[i]. Two pointers avoids the O(n) space of precomputed arrays.'
Example Test Cases
Example 1
Input: [[0,1,0,2,1,0,1,3,2,1,2,1]]
Expected: 6
Example 2
Input: [[4,2,0,3,2,5]]
Expected: 9
Example 3
Input: [[1,0,1]]
Expected: 1
Example 4
Input: [[3,0,2,0,4]]
Expected: 7
Run your code to see the results