[LeetCode] – Update Matrix Solution

25

In this problem, we are given a matrix consisting of 0s and 1s. The goal is to update matrix and compute the distance of each cell containing 1 to the nearest 0. The distance between two adjacent cells is considered to be 1.

The key challenge in this problem is efficiently determining the minimum distance for each cell while avoiding unnecessary computations.

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

Output:
[[0, 0, 0],
 [0, 1, 0],
 [1, 2, 1]]

Explanation:
Each cell containing 1 is replaced by its shortest distance to the nearest 0.

Brute Force Approach

A straightforward approach is to traverse the entire matrix for each cell containing 1, performing a breadth-first search (BFS) or depth-first search (DFS) to find the nearest 0. However, this results in high time complexity.

Steps:

1. Iterate over all the cells in the matrix.
2. For each cell with value 0, add it to a queue.
3. Until the queue is empty, pop a 0, and use BFS to find the distance to each 1
4. Store the minimum distance found.
5. Repeat this process for all 0s in the queue

Complexity Analysis:

Since each BFS/DFS runs independently for each 1 in the matrix, the worst-case time complexity is O(m * n * (m + n)), which is highly inefficient for large matrices.

This brute force method is impractical for large inputs, so we need a more optimized approach.

Optimized Approach

To efficiently compute the minimum distance, we can use Dynamic Programming (DP) with Two Passes. The idea is to use a bottom-up and top-down scan to propagate distances efficiently.

Steps:

1. Initialize a result matrix with maximum values (except for 0s, which remain 0).
2. First pass (Top-left to Bottom-right):
   • If the current cell is 1, update it by considering the minimum value from the top and left neighbors plus 1.
3. Second pass (Bottom-right to Top-left):
   • If the current cell is 1, update it by considering the minimum value from the bottom and right neighbors plus 1.
4. Return the updated result matrix.

Code:

  int[][] updateMatrix(int[][] mat) {
    int rows = mat.length;
    int cols = mat[0].length;
    int[][] result = new int[rows][cols];

    // Initialize the result matrix with maximum values
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        result[i][j] = Integer.MAX_VALUE;

    // First pass: top-left to bottom-right
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        if (mat[i][j] == 0) result[i][j] = 0;
        else {
          if (i > 0)
            result[i][j] = Math.min(result[i][j], result[i - 1][j] + 1);
          if (j > 0)
            result[i][j] = Math.min(result[i][j], result[i][j - 1] + 1);
        }

    // Second pass: bottom-right to top-left
    for (int i = rows - 1; i >= 0; i--)
      for (int j = cols - 1; j >= 0; j--)
        if (mat[i][j] != 0) {
          if (i < rows - 1)
            result[i][j] = Math.min(result[i][j], result[i + 1][j] + 1);
          if (j < cols - 1)
            result[i][j] = Math.min(result[i][j], result[i][j + 1] + 1);
        }

    return result;
  }Code language: Java (java)

Complexity Analysis:

• Time Complexity: O(m × n), since each cell is updated at most twice.
• Space Complexity: O(1) if modifying the input matrix in-place; otherwise, O(m × n) for an auxiliary matrix.

Video Explanation: