Java 33ms BFS solution, beat 99%


  • 0
    S

    1. run through matrix to find all cell with value 1. If the cell doesn't have zero around it, set it to Integer.MAX_VALUE
    2. run through matrix again. For cell with value 1, use BFS to update matrix. If cell value larger than new value, update it and put cell into queue

    public class Solution {
        int[][] dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        public int[][] updateMatrix(int[][] matrix) {
            if(matrix.length==0||matrix[0].length==0) return matrix;
            int m = matrix.length;
            int n = matrix[0].length;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(matrix[i][j]==1){
                        if(!checkZero(matrix,i,j)){
                            matrix[i][j] = Integer.MAX_VALUE;
                        }
                    }
                }
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(matrix[i][j]==1){
                        bfs(matrix,i,j);
                    }
                }
            }
            return matrix;
        }
        public boolean checkZero(int[][] matrix,int i,int j){
            int m = matrix.length;
            int n = matrix[0].length;
            for(int[] d:dir){
                int dx = d[0]+i;
                int dy = d[1]+j;
                if(dx>=0&&dx<m&&dy>=0&&dy<n&&matrix[dx][dy]==0) return true;
            }
            return false;
        }
        public void bfs(int[][] matrix,int i,int j){
            int m = matrix.length;
            int n = matrix[0].length;
            Queue<int[]> queue = new LinkedList();
            queue.offer(new int[]{i,j});
            int count = 1;
            while(!queue.isEmpty()){
                int size = queue.size();
                count++;
                while(size>0){
                    size--;
                    int[] p = queue.poll();
                    int px = p[0];
                    int py = p[1];
                    for(int[] d:dir){
                        int dx = d[0]+px;
                        int dy = d[1]+py;
                        if(dx<m&&dx>=0&&dy<n&&dy>=0&&matrix[dx][dy]>count){
                            matrix[dx][dy] = count;
                            queue.offer(new int[]{dx,dy});
                        }
                    }
                }
            }
        }
    }
    

Log in to reply
 

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