01 Matrix

Problem Statement

Given a binary matrix mat of dimensions m x n, the task is to compute a new matrix in which each cell contains the distance to the nearest cell with a value of 0. Each cell in the matrix can contain either a 0 or a 1. The 'distance' between any two directly adjacent cells is always 1. This means that for each cell located at (i,j) in the matrix, we seek the distance to the closest cell which contains 0, accounting only for vertical and horizontal movements between direct neighbors.

Examples

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

Constraints

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Approach and Intuition

To solve the problem, a clear understanding of the matrix structure and the movement constraints is necessary. Here’s a glimpse into how we can intuitively approach the problem:

1. Initialize the Result Matrix: Start with a result matrix where each cell's initial value is set to a large number (indicating a large distance) unless the cell itself contains 0.

2. Two-Pass Approach:

   • First Pass (Top-Left to Bottom-Right):

     • For each cell in the matrix (traversed from top-left to bottom-right), update the cell's value based on its top and left neighbors (if accessible). The update should consider the minimum distance from these neighbors if they've been processed plus one (since the distance between adjacent cells is 1).

   • Second Pass (Bottom-Right to Top-Left):

     • Traverse the matrix again but this time from bottom-right to top-left. Update each cell based on its right and bottom neighbors. This step ensures that we consider the shortest path coming from any direction.

3. Result Matrix Computation:

   • On completion of the two passes, the matrix will contain the shortest distance for each cell to the nearest cell containing 0.

This multi-pass method works efficiently as it gradually spreads the influence of each zero to its neighboring cells and through them, to the entire matrix. Each cell computes its distance based on previously computed distances of neighboring cells, ensuring that the minimal distances are calculated due to the consolidation of information from both passes. This results in an effective distribution of the known distances (zeros) through the matrix without the need for complex operations or additional storage structures like graphs or priority queues.

Solutions

class Solution {
public:
    vector<vector<int>> calculateDistanceMatrix(vector<vector<int>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> distanceMatrix;
            
        // Duplicate the matrix
        for (vector<int>& row: matrix) {
            distanceMatrix.emplace_back(row.begin(), row.end());
        }
            
        // Forward pass
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (distanceMatrix[i][j] == 0) {
                    continue;
                }
    
                int minAdj = rows * cols;
                if (i > 0) {
                    minAdj = min(minAdj, distanceMatrix[i - 1][j]);
                }
                    
                if (j > 0) {
                    minAdj = min(minAdj, distanceMatrix[i][j - 1]);
                }
                    
                distanceMatrix[i][j] = minAdj + 1;
            }
        }
            
        // Backward pass
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (distanceMatrix[i][j] == 0) {
                    continue;
                }
                    
                int minAdj = rows * cols;
                if (i < rows - 1) {
                    minAdj = min(minAdj, distanceMatrix[i + 1][j]);
                }
                    
                if (j < cols - 1) {
                    minAdj = min(minAdj, distanceMatrix[i][j + 1]);
                }
                    
                distanceMatrix[i][j] = min(distanceMatrix[i][j], minAdj + 1);
            }
        }
            
        return distanceMatrix;
    }
};