Trapping Rain Water - Lintcode

Given_n_non-negative integers representing an elevation map where the width of each bar is1, compute how much water it is able to trap after raining.

Example

Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

Analysis

From the graph, it's obvious to see that if the rightmost bar > leftmost bar, the the water can only flow away from the left side; and how much water is trapped is if (Bar(left) > Bar(left+1)) then Bar(left) - Bar(left+1), else 0. Same logic works for the bars on the right side. With this in mind, writing the algorithm with two pointers is a simple process.

Solution

public int trapRainWater(int[] heights) {
    int left = 0;
    int right = heights.length - 1;
    int res = 0;
    int leftHeight = Integer.MIN_VALUE;
    int rightHeight = Integer.MIN_VALUE;

    while (left < right){
        leftHeight = Math.max(leftHeight, heights[left]);
        rightHeight = Math.max(rightHeight, heights[right]);

        if (leftHeight < rightHeight){
            left++;
            if (leftHeight > heights[left]){
                res += leftHeight -heights[left];
            }
        } else {
            right--;
            if (rightHeight > heights[right]){
                res += rightHeight - heights[right];
            }
        }
    }

    return res;
}

Trapping Rain Water II

Givenn_x_m_non-negative integers representing an elevation map 2d where the area of each cell is_1_x_1, compute how much water it is able to trap after raining.

Example

Given5*4matrix

[12,13,0,12]
[13,4,13,12]
[13,8,10,12]
[12,13,12,12]
[13,13,13,13]

return14.

Analysis

It requires similar analysis as Trapping Rain Water I. First we need to establish the boundary (outermost cells on each side) for the map to hold water. The lowest cell of the boundary is identified and if it's higher than its neighboring inner cells, then it's holding water. And the inner cells are then compared to their neighboring cells for the same calculation. A matrix is required to mark the cells that have been visited to avoid infinite loops.

class Cell implements Comparable<Cell> {
    int x, y, h;

    public Cell(int x, int y, int h) {
        this.x = x;
        this.y = y;
        this.h = h;
    }

    @Override
    public int compareTo(Cell o) {
        return this.h - o.h;
    }
}

int[] deltaX = { 0, 0, 1, -1 };
int[] deltaY = { 1, -1, 0, 0 };

public boolean inBound(int x, int y, int[][] heights) {
    if (x < 0 || x >= heights.length || y < 0 || y >= heights[0].length) {
        return false;
    }
    return true;
}

public int trapRainWater(int[][] heights) {
    int res = 0;
    if (heights == null || heights.length <= 2 || heights[0].length <= 2) {
        return res;
    }

    PriorityQueue<Cell> queue = new PriorityQueue<Cell>();
    boolean[][] visited = new boolean[heights.length][heights[0].length];
    int n = heights.length;
    int m = heights[0].length;

    // row 1 and row n - 1;
    for (int i = 0; i < n; i++) {
        queue.offer(new Cell(i, 0, heights[i][0]));
        queue.offer(new Cell(i, m - 1, heights[i][m - 1]));
        visited[i][0] = true;
        visited[i][m - 1] = true;
    }

    for (int i = 1; i < m - 1; i++) {
        queue.offer(new Cell(0, i, heights[0][i]));
        queue.offer(new Cell(n - 1, i, heights[n - 1][i]));
        visited[0][i] = true;
        visited[n-1][i] = true;
    }

    while (!queue.isEmpty()) {
        Cell min = queue.poll();

        for (int i = 0; i < 4; i++) {
            int nx = min.x + deltaX[i];
            int ny = min.y + deltaY[i];

            if (inBound(nx, ny, heights) && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.offer(new Cell(nx, ny, Math.max(min.h, heights[nx][ny])));
                res += Math.max(0, min.h - heights[nx][ny]);
            }
        }
    }

    return res;
}