01 Matrix - Leetcode Solution

Problem Statement: Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1: Input: 0 0 0 0 1 0 0 0 0

Output: 0 0 0 0 1 0 0 0 0

Example 2: Input: 0 0 0 0 1 0 1 1 1

Output: 0 0 0 0 1 0 1 2 1

Approach: The given problem can be solved in multiple ways. The approach that we will be discussing is a BFS-based approach.

Breadth-First Search (BFS): BFS is a graph traversal algorithm that traverses all the vertices of a graph in layers. Starting from the source, the BFS algorithm visits all its neighbors at a current depth before moving to its next depth vertices.

Algorithm:

1. Initialize a result matrix with all values set to infinity.
2. Initialize a queue.
3. Traverse the matrix and enqueue all the coordinates having value 0. Set the corresponding result matrix cell to 0.
4. Start a BFS traversal using the coordinates added to the queue.
5. In each iteration, dequeue the front element of the queue.
6. Traverse all the neighbors of the current coordinate. If a neighbor is not visited and its distance is not already set, set its distance in the result matrix to its distance from the current coordinate + 1.
7. Add the newly discovered neighbors to the queue.
8. Repeat steps 5 to 7 until the queue is empty.
9. Return the result matrix.

Let's see the implementation of the above algorithm:

class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<vector<int>> result(m, vector<int>(n, INT_MAX));

    queue<pair<int, int>> q;

    // Adding all the coordinates having value 0 to the queue
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(matrix[i][j] == 0){
                q.push({i, j});
                result[i][j] = 0;
            }
        }
    }

    // BFS Traversal
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop();

        // Traversing all the neighbors of the current coordinate
        if(x > 0 && result[x-1][y] > result[x][y]+1){
            result[x-1][y] = result[x][y]+1;
            q.push({x-1, y});
        }

        if(x < m-1 && result[x+1][y] > result[x][y]+1){
            result[x+1][y] = result[x][y]+1;
            q.push({x+1, y});
        }

        if(y > 0 && result[x][y-1] > result[x][y]+1){
            result[x][y-1] = result[x][y]+1;
            q.push({x, y-1});
        }

        if(y < n-1 && result[x][y+1] > result[x][y]+1){
            result[x][y+1] = result[x][y]+1;
            q.push({x, y+1});
        }
    }

    return result;
}

};

Time Complexity: The time complexity of the above approach is O(m*n) where m and n are the number of rows and columns respectively.

Space Complexity: The space complexity of the above approach is also O(m*n) where m and n are the number of rows and columns respectively.

1