Example: 01 Matrix

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.

Solution

• init res matrix with maximum distance
• find all zeroes and set their distance to 0
• for each zero, do a bfs exploration updating distance of neighbors
  • if bigger than curr to curr distance + 1
  • (if dist is 0 or smaller we have a dist already)
  • (if it is bigger it was not assigned yet.)

class Solution {
    public int[][] updateMatrix(int[][] mat) {        
        int m = mat.length;
        int n = mat[0].length;
        int[][] result = new int[m][n];
        // Initialize the result matrix with maximum distance
        for (int i = 0; i < m; i++) {
            Arrays.fill (result[i], Integer.MAX_VALUE);
        }
        
        // Add all 0s to the queue and mark their distance as 0
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer (new int[]{i, j});
                    result[i][j] = 0;
                }
            }
        }
        
        // Define possible directions to move (up, down, left, right)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // perform bfs from each 0, update cell if new distance is smaller
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];

            // Explore neighbors
            for (int[] direction: directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];

                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                    // if old dist (already in cell) > cur + 1 (cur cell to closest 0)
                    if (result[newRow][newCol] > result[row][col] + 1) {
                        result[newRow][newCol] = result[row][col] + 1;
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }
        }

        return result;
    }
}