JSFiddle - React, Tailwind, and code Playground

by Stepan Parunashvili

JavaScript

/*
	Key Insight
  	The height at any point is defined like so:
    	the minimum of 
	    	the maximum left boundary
  	    the maximum right boundary
       if that minimum is greater then the current height
       	then water will get trapped
        	min(left, right) - height
	
  The brute force idea would be
  	At each point, calculate the max left and max right
    	if higher, then add the difference between that and the current height
*/

/*
   One way to improve it is to run through the array twice
   The first time, just record the max left until i
   The second time, go backwards, starting from the second-last element
   Keep track of the maxRight you see so far
   Then bam, you got the boundaries
*/
function trapRunTwice(height) {
  let maxLefts = [height[0]];
  for (let i = 1; i < height.length - 1; i++) {
    maxLefts[i] = Math.max(maxLefts[i - 1], height[i])
  }
  let maxRight = height[height.length - 1];
  let res = 0;
  for (let i = height.length - 2; i > 0; i--) {
    maxRight = Math.max(height[i + 1], maxRight);
    let minBoundary = Math.min(maxRight, maxLefts[i - 1]);
    let thisHeight = height[i];
    if (thisHeight < minBoundary) {
      res += minBoundary - thisHeight;
    }
  }
  return res;
}

/*
	one way we can think about it is like this: 
	
  let's start with the leftMax, rightMax at each end
  with two pointers, leftIdx, rightIdx
  if leftMax < rightMax
  	- we know that the left element can at most have the boundary leftMax
    - and a rightMax already exists that could trap the water
		- so we can advance
  if rightMax < leftMax
  	- we know that the right element can at most have the boundary rightMax
    - and a leftMax exists that would trap the water
    - so we can advance
  start with the two pointers, left and right
*/
function trapRunOnce(height) {
	let leftMax = height[0];
  let rightMax = height[height.length - 1];
  let leftIdx = 1;
  let rightIdx = height.length - 2;
  let res = 0;
  while (leftIdx <= rightIdx) {
	  if...