542.01-matrix.md

542. 01 Matrix

Clarification Questions

• Is there at least one 0's in the matrix?

Test Cases

Edge / Corner Cases

• There are some 1 with different distances to the nearest 0's.

Input: 
0 0 0
0 1 1

Output: 
0 0 0
0 1 2

• All are 0's.

BFS

To find the shortest distance, we can use BFS. But if we search for 0's for every 1, it leads TLE (TC is O((m * n)^2)). Alteratively, we start the shorest distance calcluation from all 0's. The distance from 0's to itself is 0's, and we can propagate the distance to all other cells.

We start a BFS from every 0's, by enqueuing all 0's initially, we ensure that the BFS will propagate the shortest distance to all other cells. For each cell popped out from the queue, we check the adjacent cells (not out-of-bound) if we can relax the distance, and enqueue the cell if the distance is updated for further exploration.

Here are the steps:

• Enqueue all 0's and update the cells to 0's.
• We keep popping out the cells from queue and update the distance of the adjacent cell if the distance is shorter.
• If the distance is updated, then enqueue the adjacency cell to queue.

Why don't we need to check if the cell is visited?

1. The distances array acts as the visited set. Since we only update distance[newX][newY] if we find a shorter path, we are guaranteed to visite each cell at more once. A cell is "visited" once its shortest distance is determined.
2. BFS expands in a monotonic way, each cell is processed only when its shortest distance is known. This ensure we never revisit a cell with a longer path, avoiding redundant visit.

fun updateMatrix(mat: Array<IntArray>): Array<IntArray> {
    val m = mat.size
    val n = mat[0].size
    val distances = Array(m) { IntArray(n) { Int.MAX_VALUE } }

    val queue = ArrayDeque<Pair<Int, Int>>()
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (mat[i][j] == 0) {
                queue.addLast(i to j)
                distances[i][j] = 0 
            }
        }
    }

    while (queue.isNotEmpty()) {
        val position = queue.removeFirst()
        val x = position.first
        val y = position.second
        directions.forEach { d -> 
            val newX = x + d[0]
            val newY = y + d[1]
            if (newX in 0 until m && newY in 0 until n) {
                // Here we do relaxation, and enqueue the node if we can relax.
                if (distances[newX][newY] > distances[x][y] + 1) {
                    distances[newX][newY] = distances[x][y] + 1
                    queue.addLast(newX to newY)
                }
            }
        }
    }
    return distances
}

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