Trapping Rain Water II

This page explains Java solution to problem Trapping Rain Water II using Priority Queue data structure.

Problem Statement

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Follow up: The overall run time complexity should be O(log (m+n)).

Example 1:

Input:
[
        [1,4,3,1,3,2],
        [3,2,1,3,2,4],
        [2,3,3,2,3,1]
]
Output: 4

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class TrappingRainWaterIi {
    public int trapRainWater(int[][] height) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            @Override
            public int compare(int[] x, int[] y) {
                return Integer.compare(x[0], y[0]);
            }
        });

        int row = 0;
        int col = 0;
        int n = height.length;
        int m = height[0].length;

        while(col < m) {
            pq.offer(new int[]{height[row][col], row, col});
            height[row][col] = -1;
            col++;
        }
        row++;
        col--;

        while(row < n) {
            pq.offer(new int[]{height[row][col], row, col});
            height[row][col] = -1;
            row++;
        }
        row--;
        col--;

        while(col >= 0) {
            pq.offer(new int[]{height[row][col], row, col});
            height[row][col] = -1;
            col--;
        }
        row--;
        col++;

        while(row > 0) {
            pq.offer(new int[]{height[row][col], row, col});
            height[row][col] = -1;
            row--;
        }

        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int max = 0;
        int res = 0;
        while(!pq.isEmpty()) {
            int[] entry = pq.poll();
            max = Math.max(entry[0], max);
            for(int[] dir: dirs) {
                int xNew = entry[1] + dir[0];
                int yNew = entry[2] + dir[1];
                if(xNew >= 0 && xNew < height.length && yNew >= 0 && yNew < height[0].length && height[xNew][yNew] != -1) {
                    if(max > height[xNew][yNew]) {
                        res += (max - height[xNew][yNew]);
                    }
                    pq.offer(new int[]{height[xNew][yNew], xNew, yNew});
                    height[xNew][yNew] = -1;
                }
            }
        }
        return res;
    }
}

Time Complexity

O(M * N) Where
M is total number of elements in an input array
N is total number of elements in an input array

Space Complexity

O(M + N) Where
M is total number of elements in an input array
N is total number of elements in an input array