542. 01 Matrix

542. 01 Matrix

Difficulty: Medium

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

Solution:

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) { ... ... ... /** * go to ./solution.php */ } // 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.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub