Question

link

Stats

Frequency	2
Difficulty	4
Adjusted Difficulty	3
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is an interesting question.

Most popular solution is DP. The explanation from this blog is slightly confusing, so I will explain it here. Basic idea is to do 2 iteration. First time get the heighest bound to the left of every point. Second time get the heighest bound to the right.

Example: input = [0,1,0,2,1,0,1,3,2,1,2,1].

Assume the 2 DP arrays are called highestLeftSoFar and highestRightSoFar.

highestLeftSoFar = 0,1,1,2,2,2,2,3,3,3,3,3

highestRightSoFar = 3,3,3,3,3,3,3,3,2,2,2,1

For each point, get the lowest bound (of the 2 bounds), and calculate water.

There is another solution making use of stack from this blog. This idea is IMHO not very good.

1. Use Stack to store the index of a bar;
2. If the current one is smaller then the top of the stack, push it to stack;
3. Otherwise, pop up the top until stack is empty or top is greater than the current one, add up the volume, push the current one to stack.

The tricky part is what is the volume to be added each time when we pop up a value from the stack.

My code

public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        int len = A.length;
        int[] leftBound = new int[len];
        for (int i = 1; i < len; i++) {
            leftBound[i] = Math.max(leftBound[i - 1], A[i - 1]);
        }
        int rightBound = 0;
        int water = 0;
        for (int i = len - 2; i > 0; i--) {
            rightBound = Math.max(rightBound, A[i + 1]);
            int contains = Math.min(leftBound[i], rightBound);
            // important to note, that contains can be 0!
            water += Math.max(0, contains - A[i]);
        }
        return water;
    }
}

Stack Solution.

public int trap(int[] A) {
    int cur = 0;
    while (cur < A.length && A[cur] == 0) cur ++;
    int vol = 0;
    Stack<Integer> stack = new Stack<Integer>();
    while (cur < A.length) {
        while (!stack.isEmpty() && A[cur] >= A[stack.peek()]) {
            int b = stack.pop();
            if (stack.isEmpty()) break;
            vol += ((cur - stack.peek() - 1) * (Math.min(A[cur], A[stack.peek()]) - A[b]));
        }
        stack.push(cur ++);
        cur ++;
    }
    return vol;
}

updated on Aug 27th, 2014, there is a very very good 2 pointer solution which reads the input only once!

This post wrote about it, and source code available.

public int trap(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }

    int len = A.length;
    int left = 0;
    int right = len - 1;
    int leftHeight = 0;
    int rightHeight = 0;
    int water = 0;

    while (left < right) {
        leftHeight = Math.max(leftHeight, A[left]);
        rightHeight = Math.max(rightHeight, A[right]);
        // Two ways to write the following if-condition 
        // This would also work: if (A[left] < A[right]) {
        if (leftHeight < rightHeight) {
            // increase left pointer
            water += leftHeight - A[left];
            left++;
        } else {
            water += rightHeight - A[right];
            right--;
        }
    }
    return water;
}