Both DFS and BFS got TLE...


  • 0
    L

    I tried bfs and dfs to get distance to closest zero but got TLE for both. Can someone plz tell me what is wrong with my methods?

    public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
            if (matrix == null || matrix.size() == 0) {
                return res;
            }
            m = matrix.size();
            n = matrix.get(0).size();
            for (int i = 0; i < m; ++i) {
                List<Integer> row = new ArrayList<>();
                for (int j = 0; j < n; ++j) {
                    if (matrix.get(i).get(j) == 0) {
                        row.add(0);
                    } else {
                        row.add(findZero(matrix, i, j, new boolean[m][n]));
                    }
                }
                res.add(row);
            }
            return res;
        }
    
    private int bfs(List<List<Integer>> matrix, int x, int y, boolean[][] visited) {
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[]{x, y});
            int res = 0;
            while (!q.isEmpty()) {
                int size = q.size();
                for (int s = 0; s < size; ++s) {
                    int[] cur = q.poll();
                    int i = cur[0], j = cur[1];
                    visited[i][j] = true;
                    if (matrix.get(i).get(j) == 0) {
                        return res;
                    }
                    if (i > 0 && !visited[i - 1][j]) {
                        q.offer(new int[]{i - 1, j});
                    }
                    if (i < m - 1 && !visited[i + 1][j]) {
                        q.offer(new int[]{i + 1, j});
                    }
                    if (j > 0 && !visited[i][j - 1]) {
                        q.offer(new int[]{i, j - 1});
                    }
                    if (j < n - 1 && !visited[i][j + 1]) {
                        q.offer(new int[]{i, j + 1});
                    }
                }
                ++res;
            }
            return res;
        }
    
    private int dfs(List<List<Integer>> matrix, int i, int j, boolean[][] visited) {
            if (matrix.get(i).get(j) == 0) {
                return 0;
            }
            visited[i][j] = true;
            int res = Math.max(m,n);
    
            if (i > 0 && !visited[i - 1][j]) {
                res = Math.min(res, dfs(matrix, i - 1, j, visited));
            }
            if (i < m - 1 && !visited[i + 1][j]) {
                res = Math.min(res, dfs(matrix, i + 1, j, visited));
            }
            if (j > 0 && !visited[i][j - 1]) {
                res = Math.min(res, dfs(matrix, i, j - 1, visited));
            }
            if (j < n - 1 && !visited[i][j + 1]) {
                res = Math.min(res, dfs(matrix, i, j + 1, visited));
            }
            visited[i][j] = false;
            return 1 + res;
        }
    

  • 0
    J

    Your direction of the search should be opposite. Starting from the zeros, and then expand the map with bfs, you'll only need to travel each point once.
    It seems worst case run time with your method is (m*n)^2?


  • 0

    try mark {i, j} as visited before inserted into the queue, this could remove duplicates in queue.


Log in to reply
 

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