Simple C++ O(2*n) Time, O(1) Extra Space Solution


  • 0
    F
    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            vector<vector<int>> result(matrix.size(), vector<int>(matrix.back().size()));
            for (int i = 0; i < matrix.size(); ++ i)
                for (int j = 0; j < matrix.back().size(); ++ j)
                {
                    if (matrix[i][j] == 0)
                        continue;
                    int dist = INT_MAX>>1;
                    if (j - 1 >= 0)
                        dist = min(dist, result[i][j - 1] + 1);
                    if (i - 1 >= 0)
                        dist = min(dist, result[i - 1][j] + 1);    
                    result[i][j] = dist;
                }
            for (int i = matrix.size() - 1; i >= 0 ; -- i)
                for (int j = matrix.back().size() - 1; j >= 0 ; -- j)
                {
                    if (matrix[i][j] == 0)
                        continue;
                    int dist = INT_MAX>>1;
                    if (j + 1 < matrix.back().size())
                        dist = min(dist, result[i][j + 1] + 1);
                    if (i + 1 < matrix.size())
                        dist = min(dist, result[i + 1][j] + 1);    
                    result[i][j] = min(dist, result[i][j]);
                }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.