Trapping Rain Water – Java

O(n) Memory and O(n) time

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;
 }
}