Trapping Rain Water

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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

The idea is to maintain two array, the first one is to track for current position what is the highest bar in its left, the second one is to track for current position what is the highest bar in its right.

Then find the lower one from left[i-1] and right[i+1], if it is more than the current position, we know how much water we can trap in this position.

public int trap(int[] A) {
        int[] left = new int[A.length];
        int[] right = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            left[i] = i > 0 ? Math.max(left[i - 1], A[i]) : A[i];
        }
        for (int i = A.length - 1; i >= 0; i--) {
            right[i] = i < A.length - 1 ? Math.max(right[i + 1], A[i]) : A[i];
        }
        int result = 0;
        for (int i = 1; i < A.length - 1; i++) { //two edges can't trap anything
            int lowBar = Math.min(left[i - 1], right[i + 1]);
            if (lowBar > A[i])
                result += lowBar - A[i];
        }
        return result;
    }