LeetCode - 42. Trapping Rain Water

Thoughts:

I choose two pointer to solve this problem. I can calculate the height of trapped water by comparing the max height of left side bar and the max height of right side bar, then find the minimun one between them.

Thoughts visuzlization:

height = [0,1,0,2,1,0,1,3,2,1,2,1]
waters = 0
l = 0
r = height.length - 1
leftMax = height[l]
rightMax = height[r]

first, I don't need to calculate the first and last bar, it's impossible to trap water
second, I need left and right pointer to compare with the current max height and calculate the height of trapped water
third, I need to move the lower side pointer to the center to keep calculating the height of trapped water
why move the lower side pointer
because the higher one is irrelevant to the trapped water
the height of trapped water is calculated by the lower one
if encounter the equal height, I can move either side, because every height is calculated individually
and I choose move right pointer to left

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 0
 l                     r  rightMax = 1
                          waters = 0

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 1
   l                   r  rightMax = 1
                          waters = 0

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 1
   l                 r    rightMax = 2
                          waters = 0

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 1
     l               r    rightMax = 2
                          waters = 1

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
       l             r    rightMax = 2
                          waters = 1

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
       l           r      rightMax = 2
                          waters = 2

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
       l         r        rightMax = 2
                          waters = 2

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
       l       r          rightMax = 3
                          waters = 2

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
         l     r          rightMax = 3
                          waters = 3

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
           l   r          rightMax = 3
                          waters = 5

[0,1,0,2,1,0,1,3,2,1,2,1] leftMax = 2
             l r          rightMax = 3
                          waters = 6

Code:

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let waters = 0;
  // if not enough bars to trap water, just return 0
  if (height.length < 3) return waters;
  let l = 0;
  let r = height.length - 1;
  let maxLeft = height[l];
  let maxRight = height[r];
  while (l < r) {
    if (maxLeft < maxRight) {
      l++;
      maxLeft = Math.max(maxLeft, height[l]);
      waters += maxLeft - height[l];
    } else {
      r--;
      maxRight = Math.max(maxRight, height[r]);
      waters += maxRight - height[r];
    }
  }
  return waters;
};

Reference

Original link