01 Matrix

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;
    }
};

The provided C++ code defines a solution for computing the distance of each cell in a binary matrix to the nearest zero. The function calculateDistanceMatrix takes a reference to a 2D vector of integers, which represents the input matrix, and returns a 2D vector with the computed distances.

• The function first determines the number of rows and columns in the input matrix and initializes an empty 2D vector called distanceMatrix that will eventually hold the calculated distances.
• Initially, the distanceMatrix is populated with the exact same values from the input matrix using a copy loop.
• The code then proceeds with a two-pass approach for computing the nearest distance:
  • The forward pass iterates the matrix from the top left to the bottom right. For each cell, if its value is not zero, it computes the minimum distance from the top and left neighbors (if they exist), and updates the current cell's value.
  • The backward pass iterates the matrix from the bottom right to the top left. Similar to the forward pass, this calculates the minimum distance from the bottom and right neighbors (if they exist), and updates the current cell's value taking the minimum between the current value and the newly computed distance.
• The approach effectively finds the shortest path to a zero for each cell by first considering top and left paths in the forward pass and right and bottom paths in the backward pass, ensuring that each cell's value is the minimum possible distance to a zero.

This method ensures efficient computation using a simple but powerful two-pass scanning technique, thereby optimizing both the performance and accuracy of the distance matrix calculation.

class Solution {
    public int[][] modifyDistance(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] result = new int[rows][cols];
        
        // Copy initial matrix values
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                result[r][c] = matrix[r][c];
            }
        } 

        // First pass: from top to bottom
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (result[r][c] == 0) continue;

                int minimal = rows * cols;
                if (r > 0) minimal = Math.min(minimal, result[r - 1][c]);
                if (c > 0) minimal = Math.min(minimal, result[r][c - 1]);
                
                result[r][c] = minimal + 1;
            }
        }
        
        // Second pass: from bottom to top
        for (int r = rows - 1; r >= 0; r--) {
            for (int c = cols - 1; c >= 0; c--) {
                if (result[r][c] == 0) continue;
                
                int minimal = rows * cols;
                if (r < rows - 1) minimal = Math.min(minimal, result[r + 1][c]);
                if (c < cols - 1) minimal = Math.min(minimal, result[r][c + 1]);
                
                result[r][c] = Math.min(result[r][c], minimal + 1);
            }
        }
        
        return result;
    }
}

The code provided is a Java implementation for the "01 Matrix" problem, where the goal is to convert a given matrix of 0s and 1s so that every cell contains the distance to the nearest 0. The solution proceeds with a two-pass algorithm on the matrix:

• Initialization step: A new result matrix is created with the same dimensions as the input matrix, and initial values are directly copied from the input matrix.

• First pass (top to bottom and left to right):

  • Traverse the matrix from the top-left to the bottom-right.
  • For each cell that is not 0, compute the minimal distance from the top or left (whichever is smaller) and update the result matrix to reflect this minimal distance plus one.

• Second pass (bottom to top and right to left):

  • Traverse the matrix from the bottom-right to the top-left.
  • For each cell, compute the minimal distance from the bottom or right (again, whichever is smaller).
  • Ensure that the current value reflects the smallest possible distance by comparing it with the existing value in the result matrix.

This method utilizes dynamic programming techniques to efficiently calculate minimum distances. Each matrix cell is updated based on previously computed values, which ensures that the solution runs in O(n*m) time where n and m are the number of rows and columns of the matrix, respectively.

This efficient approach prevents the need for a brute force solution where each cell would require a search to the nearest 0, substantially reducing computation time especially for large matrices.

class Solution:
    def transformMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        transformed_matrix = [row.copy() for row in matrix]
        rows, cols = len(transformed_matrix), len(transformed_matrix[0])

        for i in range(rows):
            for j in range(cols):
                minimum = inf
                if transformed_matrix[i][j] != 0:
                    if i > 0:
                        minimum = min(minimum, transformed_matrix[i - 1][j])
                    if j > 0:
                        minimum = min(minimum, transformed_matrix[i][j - 1])
                        
                    transformed_matrix[i][j] = minimum + 1
    
        for i in range(rows - 1, -1, -1):
            for j in range(cols - 1, -1, -1):
                minimum = inf
                if transformed_matrix[i][j] != 0:
                    if i < rows - 1:
                        minimum = min(minimum, transformed_matrix[i + 1][j])
                    if j < cols - 1:
                        minimum = min(minimum, transformed_matrix[i][j + 1])
                        
                    transformed_matrix[i][j] = min(transformed_matrix[i][j], minimum + 1)

        return transformed_matrix

The code provided is designed to modify a given matrix such that each entry in the matrix is replaced by the distance to the nearest zero. This task is executed in Python using a method named transformMatrix, which accepts a matrix as its parameter and returns a new matrix with the transformed values.

Here's a brief explanation of how the solution works:

• First, create a copy of the original matrix to keep track of transformations without altering the original matrix. Determine the number of rows and columns of the matrix.

• Traverse the matrix from the top-left corner to the bottom-right. For each cell that is not zero, calculate the minimum distance from a zero by looking leftwards and upwards. If there is a non-zero cell, update its value by adding one to the minimum value of reachable adjacent cells.

• Once the first pass is done from the top-left to the bottom-right, begin a second traversal from the bottom-right to the top-left. This time, for each non-zero cell, calculate the potential new minimum distances by looking rightwards and downwards towards previously updated cells.

• After both traversals, each cell in the matrix holds the minimum distance to the nearest zero.

Ensure to replace inf with float('inf') for a full Python implementation, and add appropriate imports such as from math import inf if using inf directly. This implementation leverages dynamic programming principles, updating the solution matrix in place for both passes to ensure optimal calculation of each cell's value.