C++: 01 Matrix

Thought Process

To solve this problem, we use a Breadth-First Search (BFS) approach. We start by initializing a queue with all cells containing 0, as these are the starting points. Hence, cells with 0 are pushed into the queue while cells with 1 are flagged as -1 to indicate they are unprocessed. During BFS, we explore each cell's four neighbors (up, down, left, right). If a neighbor is -1, we update its value to the cell's value + 1 and add it to the queue. This process continues until the queue is empty. 

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        
        int row = mat.size();
        int col = mat[0].size();
        queue<pair<int,int>> qu;

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(mat[i][j]!=0){
                    mat[i][j]=-1; // Flaged
                }else{
                    qu.push(make_pair(i,j));
                }
            }
        }
        
        // Good way to iterate in all 4 direction
        int xDir[4]={1,-1,0,0};
        int yDir[4]={0,0,1,-1};
        while(!qu.empty()){

            pair<int,int> p1 = qu.front();  qu.pop();
            int x = p1.first;
            int y = p1.second;

            for(int i=0;i<4;i++){

                int x1 = x+xDir[i];
                int y1 = y+yDir[i];

                // If out of bound OR already visited
                if(x1>=mat.size() || y1>=mat[0].size() || x<0 || y<0 || mat[x1][y1]!=-1)
                    continue;
                else{
                    mat[x1][y1] = mat[x][y]+1;
                    qu.push(make_pair(x1,y1));
                }
            } 
        }
        return mat;
    }
};

Code Complexity

Time Complexity: O(n * m)

The algorithm processes each cell in the matrix once, making the time complexity
O(n * m), where 'n' is the number of rows and 'm' is the number of columns.

Space Complexity: O(n * m)

The space complexity is determined by the queue used for BFS, which can store up to O(n * m) cells in the worst case.

Code copied!