DEV Community

Cover image for 542. 01 Matrix
MD ARIFUL HAQUE
MD ARIFUL HAQUE

Posted on

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:

01-1-grid

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

Example 2:

01-2-grid

  • 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]]
?>
Enter fullscreen mode Exit fullscreen mode

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]
];
Enter fullscreen mode Exit fullscreen mode

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
        )
)
Enter fullscreen mode Exit fullscreen mode

Input 2:

$mat2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];
Enter fullscreen mode Exit fullscreen mode

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
        )
)
Enter fullscreen mode Exit fullscreen mode

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:

Imagine monitoring actually built for developers

Billboard image

Join Vercel, CrowdStrike, and thousands of other teams that trust Checkly to streamline monitor creation and configuration with Monitoring as Code.

Start Monitoring

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay