Java Solution, BFS


  • 35

    General idea is BFS. Some small tricks:

    1. At beginning, set cell value to Integer.MAX_VALUE if it is not 0.
    2. If newly calculated distance >= current distance, then we don't need to explore that cell again.
    public class Solution {
        public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            int m = matrix.size();
            int n = matrix.get(0).size();
            
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix.get(i).get(j) == 0) {
                        queue.offer(new int[] {i, j});
                    }
                    else {
                        matrix.get(i).set(j, Integer.MAX_VALUE);
                    }
                }
            }
            
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int r = cell[0] + d[0];
                    int c = cell[1] + d[1];
                    if (r < 0 || r >= m || c < 0 || c >= n || 
                        matrix.get(r).get(c) <= matrix.get(cell[0]).get(cell[1]) + 1) continue;
                    queue.add(new int[] {r, c});
                    matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
                }
            }
            
            return matrix;
        }
    }
    

    LeetCode has changed the function signature. Updated code:

    public class Solution {
        public int[][] updateMatrix(int[][] matrix) {
            int m = matrix.length;
            int n = matrix[0].length;
            
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        queue.offer(new int[] {i, j});
                    }
                    else {
                        matrix[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
            
            int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int r = cell[0] + d[0];
                    int c = cell[1] + d[1];
                    if (r < 0 || r >= m || c < 0 || c >= n || 
                        matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
                    queue.add(new int[] {r, c});
                    matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
                }
            }
            
            return matrix;
        }
    }
    

  • 2
    V

    @shawngao Could you elaborate on the possible complexity of your solution or in the worst case how many times would the same cell be added to the queue


  • 4

    @vineeth_kumar In worst case, one cell will at max be added to queue once. Thus run time complexity is O(n), n is number of cells.


  • 1
    V

    @shawngao Thank you got a little mixed up with stopping condition of bfs thanks for clearing it up


  • 0
    D

    Great idea! But I think there is no need to check m and n at the beginning since there are at least one zero in the given matrix. I tested that and just got accepted.
    Thanks again for sharing your idea!


  • 0

    @doctral Yes, you are right. Updated my post. Thanks.


  • 1
    M

    I think you can stop exploring the cell as long as it value is not INT_MAX :)


  • 0

    @MichaelZ205 Yes, that's right too.


  • 2
    Q

    just update from four direction, since this is just Manhattan distance

    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        const int m = matrix.size(), n = matrix.empty()? 0 : matrix[0].size();
        auto res = matrix;
        for (auto &vec: res) {
            for (auto &x: vec) {
                if (x != 0) { x = m + n; }  // set to upper bound
            }
        }
        for (int i = 0, h = m - 1; i < m; ++i, --h) {
            for (int j = 0, k = n - 1; j < n; ++j, --k) {
                if (i != 0) {   // not row border
                    res[i][j] = std::min(res[i][j], res[i-1][j] + 1);
                    res[h][j] = std::min(res[h][j], res[h+1][j] + 1);
                }
                if (j != 0) {   // not column border
                    res[i][j] = std::min(res[i][j], res[i][j-1] + 1);
                    res[i][k] = std::min(res[i][k], res[i][k+1] + 1);
                    res[h][j] = std::min(res[h][j], res[h][j-1] + 1);
                    res[h][k] = std::min(res[h][k], res[h][k+1] + 1);
                }
            }
        }
        return res;
    }

  • 1
    P

    Since it is BFS the updated procedure should be:

                if (r < 0 || r >= m || c < 0 || c>= n) {
                    continue;
                }
                if (matrix.get(r).get(c) == Integer.MAX_VALUE) {
                    queue.offer(new int[] {r, c});
                    matrix.get(r).set(c, matrix.get(cell[0]).get(cell[1]) + 1);
                }

  • 0
    C

    The worst case time complexity in this solution is actually when all the cells are 0, so we need to do a BFS in every cell even though we are not updating the value, which is believed to be O(n^3).


  • 1
    E

    @ctfu not sure what you're basing your n as, but for your example it will still be O(N) where N is the number of elements. Yes you are appending then popping each element to and from the queue but all you'll be doing for each element is a boolean check on it's neighbors, which will return false due to every neighbor being 0 which is less than 0 + 1 which is the proposed distance. Since this BFS does not continue when the proposed value is greater than the current "minimum distance," which will be 0 since all cells are 0's, as mentioned previously, it won't proceed. Even if you count constant operations (append, pop, bool comparison) it will still be in the realm of O(N).

    If you want to be pseudo-exact each cell will queue up 2-4 neighbors and all of them will do a boolean comparison upon being popped from the queue so it'll be O(4N * C)
    (if we count these comparisons and popping as constant operations C) which will be O(N).


  • 1

    Previously I tried start from each ZERO do BFS, and it times out. This solution uses some optimization of doing BFS for all zeros at once.


  • 0
    Y

    @shawngao
    DFS VERSION. faster than bfs
    use 0 to turn 1 to -1
    use -1 to turn 1 to -2
    use -2 to turn 1 to -3
    use -3 to turn 1 to -4
    ...
    until all the nodes are visited
    then turn all the value to -value.

        private boolean[][] mark = null;
        private int[][] mtx = null;
        private int m = 0;
        private int n = 0;
        private int cnt = 0;
        public int[][] updateMatrix(int[][] matrix) {
            m = matrix.length;
            if (0 == m) return matrix;
    
            n = matrix[0].length;
            if (0 == n) return matrix;
    
            mark = new boolean[m][n];
            mtx = matrix;
            
            int marker = 0;
            while (cnt != m * n) {
                for (int row = 0; row < m; ++row) {
                    for (int col = 0; col < n; ++col) {
                        if (!mark[row][col] && marker == mtx[row][col])  {
                            dfs(marker, row, col);
                        }
                    }
                }
                --marker;
            }
    
            for (int row = 0; row < m; ++row) {
                for (int col = 0; col < n; ++col) {
                    mtx[row][col] = -mtx[row][col];
                }
            }
    
            return mtx;
        }
    
        // visit point[row][col]
        private void dfs(int marker, int row, int col) {
            mark[row][col] = true;
            ++cnt;
    
            if (row + 1 < m)  {
                if (!mark[row + 1][col] && mtx[row + 1][col] == marker) dfs(marker,row + 1, col);
                else if (1 == mtx[row + 1][col]) mtx[row + 1][col] = marker - 1;
            }
    
            if (row -1 >= 0)  {
                if (!mark[row - 1][col] && mtx[row - 1][col] == marker) dfs(marker,row - 1, col);
                else if (1 == mtx[row - 1][col]) mtx[row - 1][col] = marker - 1;
            }
    
            if (col + 1 < n)  {
                if (!mark[row][col + 1] && mtx[row][col + 1] == marker) dfs(marker,row, col + 1);
                else if (1 == mtx[row][col + 1]) mtx[row][col + 1] = marker - 1;
            }
    
            if (col - 1 >= 0)  {
                if (!mark[row][col - 1] && mtx[row][col - 1] == marker) dfs(marker,row, col - 1);
                else if (1 == mtx[row][col - 1]) mtx[row][col - 1] = marker - 1;
            }
    
        }
    

  • 0
    M

    perfect solution


  • 1
    M

    @vineeth_kumar ,after completed the whole procedure ,every cell would have be added to the queue,and in the end ,the queue is empty;


  • 0
    M

    @shawngao I think every cell would be added to the queue,not only at the worst case,what’s your opinion?


  • 0
    E

    Will there be any problem if we make matrix[i][j] = Integer.MAX_VALUE when it is 1?
    I mean since there is if (r < 0 || r >= m || c < 0 || c >= n || matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
    if matrix[cell[0]][cell[1]] is Integer.MAX_VALUE. Can matrix[r][c] <= matrix[cell[0]][cell[1]] + 1 still work?


  • 0
    M

    @Evilgit after the first procedure ,there are two states vaule of the cells,they are 0,or integer.MAX_VLUE,and the cell of value 0 have been added to the queue,in the next stage ,all the cell valued Integer.MAX_VALUE will be added ti the queue individually,
    in the end ,after the queue is empty,all the cell got their correct value ,


  • 0
    P

    @shawngao The time complexity would be worse as each cell not just en-queue once. For example, if the top-left cell and bottom-right are 0. All cells will en-queue while BFS of top-left 0 (some cell could en-queue several times). Then cells in bottom-right half part of the matrix will en-queue while BFS of bottom-right 0. Suppose there is more 0s. Hence the complexity is not O(n). Please correct me if I am wrong. Thanks!


Log in to reply
 

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