01 Matrix - C++ Solution and Time Complexity Analysis

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 compute the shortest distance from each cell to the nearest cell containing a 0. 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 impractical for larger matrices.

Approach

To solve this problem, we can use a multi-source Breadth-First Search (BFS) approach. The idea is to start from all the cells containing 0 and then propagate the distance to their neighboring cells. This ensures that each cell is visited in the shortest path order.

Naive Solution

A naive solution would involve iterating over 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), where m and n are the dimensions of the matrix.

Optimized Solution

The optimized solution involves using a queue to perform a BFS starting from all 0 cells simultaneously. This ensures that we compute the shortest distance in a single pass.

Algorithm

Initialize a queue and push all cells containing 0 into the queue. Set their distance to 0.
For all other cells, set their distance to infinity (or a large number).
While the queue is not empty, pop a cell from the queue and update the distance of its neighboring cells if a shorter path is found.
Push the updated neighboring cells into the queue.
Continue this process until the queue is empty.

Code Implementation

#include <vector>
#include <queue>
#include <utility>
#include <climits>

using namespace std;

vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    queue<pair<int, int>> q;
    vector<vector<int>> dist(m, vector<int>(n, INT_MAX));

    // Initialize the queue with all 0 cells
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 0) {
                q.push({i, j});
                dist[i][j] = 0;
            }
        }
    }

    // Directions for moving in the matrix
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // BFS from all 0 cells
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();

        for (auto [dx, dy] : directions) {
            int newX = x + dx;
            int newY = y + dy;

            // Check if the new cell is within bounds and can be updated
            if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                if (dist[newX][newY] > dist[x][y] + 1) {
                    dist[newX][newY] = dist[x][y] + 1;
                    q.push({newX, newY});
                }
            }
        }
    }

    return dist;
}

Complexity Analysis

The time complexity of the optimized solution 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.

Edge Cases

Potential edge cases include:

A matrix with all 0s.
A matrix with all 1s except one 0.
Single row or single column matrices.

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 cases with small matrices.
Large matrices with random distributions of 0s and 1s.
Edge cases as mentioned above.

Using a testing framework like Google Test 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 parts.
Think about the most efficient way to propagate information (e.g., BFS for shortest paths).
Consider edge cases and how your algorithm handles them.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed the problem of finding the distance to the nearest 0 in a binary matrix. We explored a naive solution and an optimized BFS-based solution. We also analyzed the complexity and discussed edge cases and testing strategies. Understanding and solving such problems is crucial for improving algorithmic thinking and problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: