Trapping Rain Water

Javascript (ES6)

/**
 * @param {number[]} height
 * @return {number}
 */
const trap = function(height) {
  const left = [];
  const right = [];
  let lmax = height[0];
  let rmax = height[height.length - 1];
  for (let i = 0; i < height.length; i++) {
    if (height[i] > lmax) {
      lmax = height[i];
    }
    left[i] = lmax;
    let j = height.length - i - 1;
    if (height[j] > rmax) {
      rmax = height[j];
    }
    right[j] = rmax;
  }
  let total = 0;
  for (let i = 0; i < height.length; i++) {
    total += Math.abs(height[i] - Math.min(left[i], right[i]));
  }
  return total;
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])); // 6

Demo

Java

Time: O(n)
Memory: O(n)

class Solution {
 public int trap(int[] height) {
  int n = height.length;
  if (n == 0)
   return 0;
  int[] left = new int[n];
  int[] right = new int[n];
  left[0] = height[0];
  right[n - 1] = height[n - 1];
  int j;
  for (int i = 1; i < n; i++) {
   left[i] = Math.max(left[i - 1], height[i]);
   right[n - i - 1] = Math.max(right[n - i], height[n - i - 1]);
  }
  int area = 0;
  for (int i = 1; i < n - 1; i++) {
   area += Math.min(left[i], right[i]) - height[i];
  }
  return area;
 }
}