Leetcode - Trapping Rain Water

Question

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.

Ideas

• Kind of like Leetcode - Container With Most Water
• We can use a 2 pointer approach along with the formula water=min(maxL, maxR)-height at i where maxL and maxR are the max wall heights we’ve seen so far to either side of index i
• We can compute this for every i position in height as a brute force solution O(n^2)
• The repeated efforts here are re-finding maxL and maxR
• Instead, using a 2 pointer approach, starting each pointer at either end of the container:
  • We can recognize that our formula for water is depending on the height of the observed position and the minimum of the max bounds we have seen so far
  • Therefore, on each iteration, we want to check if the left or the right wall is the limiting factor:
    • Move the pointer with the smaller max height (container bound) inwards
    • update the max height for that side (maxL or maxR)
    • compute the water trapped at that position using the new max on the side that we just moved
  • This works because this invariant is maintained: maxL = max(height[0..l]) and maxR = max(height[r..n-1]) which is effectively what we are recomputing in the brute force solution above

Solution