6.9 Distance of Nearest Cell Having 1

6.9.1 Problem Metadata

6.9.2 Description

Given a binary matrix, for every cell compute the distance to the nearest cell containing 1.

6.9.3 Solution - Multi-source BFS

6.9.3.1 Walkthrough

Enqueue all cells containing 1 with distance 0 and run BFS to fill distances for zeros. Each expansion relaxes the first time a cell is reached, guaranteeing the shortest distance.

6.9.3.2 Analysis

  • Time Complexity: O(m * n)
  • Space Complexity: O(m * n)

6.9.3.3 Code - Java

public int[][] nearestOne(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) {
        Arrays.fill(row, -1);
    }
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 1) {
                dist[i][j] = 0;
                queue.offer(new int[]{i, j});
            }
        }
    }
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : dirs) {
            int nr = cell[0] + d[0];
            int nc = cell[1] + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{nr, nc});
            }
        }
    }
    return dist;
}