DAY 34 - 0/1 Matrix

Hey everyone! Welcome back to another day of problem-solving. It's day 34, and I'm still going strong on my quest for consistency. Today, we have an interesting problem to tackle. But before we dive in, let's make sure we're all on the same page.

Incase you are unfamiliar with graphs I suggest reading the previous article 32 && 33. It also contains the links to valuable resources.

Question:

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

The distance between two adjacent cells is 1.

Note: The matrix consists of only 0's and 1's.

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]]

Intuition:

• Let's start by breaking down the question first and then approaching a possible solution.
• The quest wants us to find the nearest 0 from every cell.
• We know that nearest distance of 0 from a cell that is 0 will be zero. Obviously.
• Let's build on this approach more.
• Suppose we want to go from (0,1) to (1,1) in example 1.
• The distance is 1. It would be same if we wanted to go from (1,1) to (0,1). Distance to nearest won't change.
• How about we use the DFS approach which traverses the next level.
• The next nearest distance and checks again and adds distance by 1.
• From every 0 if we check it's neighbors and update accordingly we will be able to follow a process that get's our result.

Read algorithm and code for better understanding.

Algorithm:

1. Obtain the dimensions of the matrix, storing the number of rows in the variable m and the number of columns in the variable n.
2. Create a result matrix, result, of size m x n, initialized with zeros.
3. Create a visited matrix, vis, of size m x n, initialized with zeros, to keep track of visited cells.
4. Create a queue of pairs, where each pair represents the coordinates of a cell and its corresponding distance from a 0.
5. Define two arrays, rowTraverse and colTraverse, to represent the four possible directions: up, right, down, and left.
6. Iterate through the matrix, mat, to find all cells containing 0s. For each cell found, enqueue its coordinates and set the corresponding vis value to 1.
7. While the queue is not empty, perform the following steps:
8. Dequeue a cell from the front of the queue, obtaining its row, column, and distance.
9. Update the distance in the result matrix at the current coordinates.
10. Explore the four adjacent cells (up, right, down, and left) of the dequeued cell:
11. Calculate the coordinates of the adjacent cell using rowTraverse and colTraverse.
12. Check if the adjacent cell is within the matrix boundaries and has not been visited.
13. If the conditions are met, update the vis value to 1, enqueue the adjacent cell's coordinates, and set its distance to the current distance plus one.
14. Once the BFS traversal is complete, return the resulting matrix, result.

Code:

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> result(m , vector<int> (n,0));
        vector<vector<int>> vis(m , vector<int> (n,0));
        queue<pair<pair<int,int>,int>> q;
        int rowTraverse[] = {-1,0,1,0};
        int colTraverse[] = {0,1,0,-1};
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(mat[i][j] == 0){
                    q.push({{i,j},0});
                    vis[i][j] = 1;
                }
            }
        }

        while(!q.empty()){
            int row = q.front().first.first;
            int col = q.front().first.second;
            int dist = q.front().second;
            q.pop();
            result[row][col] = dist;
            for(int i = 0; i < 4; i++){
                int nextRow = row + rowTraverse[i];
                int nextCol = col + colTraverse[i];
                if(nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && 
                vis[nextRow][nextCol] == 0){
                    vis[nextRow][nextCol] = 1;
                    q.push({{nextRow,nextCol},dist + 1});
                }
            }

    }
    return result;
    }
};

Complexity Analysis:

• Time COmplexity: O(M*N)
• Space COmplexity: O(M*N)

Thanks for reading. Feedback is highly appreciated.