algoadvance

Leetcode 542. 01 Matrix

Problem Statement

You are given an m x n binary matrix mat of 0s and 1s, where each cell represents either land (1) or water (0). You need to find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

You need to return a matrix ans of the same size as mat such that ans[i][j] is the distance to the nearest 0 for cell (i, j).

Example:

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

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

Clarifying Questions

  1. Can there be multiple 0s in the input matrix?
    • Yes, the matrix can contain multiple 0s.
  2. Can all cells in the matrix be 1s or 0s?
    • Yes, the matrix can be fully 0s or fully 1s.
  3. What is the maximum size of the matrix?
    • Typically the constraints might be around m, n <= 10^3 for an efficient solution.
  4. Should we consider diagonal distances?
    • No, only vertical and horizontal distances matter.

Strategy

Breadth-First Search (BFS)

  1. Initialization:
    • Create an output matrix ans initially filled with a large value (e.g., INT_MAX), except for cells with 0s in mat, which should have a value of 0.
    • Use a queue to perform BFS, starting with all 0 cells.
  2. BFS Execution:
    • For each cell with 0, push it into the queue.
    • For each cell in the queue, process its neighbors (up, down, left, right).
    • If a neighboring cell’s current recorded distance is greater than the distance from the current cell plus one, update it and push the neighbor into the queue.
  3. Result:
    • Once the BFS completes, ans will contain the shortest distances to the nearest 0.

Time Complexity

Code

Here is the C++ implementation for the problem using the explained strategy:

#include <vector>
#include <queue>
#include <climits> // For INT_MAX

using namespace std;

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size();
    int n = mat[0].size();
    
    vector<vector<int>> ans(m, vector<int>(n, INT_MAX));
    queue<pair<int, int>> q;
    
    // Initialize with all '0' cells
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            if(mat[i][j] == 0) {
                ans[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    
    // Directions for moving in the matrix (up, down, left, right)
    vector<pair<int, int>> directions = \{\{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    // BFS from all '0' cells
    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        for(const auto& dir : directions) {
            int newX = x + dir.first;
            int newY = y + dir.second;
            
            if(newX >= 0 && newY >= 0 && newX < m && newY < n) {
                if(ans[newX][newY] > ans[x][y] + 1) {
                    ans[newX][newY] = ans[x][y] + 1;
                    q.push({newX, newY});
                }
            }
        }
    }
    
    return ans;
}

This implementation ensures an efficient BFS approach, creating a matrix of shortest distances to the nearest 0 for each cell.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI