BFS 30ms without additional visited matrix.


  • 0
    F
     class Point {
            int x;
            int y;
            int h;
            Point(int i, int j, int height) {
                x = i;
                y = j;
                h = height;
            }
        }
        public static final int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        public int trapRainWater(int[][] heightMap) {
            if (heightMap.length < 3 || heightMap[0].length < 3) return 0;
            int water = 0;
            PriorityQueue<Point> queue = new PriorityQueue<>(1, new Comparator<Point>(){
                @Override
                public int compare(Point p1, Point p2) {
                    return p1.h - p2.h;
                }
            });
            int m = heightMap.length, n = heightMap[0].length, visitedValue = -1;
            for (int i = 0; i < m; i++) {
                queue.add(new Point(i, 0, heightMap[i][0]));
                queue.add(new Point(i, n-1, heightMap[i][n-1]));
                heightMap[i][0] = visitedValue;
                heightMap[i][n-1] = visitedValue;
            }
            
            for (int j = 1; j < n-1; j++) {
                queue.add(new Point(0, j, heightMap[0][j]));
                queue.add(new Point(m-1, j, heightMap[m-1][j]));
                heightMap[0][j] = visitedValue;
                heightMap[m-1][j] = visitedValue;
            }
            
            Point p = null;
            int x, y, counter = (m-1)*(n-1);
            while(queue.size() > 0 && counter > 0) {
                p = queue.poll();
                for (int[] dir: dirs) {
                    x = p.x+dir[0];
                    y = p.y+dir[1];
                    if (x < 0 || x > m-1 || y < 0 || y > n-1 || heightMap[x][y] == visitedValue) continue;
                    if (p.h > heightMap[x][y]) {
                        water += (p.h-heightMap[x][y]);
                        queue.add(new Point(x, y, p.h));
                    } else {
                        queue.add(new Point(x, y, heightMap[x][y]));
                    }
                    heightMap[x][y] = visitedValue;
                    counter--;
                }
            }
            return water;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.