Daily Archives: October 12, 2015

Problem description:
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 the input
[0,1,0,2,1,0,1,3,2,1,2,1]

the return value would be
6

This problem can be solved in O(n) time, by going through from left to right, and right to left to record the maximum height to now in O(n) time, O(n) space. The code is like below:

public int trap2(int[] height) {
    int[] leftDp = new int[height.length], rightDp = new int[height.length];
    int leftMax = 0, rightMax = 0;
    for (int i = 0; i < height.length; i++) {
        leftDp[i] = leftMax;
        leftMax = Math.max(leftMax, height[i]);
        rightDp[height.length - i - 1] = rightMax;
        rightMax = Math.max(rightMax, height[height.length - i - 1]);
    }
    int ans = 0;
    for (int i = 0; i < height.length; i++) {
        int hi = Math.min(leftDp[i], rightDp[i]);
        ans += hi <= height[i] ? 0 : (hi - height[i]);
    }
    return ans;
}

However, this problem can be solved in O(n) time and O(1) space. Starting from left and right. Handle the smaller one and update the area size:

public int trap(int[] height) {
    int leftMax = 0, rightMax = 0, areaSize= 0, left = 0, right = height.length - 1;
    while (left <= right) {
        if (height[left] <= height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            areaSize += leftMax - height[left++];
        }
        else {
            rightMax = Math.max(rightMax, height[right]);
            areaSize += rightMax - height[right--];
        }
    }
    return areaSize;
}

Check my code on github: link