542. 01 Matrix

[mah-shamim]

Topics: Array, Dynamic Programming, Breadth-First Search, Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two cells sharing a common edge is 1.

Example 1:

• Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
• Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

• Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
• Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Note: This question is the same as 1765. Map of Highest Peak

[mah-shamim]

We will use multi-source Breadth-First Search (BFS), where all the 0 cells are treated as starting points (sources). For every 1 cell, we calculate the minimum distance to the nearest 0.

Let's implement this solution in PHP: 542. 01 Matrix

<?php
/**
 * @param Integer[][] $mat
 * @return Integer[][]
 */
function updateMatrix($mat) {
    $rows = count($mat);
    $cols = count($mat[0]);
    $directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

    // Initialize distances with a large number for '1' cells
    $distance = array_fill(0, $rows, array_fill(0, $cols, PHP_INT_MAX));
    $queue = [];

    // Add all '0' cells to the queue and set their distance to 0
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if ($mat[$i][$j] === 0) {
                $distance[$i][$j] = 0;
                $queue[] = [$i, $j];
            }
        }
    }

    // BFS from all '0' cells
    while (!empty($queue)) {
        list($currentRow, $currentCol) = array_shift($queue);

        foreach ($directions as $direction) {
            $newRow = $currentRow + $direction[0];
            $newCol = $currentCol + $direction[1];

            // Check if the new cell is within bounds
            if ($newRow >= 0 && $newRow < $rows && $newCol >= 0 && $newCol < $cols) {
                // If a shorter distance is found, update it and enqueue the cell
                if ($distance[$newRow][$newCol] > $distance[$currentRow][$currentCol] + 1) {
                    $distance[$newRow][$newCol] = $distance[$currentRow][$currentCol] + 1;
                    $queue[] = [$newRow, $newCol];
                }
            }
        }
    }

    return $distance;
}

// Example usage:
$mat1 = [[0,0,0],[0,1,0],[0,0,0]];
$mat2 = [[0,0,0],[0,1,0],[1,1,1]];

echo updateMatrix($mat1) . "\n"; // Output: [[0,0,0],[0,1,0],[0,0,0]]
echo updateMatrix($mat2) . "\n"; // Output: [[0,0,0],[0,1,0],[1,2,1]]
?>

Explanation:

1. Initialization:

   • distance array is initialized with PHP_INT_MAX for all cells initially.
   • All 0 cells are set to 0 in the distance array and added to the BFS queue.

2. Multi-Source BFS:

   • Using a queue, we perform BFS from all 0 cells simultaneously.
   • For each cell in the queue, check its neighbors (up, down, left, right).
   • If the neighbor's distance can be reduced (distance[newRow][newCol] > currentDistance + 1), update its distance and enqueue it.

3. Output:

   • The distance array is updated with the minimum distances to the nearest 0 for all cells.

Input and Output:

Input 1:

$mat1 = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

Output 1:

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )
)

Input 2:

$mat2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];

Output 2:

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 1
        )
)

This solution is efficient with a time complexity of O(m × n), as each cell is processed once. The space complexity is also O(m × n) due to the distance array and the BFS queue.

[basharul-siddike]

Thanks for solving the problem of "01 Matrix"

[mah-shamim]

Thanks