01 Matrix - Time Complexity: O(m*n) - JavaScript Solution

Given a matrix consists of 0 and 1, find the distance to the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

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

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

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

Note:

The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.

Understanding the Problem

The core challenge of this problem is to efficiently calculate the shortest distance from each cell to the nearest 0 in a matrix. This problem is significant in various applications such as image processing, pathfinding in grids, and more. A common pitfall is to use a naive approach that results in high time complexity, making it inefficient for larger matrices.

Approach

To solve this problem, we can use a Breadth-First Search (BFS) approach. The BFS algorithm is well-suited for finding the shortest path in an unweighted grid. Here's a step-by-step breakdown of the approach:

Naive Solution

A naive solution would involve iterating through each cell and performing a BFS or DFS to find the nearest 0. This approach is not optimal as it results in a time complexity of O((m*n)^2), which is inefficient for larger matrices.

Optimized Solution

An optimized solution involves initializing a queue with all the cells containing 0 and performing a multi-source BFS. This ensures that we calculate the shortest distance in a single pass. The time complexity of this approach is O(m*n), which is efficient for the given constraints.

Algorithm

Here is a step-by-step breakdown of the optimized BFS algorithm:

Initialize a queue and add all cells containing 0 to the queue.
Initialize a distance matrix with Infinity for all cells except those containing 0, which are set to 0.
Perform BFS from all 0 cells simultaneously, updating the distance for each cell based on its neighbors.
Continue the BFS until all cells have been processed.

Code Implementation

// JavaScript implementation of the optimized BFS approach
function updateMatrix(matrix) {
    const rows = matrix.length;
    const cols = matrix[0].length;
    const queue = [];
    const dist = Array.from({ length: rows }, () => Array(cols).fill(Infinity));

    // Initialize the queue with all 0 cells and set their distance to 0
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (matrix[r][c] === 0) {
                queue.push([r, c]);
                dist[r][c] = 0;
            }
        }
    }

    // Directions array for moving up, down, left, and right
    const directions = [
        [1, 0], [-1, 0], [0, 1], [0, -1]
    ];

    // Perform BFS
    while (queue.length > 0) {
        const [r, c] = queue.shift();

        for (const [dr, dc] of directions) {
            const newRow = r + dr;
            const newCol = c + dc;

            // Check if the new position is within bounds and if we found a shorter path
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
                if (dist[newRow][newCol] > dist[r][c] + 1) {
                    dist[newRow][newCol] = dist[r][c] + 1;
                    queue.push([newRow, newCol]);
                }
            }
        }
    }

    return dist;
}

// Example usage:
const matrix1 = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];
console.log(updateMatrix(matrix1));

const matrix2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];
console.log(updateMatrix(matrix2));

Complexity Analysis

The time complexity of the optimized BFS approach is O(m*n) because each cell is processed at most once. The space complexity is also O(m*n) due to the distance matrix and the queue used for BFS.

Edge Cases

Potential edge cases include:

All cells are 0.
All cells are 1 except one 0.
Large matrices with mixed 0s and 1s.

Each of these cases is handled by the BFS approach, ensuring correct distance calculations.

Testing

To test the solution comprehensively, consider the following test cases:

Simple matrices with a single 0.
Large matrices with multiple 0s and 1s.
Edge cases with all 0s or all 1s.

Using a testing framework like Jest or Mocha can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller, manageable parts.
Think about the most efficient data structures and algorithms for the task.
Practice similar problems to improve problem-solving skills.

Conclusion

Understanding and solving the 01 Matrix problem using BFS is crucial for efficient pathfinding in grids. The optimized approach ensures that we handle large matrices within acceptable time limits. Practice and exploration of similar problems can further enhance problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: