Rain water trapped problem

rain-water-trapped.js

// The idea is to use two pointer technique, pointer i & j for optimal solution
// run time complexity O(N)
// space time complexity O(1)

function trappedWater(height) {
  if (height < 3) return 0;

  // initialize trappedWater to zero
  let trappedWater = 0;

  // i starts from left which zero index
  // and j starts from right which is last index
  let i = 0;
  let j = height.length - 1;

  // initialize leftMax and rightMax to first value and last last
  let leftMax = height[i];
  let rightMax = height[j];

  // iterate util i is smaller then j
  while (i < j) {
    if (height[i] < height[j]) {
      // calculate left max and add trapped water to total
      i++;
      leftMax = Math.max(leftMax, height[i]);
      trappedWater += leftMax - height[i];
    } else {
      // calculate right max and add trapped water to total
      j--;
      rightMax = Math.max(rightMax, height[j]);
      trappedWater += rightMax - height[j];
    }
  }
  // return total trapped water
  return trappedWater;
}

var input = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
var output = trappedWater(input);
console.log(output);
// Output: 6