[C++] concise code + description, O(n)-time and space


  • 0

    Tip: BFS can compute shortest paths when steps are not weighted differently.

    Idea: Set all non-zero elements to -1 and enqueue indices of all zero elements (red circles in the figure depicted below) in a queue. Level by level update distances and enqueue cells. If a cell is already updated (has a value other than -1), it means that it is closer to another zero-cell and its distance has already been calculated. Our current distance calculation for such cells is for sure greater than or equal to their already calculated values. So we stop and we don't enqueue such cells' indices into our queue.

    As each cell is at most enqueued and dequeued once and its distance to closest zero is calculated once, the time and space complexity would be O(n).

    0_1491245957820_Untitled drawing.jpg

    // Idea: BFS-based shortest distance from zeros.
    class Solution {
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
            m = matrix.size();
            n = matrix[0].size();
            vector<vector<int>> result (m, vector<int> (n, -1));
            queue<pair<int, int>> q;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (!matrix[i][j]) {
                        q.emplace(i, j);
                        result[i][j] = 0;
                    }
            for (; !q.empty(); q.pop()) {
                auto cell = q.front();
                int row = cell.first, col = cell.second;
                int currdist = result[row][col];
                for (int i = 0; i < 4; i++) {
                    int newrow = row + dr[i], newcol = col + dc[i];
                    if (isValid(newrow, newcol) && result[newrow][newcol] == -1) {
                        result[newrow][newcol] = currdist + 1;
                        q.emplace(newrow, newcol);
                    }
                }
            }
            return result;
        }
    private:
        int m, n;
        int dc [4] = {-1, 1, 0, 0}; // delta-col: column change for up, down, left, right
        int dr [4] = {0, 0, -1, 1}; // delta-row: row change for up, down, left, right
        bool isValid(int row, int col) {
            return row >= 0 && row < m && col >=0 && col < n;
        }
    };
    

Log in to reply
 

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