Trapping Rain Water - Leetcode

trap.java

/*
Given n non-negative integers representing an elevation map where 
the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Algorithm: 
1. construct 2 arrays that store the max from left to right and max from right to left
2. At position i, we now know the max from its left and right, then find the max trapped water.
*/
public class Solution {
    public int trap(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        // check the max from the left to right
        int size = A.length;
        if(size == 0) return 0;

        int[] left_to_right_max = new int[size];
        int[] right_to_left_max = new int[size];

        left_to_right_max[0] = A[0];
        for(int i = 1; i < size; i++) {
            if(A[i] > left_to_right_max[i-1]) {
                left_to_right_max[i] = A[i];
            } else {
                left_to_right_max[i] = left_to_right_max[i-1];
            }
        }
        
        right_to_left_max[size-1] = A[size-1];
        for(int i = size - 2; i >= 0; i--) {
            if(right_to_left_max[i+1] < A[i]) {
                right_to_left_max[i] = A[i];
            } else {
                right_to_left_max[i] = right_to_left_max[i+1];
            }
        }
        
        // find the max water trapped
        int trapped_max = 0;
        for(int i = 0; i < size; i++) {
            if(left_to_right_max[i] > A[i] &&
               right_to_left_max[i] > A[i]) {
                   trapped_max += Math.min(left_to_right_max[i] - A[i],
                                           right_to_left_max[i] - A[i]);
               }
        }
        
        return trapped_max;
    }
}