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.

It is guaranteed that there is at least one 0 in the binary matrix.

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 approach, known as multi-source BFS or multi-start BFS, is used when we have multiple sources from which we need to calculate the distance to all the cells (in this case, the sources are the 0 cells) and we need to calculate the shortest distance of all the non-zero cells from these sources.

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. Since all 0s start processing at the same time, distances to all 1s are updated optimally.

Here is a step-by-step approach to solve this problem:

1. Initialize a queue with all 0 cell coordinates and set 1s to Integer.MAX_VALUE.
2. Perform BFS from all 0s simultaneously:
   1. Dequeue a cell (r, c).
   2. Explore its four neighbors:
      1. If the neighbor’s value is greater than mat[r][c] + 1, update it and enqueue its coordinates.
3. Ensure propagation: Newly updated cells are reprocessed to guarantee the shortest distance is assigned. 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;
}

Significance of dirs Array

The dirs array in the above mentioned implementation is used to simplify movement in four possible directions: up, down, left, and right.

• dirs[i] represents the row change.
• dirs[i+1] represents the column change.

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.