542. 01 Matrix

542. 01 Matrix (Medium)

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 1:

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

Example 2:

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 <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Companies:
Amazon, Microsoft, Google, Uber, Apple

Related Topics:
Array, Dynamic Programming, Breadth-First Search, Matrix

Similar Questions:

• Shortest Path to Get Food (Medium)

Solution 1. BFS

// OJ: https://leetcode.com/problems/01-matrix/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), step = 1, dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        vector<vector<int>> ans(M, vector<int>(N, INT_MAX));
        queue<pair<int, int>> q;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) {
                    q.emplace(i, j);
                    ans[i][j] = 0;
                }
            }
        }
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto [x, y] = q.front();
                q.pop();
                for (auto &[dx, dy] : dirs) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || a >= M || b < 0 || b >= N || ans[a][b] != INT_MAX) continue;
                    q.emplace(a, b);
                    ans[a][b] = step;
                }
            }
            ++step;
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/01-matrix/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
        queue<pair<int, int>> q;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == 0) q.emplace(i, j);
                else A[i][j] = INT_MAX;
            }
        }
        while (q.size()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto &[dx, dy] : dirs) {
                int a = x + dx, b = y + dy;
                if (a < 0 || a >= M || b < 0 || b >= N || A[a][b] != INT_MAX) continue;
                q.emplace(a, b);
                A[a][b] = A[x][y] + 1;
            }
        }
        return A;
    }
};

Solution 2. DP

// OJ: https://leetcode.com/problems/01-matrix/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j]) A[i][j] = 0x3f3f3f3f;
            }
        }
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                A[i][j] = min({ A[i][j], i - 1 >= 0 ? A[i - 1][j] + 1 : INT_MAX, j - 1 >= 0 ? A[i][j - 1] + 1 : INT_MAX });
            }
        }
        for (int i = M - 1; i >= 0; --i) {
            for (int j = N - 1; j >= 0; --j) {
                A[i][j] = min({ A[i][j], i + 1 < M ? A[i + 1][j] + 1 : INT_MAX, j + 1 < N ? A[i][j + 1] + 1 : INT_MAX });
            }
        }
        return A;
    }
};