Problem

42. Trapping Rain Water

Approach I - Dynamic Programming

1. We calculate how much water each bar can hold.

   • Find the leftmost and rightmost boundary of this bar.
   • The leftmost boundary is the bar of the least heigh that is greater than the current bar on the left.
   • The rightmost boundary is the bar of the least heigh that is greater than the current bar on the right.

2. After finding both boundaries, the water the current bar can hold is

   units = min(leftBoundary, rightBoundary) - heightOfCurrentBar

3. In the case that no valid left boundary or right boundary can be found, use the height of itself as the boundary, i.e. the current bar can not hold any water.

How to find the boundaies? Take the leftboundary for example. Let left[i] be the leftmost boundary of ith bar.

1. Base case:
   • The boundary of the first bar is itselt. left[0] = 0
2. Transition Function.
   • If current bar is higher than the leftmost boundary of previous bar, (the current bar is the highest bar so far), left[i] = i
   • Else left[i] = left[i - 1]

The rightmost boundary is calculuated in the similar way, but from right to left.

Total = 6.

Pseudo Code

withDP(A)
   left = findLeftBoundary(A)
   right = findRightBoundary(A)
   units = 0

   for i = 1 to A.length
      units += min(left[i], right[i]) - A[i]

   return units


findLeftBoundary(A)
  N = A.length
  Define an array of length N left
  left[0] = 0

  for i = 1 to N - 1
    if A[i] >= left[i - 1]
      left[i] = i
    else
      left[i] = left[i - 1]

  return left

Approach II - Monotonic Stack

In the first approach, we need to iterate the original array three times. With the usage of a stack, we can do it in one pass. The idea is to maintain a monotonically decreasing stack and pop the stack whenever a new bar with greater height is encountered. The sum of the area formed by the bar second to the top, the top, and the new higher bar is the desired result.

withMonotonicStack(A)
  N = A.length
  sum = 0
  Let S be a stack
  for i = 0 to N - 1
    while S is not empty and A[i] > A[S.top]
      top = s.pop
      left = s.isEmpty ? top : s.top
      right = i
      sum += (min(A[left], A[right]) - A[top]) * (right - left - 1)
    S.push(i)
  return sum

Approach III - Two Pointers

The water a bar can hold is determined by its left maximum height and right maximum height. To be more precisely, it is determined by the smaller value between the left maximum and right maximum height

units = min(leftMax, rightMax) - heightOfCurrentBar

We use two pointers, left and right, to track the bars we are going to examine in the next loop. We also keep track of the maximum heights of bar[0 ... left - 1] (left maximum) and bar[right + 1 ... n - 1] (right maximum).

Take bar[0] for example,

# Let A be an array of heights of the bars
withTwoPointers(A)
   left = 0, right = A.length - 1
   leftMax = 0, rightMax = 11
   units = 0

   while left < right
      if leftMax < rightMax
         units += A[leftMax] - A[left]
         leftMax = max(leftMax, A[++left])
      else
         units += rightMax - A[right]
         rightMax = max(rightMax, A[--right])

   return uints