LeetCode - Algorithms - 542. 01 Matrix

Problem

542. 01 Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Java

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    final static int d[][] = {
            {0,1},
            {1,0},
            {0,-1},
            {-1,0}
    };
    
    public int[][] updateMatrix(int[][] matrix) {
        int h = matrix.length;
        int w = matrix[0].length;
        int[][] dist = new int[h][w];

        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) {
                dist[i][j]=Integer.MAX_VALUE;
            }
        }

        Queue<int[]> queue = new LinkedList<int[]>();
        for(int i=0;i<h;i++) {
            for(int j=0;j<w;j++) {
                if (matrix[i][j]==0) {
                    dist[i][j]=0;
                    queue.add(new int[]{i,j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0];
            int col = curr[1];
            for (int i = 0; i < 4; i++) {
                int x = row + d[i][0];
                int y = col + d[i][1];
                if (isValid(matrix, h, w, x, y)) {
                    if (dist[x][y]>dist[row][col]+1) {
                        dist[x][y] = dist[row][col]+1;
                        queue.add(new int[]{x,y});
                    }
                }
            }
        }

        return dist;        
    }
    
    private boolean isValid(int[][] grid, int width, int height, int row, int col) {
        return (row >= 0) && (row < width) && (col >= 0) && (col < height);
    }    
}

Submission Detail

  • 48 / 48 test cases passed.
  • Runtime: 14 ms, faster than 64.69% of Java online submissions for 01 Matrix.
  • Memory Usage: 44 MB, less than 100.00% of Java online submissions for 01 Matrix.

ref