Why is my solution TLE?


  • 0
    J
    public class Solution {
    //BFS
    public void wallsAndGates(int[][] rooms) {
        if(rooms == null || rooms.length == 0) {
            return;
        }
        int row = rooms.length;
        int col = rooms[0].length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(rooms[i][j] == 0) {
                    BFS(rooms, i, j);
                }
            }
        }
    }
    private void BFS(int[][] rooms, int m, int n) {
        int row = rooms.length;
        int col = rooms[0].length;
        int cord = m * col + n;
        int[][] visited = new int[row][col];
        Queue<Integer> qu = new LinkedList<Integer>();
        qu.offer(cord);
        visited[m][n] = 1;
        int dis = 0;
        int[] dx = {1, -1, 0, 0};//up, down, right, left
        int[] dy = {0, 0, 1, -1};
        while(!qu.isEmpty()) {
            int size = qu.size();
            for(int i = 0; i < size; i++) {
                int tmp = qu.poll();
                int x = tmp / col;
                int y = tmp % col;
                rooms[x][y] = Math.min(rooms[x][y], dis);
                for(int k = 0; k < 4; k++) {
                    int newX = x + dx[k];
                    int newY = y + dy[k];
                    if(newX < 0 || newX >= row || newY < 0 || newY >= col) {
                        continue;
                    }   
                    if(visited[newX][newY] == 1) {
                        continue;
                    }
                    if(rooms[newX][newY] == -1) {
                        continue;
                    }
                        qu.offer(newX * col + newY);
                        visited[newX][newY] = 1;
                }
            }
            dis++;
        }
    }
    

    }


  • 0
    P

    The problem may lie in this line:

    rooms[x][y] = Math.min(rooms[x][y], dis);
    

    You just push it into queue not matter what, and continue to evaluate even if you don't have to, for example, if its value is smaller than current dis, you don't have to continue.

    I assume simply continue in this case to cut the branch would work.


Log in to reply
 

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