Java BFS solution with O(mn) time complexity


  • 2
    A
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
    	    return;
        }
        Queue<Grid> queue = new LinkedList<Grid> ();
        for (int i = 0; i < rooms.length; i++) {
    	    for (int j = 0; j < rooms[0].length; j++) {
    		    if (rooms[i][j] == 0) {
    			    queue.offer(new Grid(i, j));
    		    }
    	    }
        }
        int[][] diffs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
    	    Grid cur = queue.poll();
    	    for (int[] diff : diffs) {
    		    int i = cur.x + diff[0];
    		    int j = cur.y + diff[1];
    		    if (i >= 0 && i <= rooms.length - 1 && j >= 0 && j <= rooms[0].length - 1 && rooms[i][j] == Integer.MAX_VALUE) {
    			    rooms[i][j] = rooms[cur.x][cur.y] + 1;
    			    queue.offer(new Grid(i, j));
    		    }
    	    }
        }
    }
    
    class Grid {
        int x;
    	int y;
        public Grid(int x, int y) {
    	    this.x = x;
    	    this.y = y;
        }
    }

Log in to reply
 

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