01 Matrix medium

Problem Statement

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

The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

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,1,0],[1,1,1],[0,1,0]] Output: [[0,1,0],[1,2,1],[0,1,0]]

Steps and Explanation

This problem can be efficiently solved using Breadth-First Search (BFS). The core idea is to treat cells containing '0' as sources and perform a BFS to find the shortest distance to all other cells (containing '1').

1. Initialization: Create a copy of the input matrix dist to store the distances. Initialize dist with a large value (e.g., INT_MAX) for all cells containing '1'. Cells with '0' remain 0. Create a queue q and add the coordinates of all cells containing '0' to it.

2. BFS Traversal: While the queue q is not empty:

   • Dequeue a cell (row, col).
   • Explore its four neighboring cells: (row-1, col), (row+1, col), (row, col-1), (row, col+1).
   • For each neighbor:
     • If the neighbor is within the matrix bounds and its distance in dist is greater than the distance from the current cell plus 1, update the distance in dist and enqueue the neighbor.

3. Return Result: After the BFS completes, dist will contain the shortest distance to the nearest 0 for each cell.

Code (C++)

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // for numeric_limits

using namespace std;

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size();
    int n = mat[0].size();

    vector<vector<int>> dist(m, vector<int>(n, numeric_limits<int>::max()));
    queue<pair<int, int>> q;

    // Initialize queue and dist matrix for cells with 0
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (mat[i][j] == 0) {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }

    // BFS traversal
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i) {
            int nr = curr.first + dr[i];
            int nc = curr.second + dc[i];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[curr.first][curr.second] + 1) {
                dist[nr][nc] = dist[curr.first][curr.second] + 1;
                q.push({nr, nc});
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<int>> mat1 = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
    vector<vector<int>> result1 = updateMatrix(mat1);

    for (const auto& row : result1) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }

    return 0;
}

Complexity Analysis

• Time Complexity: O(M*N), where M and N are the dimensions of the matrix. BFS visits each cell at most once.
• Space Complexity: O(M*N) in the worst case, due to the queue and the dist matrix. In the best case (all 0s), the space complexity will be smaller.