Start learning free

LESSON 339 OF 348 · GRAPHS

01 Matrix in Kotlin: Multi-Source BFS for Nearest Zero

Practice O(n * m) Read the full explanation

Given a matrix consists of 0 and 1, find the distance to the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1: 

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2: 

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

 

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.
STEP 1 OF 15
    Ctrl + Enter to check

    KOTLIN · GRAPHS

    01 Matrix in Kotlin, explained

    Problem overview

    The function computeGrid receives grid, an Array<IntArray> containing only 0 and 1, and must return a grid of the same shape in which each cell holds its distance to the nearest 0. Distance counts steps between adjacent cells, moving up, down, left or right. The grid always has at least one 0, and at most 10,000 cells.

    For this input:

    0 0 0
0 1 0
1 1 1

    the answer is:

    0 0 0
0 1 0
1 2 1

    Every zero stays 0. The middle cell is one step from the zero above it. The bottom row's corners are one step from the zeros above them, and the bottom middle cell has to go two steps.

    Approach: start the search from every zero at once

    The obvious plan is to run a search from every 1 to find its closest zero. That repeats a lot of work. Flip the question around: instead of asking each cell where the nearest zero is, grow outward from the zeros.

    Put every zero in a queue at distance 0 and run a breadth-first search (BFS). The search handles cells in rings: first the zeros, then every cell one step from a zero, then every cell two steps away, and so on. This is called a multi-source BFS. The first time the search reaches a cell, it comes from the closest zero, so that distance is final.

    The grid itself can store the progress. Before the search, every 1 is overwritten with -1, meaning "not reached yet". Distances are never negative, so there is no confusion with a real answer. When the search reaches a -1 neighbour, it writes the current cell's distance plus one into it and queues it. A cell that's no longer -1 has already been handled, which is why each cell enters the queue exactly once.

    Step by step

    1. Create the queue. An ArrayDeque of IntArray pairs, named que, will hold cell coordinates as [row, column]. Adding goes to the back and removeFirst removes from the front.
    2. Store the dimensions. n is the number of rows, grid.size, and m is the number of columns, grid[0].size. Both are properties, with no parentheses.
    3. Loop over the rows with i, and inside it loop over the columns with j, so that every cell is classified.
    4. Queue each zero. A zero is at distance 0 from itself, so it is a starting point of the search and stays as it is in the grid.
    5. Mark each other cell as unreached by setting it to -1.
    6. Define the four directions as offsets for up, down, left and right. Each changes only one coordinate, so diagonals are excluded.
    7. Loop while the queue is not empty. Cells leave the queue in order of growing distance.
    8. Take the front cell and unpack it into x1 and y1. Taking from the back would make the search depth-first and the distances would be wrong.
    9. Visit its four neighbours, one offset d at a time.
    10. Compute the neighbour's coordinates x2 and y2. They may lie outside the grid.
    11. Test bounds and status. The neighbour must be inside the grid and still hold -1.
    12. Set its distance to the current cell's distance plus one, and put it in the queue so that its own neighbours are processed later.
    13. Return grid, which now holds the answers.

    The solution in Kotlin

    class Solution {
    fun computeGrid(grid: Array<IntArray>): Array<IntArray> {
        val que = ArrayDeque<IntArray>()
        val n = grid.size
        val m = grid[0].size
        for (i in 0 until n) {
            for (j in 0 until m) {
                if (grid[i][j] == 0) {
                    que.add(intArrayOf(i, j))
                } else {
                    grid[i][j] = -1
                }
            }
        }

        val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
        while (que.isNotEmpty()) {
            val front = que.removeFirst()
            val x1 = front[0]
            val y1 = front[1]
            for (d in directions) {
                val x2 = x1 + d[0]
                val y2 = y1 + d[1]
                if (x2 in 0 until n && y2 in 0 until m && grid[x2][y2] == -1) {
                    grid[x2][y2] = grid[x1][y1] + 1
                    que.add(intArrayOf(x2, y2))
                }
            }
        }

        return grid
    }
}

    The Kotlin details worth a closer look:

    • x2 in 0 until n is a range test: it means 0 <= x2 && x2 < n, because until excludes the end. Using 0..n would accept n, which is one past the last row.
    • Short-circuit &&. grid[x2][y2] is read only after both range tests pass, so a neighbour beyond the edge never triggers an ArrayIndexOutOfBoundsException.
    • Pairs as IntArray. intArrayOf(i, j) is a simple coordinate pair read back with front[0] and front[1]. A queue of IntArray is a queue of references to those small arrays.
    • In-place update. The function modifies the grid it receives and returns that same array, not a copy. The caller's original is overwritten.
    • val inside loops. front, x1, x2 and the others are declared with val, so each iteration gets fresh read-only values. Only the grid's cells change.
    • for (d in directions) loops straight over the elements, so no index is needed.

    Complexity

    Time: O(n * m). The setup scan visits every cell once. In the search, each cell is queued once, because it's marked the moment it's queued, and each queued cell checks four neighbours.

    Space: O(n * m) in the worst case for the queue, for example when the grid is mostly zeros and all of them start in the queue. The distances reuse the input grid, so no second matrix is needed.

    Edge cases and common mistakes

    • All zeros. The grid comes back unchanged, because no 1 is ever converted.
    • A single zero. For a 3 by 3 grid of ones with one zero in a corner, the farthest corner gets 4: the result is rows 4 3 2, 3 2 1 and 2 1 0 when the zero is at the bottom right.
    • One row or one column. The row 0 1 1 1 1 gives 0 1 2 3 4, and the column holding 1, 1, 0, 1 gives 2, 1, 0, 1 from top to bottom.
    • Starting from the ones. A search from each 1 repeats work across cells. Starting from the zeros handles all the cells in one pass.
    • Using a stack. Taking from the back of the queue gives depth-first order, and distances are no longer shortest.
    • Leaving cells at 1. If ones are not replaced by -1, the code can't tell an unvisited 1 from a distance of 1.
    • Marking too late. Setting the distance when a cell is taken from the queue, not when it is added, would let it be queued several times.

    Testing

    • A 3 by 3 grid with a single 1 in the centre, surrounded by zeros, comes back unchanged.
    • Rows 0 0 0, 0 1 0, 1 1 1 give rows 0 0 0, 0 1 0, 1 2 1.
    • Rows 1 1 1, 1 1 1, 1 1 0 give rows 4 3 2, 3 2 1, 2 1 0.
    • The single cell 0 gives 0.
    • The row 0 1 1 1 1 gives 0 1 2 3 4.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free