Leetcode: 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. Thanks Marcos for contributing this image!

Understand the problem:
The problem asks for how much water can be trapped after raining. If you remember, there is another similar problem about container: Container with Most Water. 

Solution:
The trapped water for slot i is determined by min(leftMostHeight[i], rgithMostHeight[i]) - A[i], which means the most water trapped for slot i is determined by the highest block left to i (exclusive), and the highest block right to i, whichever is less, and subtract by the height of the block itself. So we can iterate through the array to get the left highest and right highest for i. Then the third loop is to calculate the trapped water. 

Code (Java):

public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length <= 2) {
            return 0;
        }
        
        int[] maxLeft = new int[A.length];
        int[] maxRight = new int[A.length];
        int max = 0;
        int sum = 0;
        
        for (int i = 1; i < A.length; i++) {
            if (A[i - 1] > max) {
                max = A[i - 1];
            }
            maxLeft[i] = max;
        }
        
        max = 0;
        for (int i = A.length - 2; i >= 0; i--) {
            if (A[i + 1] > max) {
                max = A[i + 1];
            }
            maxRight[i] = max;
        }
        
        for (int i = 0; i < A.length; i++) {
            int water = Math.min(maxLeft[i], maxRight[i]) - A[i];
            if (water > 0) {
                sum += water;
            }
        }
        return sum;
    }
}

Discussion:
The time complexity is O(n). The space complexity is O(n) as well since we used two additional arrays.
Summary:
This problem is very similar to the most container water. But the container takes 1 unit. For these kind of application problems, it is very important to generalize it to a mathematical problem, especially a equation.