01 Matrix

Problem Statement

LeetCode-542: Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Approach

As is the case with most of the matrix and nearest neighbor problems, we can use a BFS traversal to solve this problem. The idea is to start from all the 0 cells and traverse the matrix in all four directions.

The BFS algorithm works for this problem because the distance of a cell from the nearest 0 cell is the minimum distance of the adjacent cells (which were also calculated this way) plus one. Here is a step-by-step approach to solve this problem:

1. Initialize a queue to store the row, col coordinates of the 0 cells.
2. Traverse the matrix and:
   1. If the current cell is 0, add its coordinates to the queue.
   2. Else set the value of the current cell to Integer.MAX_VALUE.
3. Once done, all the zero will be in the queue and the rest of the cells will have Integer.MAX_VALUE - ready for BFS traversal.
4. While the queue is not empty:
   1. Pop the front element from the queue.
   2. Traverse the four directions and:
      1. If the cell is within the bounds of the matrix and the value of the current cell is greater than the value of the adjacent cell plus one:
         1. Update the value of the current cell to the value of the adjacent cell plus one.
         2. And add the coordinates of the current cell to the queue.
      2. Else, continue to the next cell.

In point 4.2.1.2, it is important to add the coordinates of the current cell to the queue. This is because the value of the current cell might be updated in the future(via some other path) and we need to traverse the adjacent cells again to update their values.

Implementation

Here is a Java implementation of the above approach:

public int[][] updateMatrix(int[][] mat) {
    Queue<int[]> queue = new LinkedList<>();
    int rows = mat.length;
    int cols = mat[0].length;

    // prepare the queue for BFS and set the 
    // rest of the cells to Integer.MAX_VALUE
    for(int i=0; i < rows; i++){
        for(int j=0; j < cols; j++){
            if(mat[i][j] == 0){
                queue.add(new int[]{i,j});
            }else{
                mat[i][j] = Integer.MAX_VALUE;
            }
        }
    }

    int[] dirs = new int[]{0,1,0,-1,0};
    
    while(!queue.isEmpty()){
        int[] entry = queue.remove();
        int r = entry[0];
        int c = entry[1];

        // traverse the four directions
        for(int i=0; i < 4; i++){
            int newRow = r + dirs[i];
            int newCol = c + dirs[i+1];
            // if the cell is within the bounds of the matrix
            if(isValid(newRow, newCol, mat)){
                // if the value of the current cell is greater 
                // than the value of the adjacent cell plus one
                if(mat[newRow][newCol] > mat[r][c]+1){
                    mat[newRow][newCol] = mat[r][c]+1;

                    // so that these coordinates can be traversed again
                    // to calculate higher order neighbors
                    queue.add(new int[]{newRow, newCol});
                }
            }
        }
    }
    return mat;
}
private boolean isValid(int r, int c, int[][] mat){
    return r >= 0 && r < mat.length && c >= 0 && c < mat[0].length;
}

Complexity Analysis

The time complexity for this approach is $O(m \times n)$ where m is the number of rows and n is the number of columns in the matrix. This is because we are traversing the matrix once and performing a constant number of operations for each cell.

The space complexity is also $O(m \times n)$ as we are using a queue to store the coordinates of the 0 cells.