Search for a command to run...
Water held between bars, in one two-pointer pass
Try your own input
Change the array and replay the algorithm from step one.
Initialization
Precompute, for every index, the tallest bar at or left of it and the tallest at or right of it. Then each position's water is min(leftMax, rightMax) − height, whenever that is positive.
Prefix & Suffix Max
1function findPrefixMax(arr, n) {2 const prefixMax = new Array(n);3 prefixMax[0] = arr[0];4 for (let i = 1; i < n; i++) {5 prefixMax[i] = Math.max(prefixMax[i - 1], arr[i]);6 }7 return prefixMax;8}9 10function findSuffixMax(arr, n) {11 const suffixMax = new Array(n);12 suffixMax[n - 1] = arr[n - 1];13 for (let i = n - 2; i >= 0; i--) {14 suffixMax[i] = Math.max(suffixMax[i + 1], arr[i]);15 }16 return suffixMax;17}18 19function trap(height) {20 const n = height.length;21 let total = 0;//n: 6total: 022 const leftMax = findPrefixMax(height, n);23 const rightMax = findSuffixMax(height, n);24 for (let i = 0; i < n; i++) {25 if (height[i] < leftMax[i] && height[i] < rightMax[i]) {26 total += Math.min(leftMax[i], rightMax[i]) - height[i];27 }28 }29 return total;30}