542.01-matrix.md

542. 01 Matrix

Hints

• What if you start BFS from every 1? Why is it inefficient?
• How can you use all 0s as starting points to propagate distances?
• How do you avoid revisiting or updating a cell unnecessarily?

BFS (Multi-source BFS)

• This is a classic multi-source BFS problem: all 0s are sources, and the shortest distance to a 0 for each 1 is found by expanding outward from all 0s simultaneously.
• BFS ensures that when a cell is first reached, it is via the shortest path from any 0.
• The distances array acts as both the result and the visited set: only update a cell's distance if you find a shorter path.
• This approach is much more efficient than running BFS/DFS from every 1 (which would be O((m*n)^2)).

Here are the steps:

• Enqueue all 0's and set their distances to 0.
• Pop cells from the queue and update the distance of adjacent cells if a shorter path is found.
• If the distance is updated, enqueue the adjacent cell for further exploration.

Super Source

我們先從簡化的題目開始，假設題目只有一個 0，那麼對於每個 1，我們只需要找到最短距離到那個唯一的 0 即可。

_ _ _ _   ==>   _ 1 _ _   ==>   2 1 2 _   ==>   2 1 2 3 
_ 0 _ _         1 0 1 _         1 0 1 2         1 0 1 2 
_ _ _ _         _ 1 _ _         2 1 2 _         2 1 2 3

在實際題目裡面 0 可能有多個，我們可以將剛剛唯一的 0 視為一個「超級源點」，起始距離為 -1，然後從這個超級源點開始擴散，會先擴散到原本題目裡面多個 0，這時候距離就會是 -1 + 1 = 0，然後再擴散四周。

    0 // super source, distance = -1
  / | \
[0, 0, ∞],
[∞, ∞, ∞],
[∞, ∞, 0]

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 (x, y) = queue.removeFirst()
        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)

Visited Set

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

The distances array acts as the visited set. We initialize distance[i][j] = oo to indicate it hasn't received any update from neighbors yet. Then the first time we update distance[newX][newY] as shortest distance, it's implicitly becomes "visited". Because we only process in increasing order of distance (BFS expands in a monotonic way), we never revisit a cell with a better distance.

Thus:

if (distances[newX][newY] > distances[x][y] + 1) {
    distances[newX][newY] = distances[x][y] + 1
    queue.addLast(newX to newY)
}

Is equivalent to:

// Not visited yet
if (distances[newX][newY] == oo) {
    // first visit, and mark as visited
}

Therefore, no need for a visited set, distances matrix serves that purpose.

How can you make sure that the visited index has already set the minimum distance? - by the order we push pairs of coordinates to the queue. It's guaranteed that those 0's will be visited first before those 1's. Therefore, it's guaranteed that once it's updated, its the minimum distance.

Dynamic Programming

The distance from the nearest 0 for each cell can be computed from 1 + min(left, top, right, bottom). And the distance to the nearest 0 for each cell is monotonic, it never decreases as you move away from the 0.

        top
         | 
left - cell - right
         |
      bottom

We can process the distance matrix in two sweeps to ensure that we propagate distance from all directions. We can process in two passes:

1. From top-left to bottom-right: look at the top and left neighbors.
2. From bottom-right to top-left: look at the bottom and right neighbors.

         top
          |
          v 
left -> cell  +  cell <- right
                   ^
                   |
                bottom

As long as we initialize:

• distance[i][j] = 0 for all 0s.
• distance[i][j] = Int.MAX_VALUE / 2 for all 1s. (We use Int.MAX_VALUE / 2 to avoid overflow when adding 1.)

And perform proper relaxation, the correct shortest distance will be propagated to all cells.

fun updateMatrix(mat: Array<IntArray>): Array<IntArray> {
    val m = mat.size
    val n = mat[0].size
    val distances = Array<IntArray>(m) { IntArray(n) { Int.MAX_VALUE / 2 } }
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (mat[i][j] == 0) {
                distances[i][j] = 0
            } else {
                if (i > 0) distances[i][j] = minOf(distances[i][j], distances[i - 1][j] + 1)
                if (j > 0) distances[i][j] = minOf(distances[i][j], distances[i][j - 1] + 1)
            }
        }
    }

    for (i in m - 1 downTo 0) {
        for (j in n - 1 downTo 0) {
            if (mat[i][j] == 0) {
                distances[i][j] = 0
            } else {
                if (i < m - 1) distances[i][j] = minOf(distances[i][j], distances[i + 1][j] + 1)
                if (j < n - 1) distances[i][j] = minOf(distances[i][j], distances[i][j + 1] + 1)
            }
        }
    }
    return distances
}

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

Edge Cases

• All cells are 0: output is all 0.
• All cells are 1 except for a single 0: distances increase with Manhattan distance from the 0.
• Matrix is a single row or column.
• Large matrix with 0s only at the corners.