Any idea why my BFS solution gets TLE?


  • 0
    E

    Hi, I'm trying to use BFS on this problem, so I iterate over each element, if it's 0 then just leave it, if it's 1, do BFS on it and the moment we hit a 0, that distance will be the minimum distance, couldn't pass all the test cases, any idea what's dragging me down?

    public class Solution {
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        public int[][] updateMatrix(int[][] matrix) {
            int[][] result = new int[matrix.length][matrix[0].length]; 
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 0) {
                        result[i][j] = 0;
                    } else {
                        BFS(matrix, i, j, result);
                    }
                }
            }
            return result;
        }
        private void BFS(int[][] matrix, int i, int j, int[][] result) {
            boolean[][] visited = new boolean[matrix.length][matrix[0].length];
            Queue<int[]> q = new LinkedList<>();
            visited[i][j] = true;
            q.offer(new int[]{i, j});
            int level = 1, min = Integer.MAX_VALUE;
            while (!q.isEmpty() && min == Integer.MAX_VALUE) {
                int size = q.size();
                for (int k = 0; k < size && min == Integer.MAX_VALUE; k++) {
                    if (min == Integer.MAX_VALUE) {
                        int[] curr = q.poll();
                        for (int d = 0; d < 4; d++) {
                            int x = curr[0] + dx[d], y = curr[1] + dy[d];
                            if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y]) {
                                continue;
                            }
                            if (matrix[x][y] == 0) {
                                min = Math.min(min, level);
                                break;
                            }
                            visited[x][y] = true;
                            q.offer(new int[]{x, y});
                        }     
                    }
                }
                level++;
            }
            result[i][j] = min;
        }
    }
    

  • 0
    Y

    The reason why this is not working is because the time complexity is too large. You do a whole BFS on the entire matrix for every point with value '1' in the matrix, huge redundancy involved.
    0,0,0
    0,1,0
    1,1,1
    For example, you do BFS on (1,1), then you do BFS on (2,1). In fact, doing BFS on (1,1) is part of the BFS processing on (2,1). This kind of overlapping happens in the entire approach. The huge amount of overlapping causes a lot of redundancy.

    PS: You don't have to use Math.min here, since it's BFS, you can return the value of level when you first reach the right answer, it is guaranteed to be the shortest path. This could reduce a little bit time costed.


Log in to reply
 

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