Distance of nearest cell having 1 in a binary matrix

The problem, simply

You get a grid of 0s and 1s with m rows and n columns. For every cell, find the distance to the nearest cell that holds a 1. One step moves up, down, left or right. A cell that holds a 1 has distance 0.

Give back a grid of the same size with these distances. You can assume the grid has at least one 1.

A story to remember it

Picture it

Examples

Way 1: the simple way

There are no walls in this grid, so the shortest number of steps between two cells is "rows apart plus columns apart". For every cell, check every 1 and keep the smallest such distance.

1. For each cell (r, c), walk the whole grid again.
2. For every 1 at (r1, c1), compute |r - r1| + |c - c1| and keep the minimum.

class Solution {
    public int[][] nearest(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int best = Integer.MAX_VALUE;
                for (int r1 = 0; r1 < m; r1++) {          // check every 1
                    for (int c1 = 0; c1 < n; c1++) {
                        if (grid[r1][c1] == 1) {
                            best = Math.min(best, Math.abs(r - r1) + Math.abs(c - c1));
                        }
                    }
                }
                dist[r][c] = best;
            }
        }
        return dist;
    }
}

How long it takes: each of the m * n cells walks all m * n cells again, O((m*n)^2). Extra room: O(1) besides the answer.

Way 2: the clever way

Start the ripples from all the 1s at once. This is breadth first search with many starting points.

1. Make a dist grid. Every 1 gets 0 and joins the queue. Every 0 is marked "unknown".
2. While the queue is not empty, take the cell at the front.
3. Look at its 4 neighbors. Each unknown neighbor gets dist = this cell's dist + 1 and joins the back of the queue.
4. A cell gets its number the first time any ripple reaches it, and that first ripple is always from the nearest 1.

The queue holds all distance 0 cells first, then all distance 1 cells, then all distance 2 cells. That order is what makes the first visit the shortest.

class Solution {
    public int[][] nearest(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        Deque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    dist[r][c] = 0;
                    queue.add(new int[]{r, c});     // every pebble starts at once
                } else {
                    dist[r][c] = -1;                // unknown for now
                }
            }
        }
        int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] mv : moves) {
                int r = cell[0] + mv[0], c = cell[1] + mv[1];
                if (r < 0 || c < 0 || r >= m || c >= n || dist[r][c] != -1) continue;
                dist[r][c] = dist[cell[0]][cell[1]] + 1;   // first ripple to arrive
                queue.add(new int[]{r, c});
            }
        }
        return dist;
    }
}

How long it takes: each cell joins the queue once and checks 4 neighbors, O(m*n). Extra room: the queue and the dist grid, O(m*n).

Watch out for

• Set a cell's distance when it joins the queue, not when it leaves. Otherwise the same cell can join many times.
• Mark unknown cells with -1 (or a separate visited grid). Using 0 as "unknown" mixes them up with the real 0s.
• Use a queue, not a stack. A stack explores deep first and can give a cell a longer distance before the short one arrives.
• If the grid can have no 1 at all, every distance stays -1. Ask what to return.

What interviewers ask next

• Can you do it without a queue? Yes, with two sweeps. First go top left to bottom right using the top and left neighbors, then bottom right to top left using the bottom and right neighbors. Each cell keeps the smaller value. That is O(m*n) time and O(1) extra room.
• Distance to the nearest 0 instead (LeetCode 542, "01 Matrix"). Same code with 0 and 1 swapped.
• Rotting oranges. Same multi-start search; the answer is the largest distance, or -1 if some fresh orange is never reached.
• What if some cells are walls? Then rows apart plus columns apart is wrong, but the queue method still works if it skips walls.
• What if moves have different costs? Then a plain queue is not enough. Use Dijkstra with a priority queue, or a deque for costs of 0 and 1.

Remember this

Grown-up words: the pebbles are sources, the ripples are breadth first search levels, starting from all pebbles together is multi-source BFS, the waiting line is a queue, and rows apart plus columns apart is the Manhattan distance.