algoadvance

Leetcode 542. 01 Matrix

Problem Statement

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.

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

Constraints:

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

Clarifying Questions

1. What type of distance metric is used in this problem?
   • The Manhattan distance is used where distance between two adjacent cells is 1.
2. Would there be any invalid entries in the matrix that we need to handle?
   • No, all entries are either 0 or 1.

Strategy

To solve this problem efficiently, given the constraints, we can employ a Breadth-First Search (BFS) approach:

1. Initialize a queue and enqueue all positions of 0s in the matrix as starting points, as the distance to themselves is 0.
2. All cells initialized with 1 should have their distances set to a value indicating infinity (Integer.MAX_VALUE), as they will be updated with the minimum distance during the BFS traversal.
3. Process each cell in the queue, and for each dequeued cell, check its neighbors (up, down, left, right). If any neighbor has a distance greater than the current cell’s distance plus one, update the neighbor’s distance and enqueue it for processing.

This approach ensures that all cells are processed in the shortest path manner due to the BFS traversal properties.

Code

import java.util.*;

public class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int rows = mat.length;
        int cols = mat[0].length;
        int[][] distances = new int[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        
        // Initialize distances and queue
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (mat[i][j] == 0) {
                    distances[i][j] = 0;
                    queue.offer(new int[]{i, j});
                } else {
                    distances[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        // Directions array for movement (down, up, right, left)
        int[][] directions = \ use example from above
        
        // BFS Traversal
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];
            
            for (int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                    if (distances[newRow][newCol] > distances[row][col] + 1) {
                        distances[newRow][newCol] = distances[row][col] + 1;
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }
        }
        
        return distances;
    }
}

Time Complexity

• Time Complexity: O(m * n) — Each cell is processed in constant time, i.e., added and processed in the queue at most once.
• Space Complexity: O(m * n) — Using a queue to store cell positions and a distance matrix holding distances for each cell.

This method efficiently processes the matrix and computes the required distances utilizing the BFS traversal technique.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?