BFS

841. Keys and Rooms

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms == null || rooms.size() == 0) {
            return true;
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited.add(0);
        while (!q.isEmpty()) {
            int curt = q.poll();
            for (int next : rooms.get(curt)) {
                if (!visited.contains(next)) {
                    q.offer(next);
                    visited.add(next);
                }
            }
        }
        return visited.size() == rooms.size();
    }

1091. Shortest Path in Binary Matrix

    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
        if (grid.length == 1 && grid[0][0] == 0) return 1;
        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0},{1,1}, {-1,-1}, {1,-1}, {-1,1}};
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 0});
        int step = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                for (int[] d : dir) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(grid, nx, ny) && !visited[nx][ny] && grid[nx][ny] == 0) {
                        if (nx == n - 1 && ny == n - 1) return step + 1;
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
            step++;
        }
        return -1;
    }
    
    private boolean inbound(int[][] m, int x, int y) {
        return x >= 0 && y >= 0 && x < m.length && y < m[0].length;
    }

Count the number of oranges and rotten oranges. Starting with all rotten oranges in the queue, traverse in level order to fill all good oranges. Return the number of levels if the all oranges are rotten (check count).

int[][] dirs = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.offer(new int[]{i, j});
            else if (grid[i][j] == 1) count++;
        }
    }
    if (count == 0) return 0;
    int step = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int[] curt = q.poll();
            for (int[] d : dirs) {
                int nx = curt[0] + d[0];
                int ny = curt[1] + d[1];
                if (nx >= 0 
                    && nx < m 
                    && ny >= 0 
                    && ny < n 
                    && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;
                    count--;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        step++;
    }
    return count == 0 ? step - 1 : -1;
}

    directions = [[0,1],[1,0],[-1,0], [0,-1]]
    def orangesRotting(self, grid: List[List[int]]) -> int:
        queue = []
        orange = 0
        for x in range(0, len(grid)):
            for y in range(0, len(grid[0])):
                if grid[x][y] == 2:
                    queue.append([x, y])
                if grid[x][y] == 1:
                    orange += 1
        if orange == 0:
            return 0
        level = 0
        while queue:
            size = len(queue)
            for k in range(0, size):
                curtx, curty = queue.pop(0)
                if grid[curtx][curty] == 1:
                    grid[curtx][curty] = 2
                    orange -= 1
                    if orange == 0:
                        return level
                for d in self.directions:
                    nx = curtx + d[0]
                    ny = curty + d[1]
                    if self.inbound(grid, nx, ny) and grid[nx][ny] == 1:
                        queue.append([nx, ny])
            level += 1
        if orange == 0:
            return level
        return -1
        
    def inbound(self, grid, x, y) :
        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

Highest Peak

Given a 2D boolean array where true represents water and false represents land, generate a grid with highest possible peak. Rules are:

the height of any water cell is 0.
the height of any land cell cannot differ for more than one from any of the neighboring (sharing one edge) cells.

Add all "T" nodes into a BFS queue and trigger a BFS from all those nodes. Also, maintain the distance used to reach each node alongside. Once the BFS visits all the nodes, return the distance to reach every node as the answer.
For the followup:- From all the nodes that have reached max peak height, trigger another BFS that goes from max peak height node to other nodes decrementing the distance. This would lead to more nodes having a height of 0

1162. As Far from Land as Possible

    int[][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
    public int maxDistance(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        int count0 = 0, count1 = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    q.offer(new int[]{i, j});
                    visited.add(i * n + j);
                    count1++;
                } else {
                    count0++;
                }
            }
        }
        int res = -1;
        if (count0 == 0 || count1 == 0) return res;
        int level = -1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                for (int[] d : directions) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(grid, nx, ny) 
                        && !visited.contains(nx * n + ny) && grid[nx][ny] == 0) {
                            q.offer(new int[]{nx, ny});
                            visited.add(nx * n + ny);
                    }
                }
            }
            level++;
        }
        return level;
    }
    
    private boolean inbound(int[][] matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
    }

286. Walls and Gates

    directions = [[0,1],[1,0],[-1,0], [0,-1]]
    def wallsAndGates(self, rooms: List[List[int]]) -> None:
        queue = []
        for x in range(0, len(rooms)):
            for y in range(0, len(rooms[0])):
                if (rooms[x][y] == 0):
                    queue.append([x, y])
        level = 0
        while queue:
            size = len(queue)
            for k in range(0, size):
                curtx, curty = queue.pop(0)
                if rooms[curtx][curty] == 2147483647:
                    rooms[curtx][curty] = level
                for d in self.directions:
                    nx = curtx + d[0]
                    ny = curty + d[1]
                    if self.inbound(rooms, nx, ny) and rooms[nx][ny] == 2147483647:
                        queue.append([nx, ny])
            level += 1
        return
    
    def inbound(self, grid, x, y) :
        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

130. Surrounded Regions

    directions = [[0,1],[1,0],[-1,0], [0,-1]]
    def solve(self, board: List[List[str]]) -> None:
        if not board or len(board) == 0 or len(board[0]) == 0:
            return
        m = len(board)
        n = len(board[0])
        queue = []
        for i in range(0, m):
            if board[i][0] == "O":
                queue.append([i, 0])
            if board[i][n - 1] == "O":
                queue.append([i, n - 1])
        for j in range(0, n):
            if board[0][j] == "O":
                queue.append([0, j])
            if board[m - 1][j] == "O":
                queue.append([m - 1, j])
        while queue:
            x, y = queue.pop(0)
            board[x][y] = "B"  
            for d in self.directions:  ## x= 3,y=1
                nx = x + d[0]
                ny = y + d[1]
                if self.inbound(board, nx, ny) and board[nx][ny] == "O":
                    queue.append([nx, ny])
        
        for i in range(0, m):
            for j in range(0, n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "B":
                    board[i][j] = "O"
        
    
    def inbound(self, grid, x, y) :
        return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

814. Shortest Path in Undirected Graph

public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
        // Write your code here
		Queue<UndirectedGraphNode> q = new LinkedList<>();
		Set<UndirectedGraphNode> visited = new HashSet<>();
		q.offer(A);
		visited.add(A);
		int level = 0;
		while (!q.isEmpty()) {
		    level++;
		    int size = q.size();
		    for (int i = 0; i < size; i++) {
		        UndirectedGraphNode curt = q.poll();
		        for (UndirectedGraphNode next : curt.neighbors) {
		            if (next == B) {
		                return level;
		            }
		            if (visited.contains(next)) {
		                continue;
		            }
		            visited.add(next);
		            q.offer(next);
		        }
		    }
		}
		return -1;
}

1236. Web Crawler

    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        visit = set()
        queue = []
        queue.append(startUrl)
        visit.add(startUrl)
        host = startUrl.split("/")[2]
        res = []
        while queue:
            curt = queue.pop(0)
            res.append(curt)
            for next in htmlParser.getUrls(curt):
                if next not in visit and host in next:
                    queue.append(next)
                    visit.add(next)
        return res

    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        Set<String> visited = new HashSet<>();
        String hostname = startUrl.split("/")[2];
        Queue<String> q = new LinkedList<>();
        q.offer(startUrl);
        while (!q.isEmpty()) {
            String curt = q.poll();
            visited.add(curt);
            for (String next : htmlParser.getUrls(curt)) {
                if (next.indexOf(hostname) != -1 && !visited.contains(next)) {
                    q.offer(next);
                }
            }
        }
        return new ArrayList<>(visited);
    }

417. Pacific Atlantic Water Flow

    int[][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1,0}};
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        List<List<Integer>> result = new ArrayList<>();
        Queue<int[]> q_P = new LinkedList<>();
        Queue<int[]> q_A = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (i == 0 || j == 0) {
                    q_P.offer(new int[]{i, j});
                    pacific[i][j] = true;
                }
                if (i == m - 1 || j == n - 1) {
                    q_A.offer(new int[]{i, j});
                    atlantic[i][j] = true;
                }
            }
        }
        BFS(matrix, q_P, pacific);
        BFS(matrix, q_A, atlantic);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.add(Arrays.asList(new Integer[]{i, j}));    
                }
            }
        }
        return result;
    }
    
    private void BFS(int[][] matrix, Queue<int[]> q, boolean[][] visited) {
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                int x = curt[0], y = curt[1];
                for (int[] d : directions) {
                    int nx = x + d[0];
                    int ny = y + d[1];
                    if (inbound(matrix, nx, ny)
                        && matrix[nx][ny] >= matrix[x][y]
                        && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
    
    private boolean inbound(int[][] matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
    }

815. Bus Routes

Build graph by using stop to next available stops. Level order BFS to find the next stops, return step/level when reach stop T. (This answer will return TLE when there are too many stops)

   public int numBusesToDestination(int[][] routes, int S, int T) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] route : routes) {
            for (int i = 0; i < route.length; i++) {
                for (int j = 0; j < route.length; j++) {
                    if (i == j) continue;
                    map.putIfAbsent(route[i], new HashSet<>());
                    map.putIfAbsent(route[j], new HashSet<>());
                    map.get(route[i]).add(route[j]);
                    map.get(route[j]).add(route[i]);
                }
            }
        }
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(S);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curt = q.poll();
                if (curt == T) return level;
                if (map.get(curt) == null) continue;
                for (int next : map.get(curt)) {
                    if (next == T) return level + 1;
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    q.offer(next);
                }
            }
            level++;
        }
        return -1;
    }

One modification is to check duplicate on bus route, instead of bus stops. That will eliminate lots of path since all stops on traveled path are redundant.

    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S == T) return 0;
        Map<Integer, Set<Integer>> map = new HashMap<>(); // stop : buses
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < routes.length; i++) {
            for (int n : routes[i]) {
                map.putIfAbsent(n, new HashSet<>());
                map.get(n).add(i);
            }
        }
        if (!map.containsKey(S)) return -1;
        Set<Integer> visited = new HashSet<>(); 
        int count = 0;
        q.offer(S);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int curt = q.poll();
                if (curt == T) return count + 1;
                for (int r : map.get(curt)) {
                    if (visited.contains(r)) continue;
                    visited.add(r);
                    for (int next : routes[r]) {
                        if (next == T) return count + 1;
                        q.offer(next);
                    }
                }
            }
            count++;
        }
        return -1;
    }

N is number of stops, T is the stops * edges: T: O(n^2)

490. The Maze

Find the next node by extending the directions, until reach boundary or wall. Use boolean[][] visited to record all visited nodes.

    int[][] dirs = {{1,0} , {0,1}, {-1,0}, {0,-1}};
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        visited[start[0]][start[1]] = true;
        while (!q.isEmpty()) {
            int[] curt = q.poll();
            if (curt[0] == destination[0] && curt[1] == destination[1]) {
                return true;
            }
            for (int[] dir : dirs) {
                int x = curt[0];
                int y = curt[1];
                while (inbound(maze, x + dir[0], y + dir[1]) 
                       && maze[x + dir[0]][y + dir[1]] != 1) {
                    x += dir[0];
                    y += dir[1];
                }
                if (x == destination[0] && y == destination[1]) {
                    return true;
                }
                if (!visited[x][y]) {
                    visited[x][y] = true;
                    q.offer(new int[]{x, y});
                }
            }
        }
        return false;
    }
    
    private boolean inbound(int[][] maze, int x, int y) {
        return x >= 0 && y >= 0 && x < maze.length && y < maze[0].length;
    }

505. The Maze II

The BFS solution requires to store all path to destination. Use a dist matrix to store the minimum distance between each grid and start point. Replace the distance when new calculated steps is less than the earlier calculations. Output result as all distances are calculated.

int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
    if (start == null || destination == null || maze == null || maze.length == 0 || maze[0].length == 0) {
        return -1;
    }
    int m = maze.length, n = maze[0].length;
    int[][] dist = new int[m][n];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

    Queue<int[]> q = new LinkedList<>();
    q.offer(start);
    dist[start[0]][start[1]] = 0;
    while (!q.isEmpty()) {
        int[] curt = q.poll();
        for (int[] d : direction) {
            int nx = curt[0];
            int ny = curt[1];
            int step = 0;
            while (inbound(maze, nx + d[0], ny + d[1]) && maze[nx + d[0]][ny + d[1]] == 0) {
                nx += d[0];
                ny += d[1];
                step++;
            }
            if (dist[nx][ny] > dist[curt[0]][curt[1]] + step) {
                dist[nx][ny] = dist[curt[0]][curt[1]] + step;
                q.offer(new int[]{nx, ny});
            }
        }
    }
    return dist[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 
                                : dist[destination[0]][destination[1]];
}

private boolean inbound(int[][] grid, int x, int y) {
    return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}

Solution: Dijkstra

611. Knight Shortest Path [LintCode]

Given a knight in a chessboard (a binary matrix with 0as empty a 1as barrier) with a source position, find the shortest path to a destination position, return the length of the route.

Return -1 if knight can not reached.

Notice

Source and destination must be empty.
Knight can not enter the barrier.

    int[][] directions = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1},
            {1, -2}, {2, -1}, {-1, -2}, {-2, -1}};
    public int knightshortestpath(int[][] grid, int[] start, int[] destination) {
        if(grid == null || grid.length == 0 ||
                grid[0].length == 0 || start == null || destination == null){
            return -1;
        }
        if (start[0] == destination[0] && start[1] == destination[1]) {
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        grid[start[0]][start[1]] = 2;
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curt = queue.poll();
                for (int[] d : directions) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (nx == destination[0] && ny == destination[1]) {
                        return level + 1;
                    }
                    if (inbound(grid, nx, ny) && grid[nx][ny] == 0) {
                        grid[nx][ny] = 2;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
            level++;
        }
        return -1;
    }

    private boolean inbound(int[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }

542. 01 Matrix

Fill the result matrix with Integer.MAX_VALUE to detect if the node has been visited. Starting from 0 grids, use BFS to detect if the next distance from 0 is larger than expected, if so, correct it to the right value. Offer that next node to the queue.

T: O(m * n) S: O(m * n)

    int[][] dirs = {{1,0} , {0,1}, {-1,0}, {0,-1}};
    public int[][] updateMatrix(int[][] matrix) {
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    q.offer(new int[]{i, j});
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        while (!q.isEmpty()) {
            int[] curt = q.poll();
            for (int[] d : dirs) {
                int nx = curt[0] + d[0];
                int ny = curt[1] + d[1];
                if (inbound(matrix, nx, ny) && matrix[nx][ny] > matrix[curt[0]][curt[1]] + 1) {
                    matrix[nx][ny] = matrix[curt[0]][curt[1]] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return matrix;
    }
    
    private boolean inbound(int[][] matrix, int x, int y) {
        return x >= 0 && y >= 0 && x < matrix.length && y < matrix[0].length;
    }

127. Word Ladder

T: O(k^2 * N) N is number of words and k is the average length of words

    public int ladderLength(String beginWord,
                            String endWord,
                            List<String> wordList) {
        if (beginWord == null || endWord == null 
                || beginWord.isEmpty() || endWord.isEmpty()) {
            return 0;
        }
        if (beginWord.equals(endWord)) return 0;
        Set<String> dict = new HashSet<>();
        dict.addAll(wordList);
        if (!dict.contains(endWord)) return 0;
        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int level = 1;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curt = q.poll();
                for (String next : getNexts(curt, dict)) {
                    if (next.equals(endWord)) return level + 1;
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    q.offer(next);
                }
            }
            level++;
        }
        return 0;
    }
    
    private Set<String> getNexts(String s, Set<String> dict) {
        Set<String> result = new HashSet<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[i] = c;
                String next = String.valueOf(chars);
                if (dict.contains(next)) result.add(next);
            }
            chars[i] = old;
        }
        return result;
    }

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        dic = set(wordList)
        if endWord not in dic:
            return 0
        queue = []
        visit = set()
        queue.append(beginWord)
        visit.add(beginWord)
        level = 1
        while queue:
            size = len(queue)
            for i in range(size):
                curt = queue.pop(0)
                for next in self.getNext(curt, dic, visit):
                    if next == endWord:
                        return level + 1
                    if next in dic and next not in visit:
                        visit.add(next)
                        queue.append(next)
            level += 1
        return 0
    
    def getNext(self, s, dic, visit):
        res = []
        for i in range(len(s)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new = s[:i] + c + s[i + 1:]
                if new in dic and new not in visit:
                    res.append(new)
        return res

126. Word Ladder II

Use BFS level order traversal to build graph and record distance from start node. DFS to build path.

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, Set<String>> graph = new HashMap<>();
        Set<String> dict = new HashSet<>();
        dict.addAll(wordList);
        List<List<String>> res = new ArrayList<>();
        if (!dict.contains(endWord) || beginWord.equals(endWord)) return res;
        bfsBuildGraph(beginWord, endWord, dict, dist, graph);
        List<String> list = new ArrayList<>();
        list.add(beginWord);
        dfs(beginWord, endWord, list, res, dist, graph);
        return res;
    }

    private void dfs(String curt,
                     String target,
                     List<String> list,
                     List<List<String>> result,
                     Map<String, Integer> dist,
                     Map<String, Set<String>> graph) {
        if (curt.equals(target)) {
            result.add(new ArrayList<>(list));
            return;
        }
        if (graph.get(curt) == null) return;
        for (String next : graph.get(curt)) {
            if (dist.get(next) == dist.get(curt) + 1) {
                list.add(next);
                dfs(next, target, list, result, dist, graph);
                list.remove(list.size() - 1);
            }
        }
    }

    private void bfsBuildGraph(String beginWord,
                              String endWord,
                              Set<String> dict,
                               Map<String, Integer> dist,
                               Map<String, Set<String>> graph) {
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        dist.put(beginWord, 0);
        boolean foundEnd = false;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curt = q.poll();
                int d = dist.get(curt);
                graph.putIfAbsent(curt, new HashSet<>());
                for (String next : getNexts(curt, dict)) {
                    graph.get(curt).add(next);
                    if (next.equals(endWord)) foundEnd = true;
                    if (dist.containsKey(next)) continue;
                    dist.put(next, d + 1);
                    q.offer(next);
                }
            }
            if (foundEnd) break;
        }
    }
    
    private Set<String> getNexts(String s, Set<String> dict) {
        Set<String> result = new HashSet<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char old = chars[i];
            for (char c = 'a'; c <= 'z'; c++) {
                chars[i] = c;
                String next = String.valueOf(chars);
                if (dict.contains(next)) result.add(next);
            }
            chars[i] = old;
        }
        return result;
    }

133. Clone Graph

Use a map to store the relationship key: current node value: corresponding new node. Traverse the graph with a curt node and add corresponding neighbors to the neighbors list.

T: O(n)

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> q = new LinkedList<>();
        map.put(node, new Node(node.val, new ArrayList<>()));
        q.offer(node);
        while (!q.isEmpty()) {
            Node curt = q.poll();
            for (Node next : curt.neighbors) {
                if (!map.containsKey(next)) {
                    map.put(next, new Node(next.val, new ArrayList<>()));
                    q.offer(next);
                }
                map.get(curt).neighbors.add(map.get(next));
            }
        }
        return map.get(node);
    }

    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        dic = {}
        visited = set()
        queue = []
        queue.append(node)
        visited.add(node)
        dic[node] = Node(node.val)
        while queue:
            curt = queue.pop(0)
            for next in curt.neighbors:
                if next not in visited:
                    dic[next] = Node(next.val)
                    queue.append(next)
                    visited.add(next)
                dic[curt].neighbors.append(dic[next])
        return dic[node]

DFS link

261. Graph Valid Tree

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            map.putIfAbsent(u, new HashSet<>());
            map.putIfAbsent(v, new HashSet<>());
            map.get(u).add(v);
            map.get(v).add(u);
        }
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited.add(0);
        while (!q.isEmpty()) {
            int curt = q.poll();
            if (map.get(curt) == null) continue;
            for (int next : map.get(curt)) {
                map.get(next).remove(curt);
                if (visited.contains(next)) {
                    return false;
                }
                visited.add(next);
                q.offer(next);
            }
        }
        return visited.size() == n;
    }

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if n != len(edges) + 1:
            return False
        graph = [[] for i in range(n)]
        indegree = [0] * n
        for v, u in edges:
            graph[u].append(v)
            graph[v].append(u)
            
        queue = []
        visited = set()
        queue.append(0)
        visited.add(0)
        while queue:
            curt = queue.pop(0)
            for next in graph[curt]:
                if next in visited:
                    return False
                graph[next].remove(curt)
                visited.add(next)
                queue.append(next)
        return len(visited) == n

909. Snakes and Ladders

Convert index to board by using:

int row = n - (next - 1) / n - 1
int col = (n - row) % 2 != 0 ? (next - 1) % n : n - (next - 1) % n - 1

    public int snakesAndLadders(int[][] board) {
        if (board == null || board.length == 0) return 0;
        int n = board.length;
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(1);
        visited.add(1);
        int step = 0, min = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curt = q.poll();
                if (curt == n * n) min = Math.min(min, step);
                for (int k = 1; k <= 6; k++) {
                    int next = curt + k;
                    if (next > n * n) break;
                    if (visited.contains(next)) continue;
                    visited.add(next);
                    int row = n - (next - 1) / n - 1;
                    int col = (n - row) % 2 != 0 ? (next - 1) % n
                                                 : n - (next - 1) % n - 1;
                    if (board[row][col] == curt) continue;
                    if (board[row][col] == -1) {
                        q.offer(next);
                    } else {
                        q.offer(board[row][col]);
                    }
                }
            }
            step++;
        } 
        return min == Integer.MAX_VALUE ? -1 : min;
    }

752. Open the Lock

Similar as 127. Word Ladder.

    public int openLock(String[] deadends, String target) {
        Set<String> deads = new HashSet<>();
        for (String d : deadends) {
            if (d.equals("0000")) {
                return -1;
            }
            deads.add(d);
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer("0000");
        visited.add("0000");
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curt = queue.poll();
                if (curt.equals(target)) return level;
                for (String next : getNexts(curt, deads, visited)) {
                    if (visited.contains(next)) {
                        continue;
                    }
                    visited.add(next);
                    queue.offer(next);
                }
            }
            level++;
        }
        return -1;
    }

   private Set<String> getNexts(String curt, Set<String> deads, Set<String> visited) {
     Set<String> nextCurs = new HashSet<>();
        char[] chars = curt.toCharArray();
        for (int i = 0; i < 4; i++) {
            char origin = chars[i];
            chars[i] = (char)((origin - '0' + 1) % 10 + '0');
            String next = new String(chars);

            if (!deads.contains(next) && !visited.contains(next)) {
                nextCurs.add(next);
            }
            chars[i] = (char)((origin - '0' - 1 + 10) % 10 + '0');
            next = new String(chars);

            if (!deads.contains(next) && !visited.contains(next)) {
                nextCurs.add(next);
            }
            chars[i] = origin;
        }
        return nextCurs;
    }

    def openLock(self, deadends: List[str], target: str) -> int:
        start = "0000"
        dead = set(deadends)
        if start in dead:
            return -1
        visited = set()
        queue = []
        queue.append(start)
        visited.add(start)
        level = 0
        while queue:
            level += 1
            size = len(queue)
            for i in range(size):
                curt = queue.pop(0)
                for next in self.getnexts(curt):
                    if target == next:
                        return level
                    if next not in visited and next not in dead:
                        queue.append(next)
                        visited.add(next)
        return -1
        
    
    def getnexts(self, s):
        for i in range(4):
            yield s[:i] + str((int(s[i]) + 1) % 10) + s[i+1:]
            yield s[:i] + str((int(s[i]) - 1) % 10) + s[i+1:]

1088. Confusing Number II

Check on curt get TLE, however check both on curt and next should work.

    Map<Integer, Integer> map;
    public int confusingNumberII(int N) {
        map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int count = 0;
        Set<Integer> set = new HashSet<>();
        set.add(0);
        while (!q.isEmpty()) {
            int curt = q.poll();
            for (int d : map.keySet()) {
                int next = curt * 10 + d;
                if (next > N) return count; 
                if (next != 0) {
                    q.offer(next);
                }
                if (isConfusing(next) && !set.contains(next)) {
                    set.add(next);
                    count++;
                }
            }
        }
        return count;
    }
    
    private boolean isConfusing(int n) {
        long rot = 0;
        int tmp = n;
        while (n > 0) {
            rot = rot * 10 + map.get(n % 10);
            n /= 10;
        }
        return rot != tmp;
    }

    Map<Integer, Integer> map;
    public int confusingNumberII(int N) {
        map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        int count = 0;
        Set<Integer> set = new HashSet<>();
        while (!q.isEmpty()) {
            int curt = q.poll();
            if (curt > N) break; 
            if (isConfusing(curt) && !set.contains(curt)) {
                set.add(curt);
                count++;
            }
            for (int d : map.keySet()) {
                q.offer(curt * 10 + d);
            }
        }
        return count;
    }
    
    private boolean isConfusing(int n) {
        long rot = 0;
        int tmp = n;
        while (n > 0) {
            rot = rot * 10 + map.get(n % 10);
            n /= 10;
        }
        return rot != tmp;
    }

1129. Shortest Path with Alternating Colors

    public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
        int[][] graph = new int[n][n];
        buildGraph(graph, n, red_edges, blue_edges);
        Queue<int[]> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        q.offer(new int[]{0, 1});
        q.offer(new int[]{0, -1});
        
        int[] res = new int[n];
        Arrays.fill(res, Integer.MAX_VALUE);
        res[0] = 0;
        
        int level = 0;
        while (!q.isEmpty()) {
            level++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                int node = curt[0], color = curt[1];
                for (int k = 0; k < n; k++) {
                    if (graph[node][k] == 0 || graph[node][k] == -color) {
                        if (!set.add(k + " " + (-color))) continue;
                        q.offer(new int[]{k, -color});
                        res[k] = Math.min(res[k], level);
                    }
                }
            }
        }
        for (int i = 1; i < n; i++) {
            if (res[i] == Integer.MAX_VALUE) {
                res[i] = -1;
            }
        }
        return res;
    }
    
    private void buildGraph(int[][] g, int n, int[][] red_edges, int[][] blue_edges) {
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], -n);
        }
        for (int[] e : red_edges) {
            g[e[0]][e[1]] = 1;
        }
        for (int[] e : blue_edges) {
            int from = e[0];
            int to = e[1];
            if (g[from][to] == 1) {
                g[from][to] = 0;
            } else {
                g[from][to] = -1;
            }
        }
    }

317. Shortest Distance from All Buildings

bfs level order traverse starts from all buildings, go through all each empty grids, to calculate the cumulated shortest distance from all buildings. Also count how many houses can reach this spot, when output, detect if this spot can be reached by all starting points.

T: O((mn)^2) .S: O(mn)

    int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return -1;
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n], count = new int[m][n];
        int house = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    house++;
                    dist[i][j] = -1;
                    bfs(grid, dist, count, i, j);
                } else if (grid[i][j] == 2) {
                    dist[i][j] = -1;
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] != -1 && grid[i][j] == 0 && count[i][j] == house) {
                    min = Math.min(min, dist[i][j]);
                }
            }
        } 
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    
    private void bfs(int[][] grid, int[][] dist, int[][] count, int x, int y) {
        int n = grid[0].length;
        Set<Integer> set = new HashSet<>();
        Queue<int[]> q = new LinkedList<>();
        set.add(x * n + y);
        q.offer(new int[]{x, y});
        int level = 0;
        while (!q.isEmpty()) {
            level++;
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int[] curt = q.poll();
                for (int[] d : direction) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(nx, ny, grid) 
                        && !set.contains(nx * n + ny) 
                        && grid[nx][ny] != 1 
                        && grid[nx][ny] != 2) {
                        count[nx][ny]++;
                        dist[nx][ny] += level;
                        set.add(nx * n + ny);
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }
    
    private boolean inbound(int x, int y, int[][] grid) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }

864. Shortest Path to Get All Keys

    int x = -1, y = -1;
    int max = -1;
    int[][] direction = new int[][]{{1,0}, {0,1}, {-1,0}, {0,-1}};
    public int shortestPathAllKeys(String[] grid) {
        int m = grid.length, n = grid[0].length();
        char[][] g = new char[m][n];
        for (int i = 0; i < grid.length; i++) {
            g[i] = grid[i].toCharArray();
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == '@') {
                    x = i;
                    y = j;
                } else if (g[i][j] >= 'a' && g[i][j] <= 'z') {
                    max = Math.max(g[i][j] - 'a' + 1, max);
                }
            }
        }
        Queue<Node> q = new LinkedList<>();
        Set<String> set = new HashSet<>();
        set.add(0 + " " + x + " " + y);
        q.offer(new Node(x, y, 0));
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node curt = q.poll();
                if (curt.keys == Math.pow(2, max) - 1) {
                    return level;
                }
                for (int[] d : direction) {
                    int nx = curt.x + d[0];
                    int ny = curt.y + d[1];
                    int keys = curt.keys;
                    if (inbound(g, nx, ny)) {
                        if (g[nx][ny] == '#') continue;
                        if (g[nx][ny] >= 'a' && g[nx][ny] <= 'z') {
                            keys |= 1 << g[nx][ny] - 'a';
                        }
                        if (g[nx][ny] >= 'A' && g[nx][ny] <= 'Z' && ((keys >> (g[nx][ny] - 'A')) & 1) == 0) {
                            continue;    
                        }
                        if (!set.contains(keys + " " + nx + " " + ny)) {
                            set.add(keys + " " + nx + " " + ny);
                            q.offer(new Node(nx, ny, keys));
                        }
                    }
                }
            }
            level++;
        }
        return -1;
    }
    
    class Node {
        int x, y, keys;
        public Node(int x, int y, int keys) {
            this.x = x;
            this.y = y;
            this.keys = keys;
        }
    }
    
    private boolean inbound(char[][] grid, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
    }

773. Sliding Puzzle

    public int slidingPuzzle(int[][] board) {
        StringBuilder start = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) start.append(board[i][j]);
        }
        int[][] nexts = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
        String target = "123450";
        Queue<String> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        visited.add(start.toString());
        q.offer(start.toString());
        int step = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String curt = q.poll();
                if (curt.equals(target)) return step;
                int zero = curt.indexOf('0');
                if (zero == -1) return -1;
                for (int next : nexts[zero]) {
                    StringBuilder sb = new StringBuilder(curt);
                    char temp = sb.charAt(next);
                    sb.setCharAt(zero, temp);
                    sb.setCharAt(next, '0');
                    String n = sb.toString();
                    if (n.equals(target)) return step + 1;
                    if (visited.contains(n)) continue;
                    q.offer(n);
                    visited.add(n);
                }
            }
            step++;
        }
        return -1;
    }

    int[][] move = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();
        if (start.equals(target)) {
            return 0;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curt = queue.poll();
                for (String next : getNext(curt)) {
                    if (next.equals(target)) {
                        return level;
                    }
                    if (!visited.contains(next)) {
                        queue.offer(next);
                        visited.add(next);
                    }
                }
            }
        }
        return -1;
    }
    
    private Set<String> getNext(String s) {
        Set<String> set = new HashSet<>();
        StringBuilder sb = new StringBuilder(s);
        int u = s.indexOf("0");
        char uchar = sb.charAt(u);
        for (int v : move[u]) {
            char vchar = sb.charAt(v);
            sb.setCharAt(v, uchar);
            sb.setCharAt(u, vchar);
            set.add(sb.toString());
            System.out.println(sb.toString());
            sb = new StringBuilder(s);
        }
        return set;
    }

847. Shortest Path Visiting All Nodes

1293. Shortest Path in a Grid with Obstacles Elimination

public int shortestPath(int[][] grid, int k) {
    int step = 0;
    int m = grid.length;
    int n = grid[0].length;
    int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int[][] seen = new int[m][n]; // min obstacles elimination from (0,0) to (x, y)
    for (int i = 0; i < m; i++) {
        Arrays.fill(seen[i], Integer.MAX_VALUE);
    }
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 0, 0});
    seen[0][0] = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        while (size-- > 0) {
            int[] cur = q.poll();
            if (cur[0] == m - 1 && cur[1] == n - 1) {
                return step;
            }
            for (int[] dir : DIRS) {
                int x = dir[0] + cur[0];
                int y = dir[1] + cur[1];
                if (x < 0 || x >= m || y < 0 || y >= n) {
                    continue;
                }
                int o = grid[x][y] + cur[2];
                if (o >= seen[x][y] || o > k) {
                    continue;
                }
                seen[x][y] = o;
                q.offer(new int[]{x, y, o});
            }
        }
        ++step;
    }
    return -1;  
}

675. Cut Off Trees for Golf Event

    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int cutOffTree(List<List<Integer>> forest) {
        if (forest == null || forest.size() == 0 || forest.get(0).size() == 0) {
            return -1;
        }
        List<int[]> treeHeights = getAllTreeHights(forest);
        Collections.sort(treeHeights, (a, b) -> (a[2] - b[2]));
        int i = 0;
        int[] pre = new int[]{0, 0};
        int step = 0;
        while (i < treeHeights.size()) {
            int[] curt = treeHeights.get(i);
            int s = getMinimumSteps(forest, pre[0], pre[1], curt[0], curt[1]);
            if (s == -1) return -1;
            step += s;
            pre[0] = curt[0];
            pre[1] = curt[1];
            forest.get(pre[0]).set(pre[1], 1);
            i++;
        }
        return step;
    }

    private int getMinimumSteps(List<List<Integer>> forest, int curX, int curY, int aimX, int aimY) {
        int n = forest.get(0).size();
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(new int[]{curX, curY});
        visited.add(curX * n + curY);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] curt = q.poll();
                if (curt[0] == aimX && curt[1] == aimY) {
                    return level;
                }
                for (int[] d : directions) {
                    int nx = curt[0] + d[0];
                    int ny = curt[1] + d[1];
                    if (inbound(forest, nx, ny) && !visited.contains(nx * n + ny) && forest.get(nx).get(ny) != 0) {
                        visited.add(nx * n + ny);
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
            level++;
        }
        return -1;
    }

    private List<int[]> getAllTreeHights(List<List<Integer>> forest) {
        List<int[]> treeHeights = new LinkedList<>();
        for (int i = 0; i < forest.size(); i++) {
            for (int j = 0; j < forest.get(0).size(); j++) {
                int[] res = new int[3];
                res[0] = i;
                res[1] = j;
                res[2] = forest.get(i).get(j);
                if (res[2] > 1) {
                    treeHeights.add(res);
                }
            }
        }
        return treeHeights;
    }
    
    private boolean inbound(List<List<Integer>> forest, int x, int y) {
        return x >= 0 && y >= 0 && x < forest.size() && y < forest.get(0).size();
    }

import collections
class Solution(object):
    def cutOffTree(self, G):
        """
        :type forest: List[List[int]]
        :rtype: int
        """
        if not G or not G[0]: return -1
        m, n = len(G), len(G[0])
        trees = []
        for i in xrange(m):
            for j in xrange(n):
                if G[i][j] > 1:
                    trees.append((G[i][j], i, j))
        trees = sorted(trees)
        count = 0
        cx, cy = 0, 0
        for h, x, y in trees:
            step = self.BFS(G, cx, cy, x, y)
            if step == -1:
                return -1
            else:
                count += step
                G[x][y] = 1
                cx, cy = x, y
        return count

    def BFS(self, G, cx, cy, tx, ty):
        m, n = len(G), len(G[0])
        visited = [[False for j in xrange(n)] for i in xrange(m)]
        Q = collections.deque()
        step = -1
        Q.append((cx, cy))
        while len(Q) > 0:
            size = len(Q)
            step += 1
            for i in xrange(size):
                x, y = Q.popleft()
                visited[x][y] = True
                if x == tx and y == ty:
                    return step
                for nx, ny in [(x + 1, y), (x - 1, y), (x, y-1), (x, y + 1)]:
                    if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]:
                        continue
                    Q.append((nx, ny))
        return -1

1345. Jump Game IV

BFS Level order traversal.

public int minJumps(int[] arr) {
    int n = arr.length;
    HashMap<Integer, List<Integer>> indicies = new HashMap<>();
    for (int i = 0; i < n; i++)
        indicies.computeIfAbsent(arr[i], x -> new LinkedList<>()).add(i);
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    int level = 0;
    visited[0] = true;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int index = q.poll();
            if (index == n - 1) {
                return level;
            }
            List<Integer> nexts = indicies.get(arr[index]);
            nexts.add(index + 1);
            nexts.add(index - 1);
            for (int next : nexts) {
                if (next >= 0 && next < n && !visited[next] && next != index) {
                    q.offer(next);
                    visited[next] = true;
                }
            }
            nexts.clear();
        }
        level++;
    }
    return -1;
}

2096. Step-By-Step Directions From a Binary Tree Node to Another

import java.util.*;

public class Solution {
    private static final String L = "L";
    private static final String R = "R";
    private static final String U = "U";

    private Map<TreeNode, List<DirNode>> map;
    private TreeNode root;
    private int startValue;

    public String getDirections(TreeNode root, int startValue, int destValue) {
        this.map = new HashMap<>();
        this.startValue = startValue;
        this.root = root;

        buildGraph(root);

        TreeNode startNode = findNode(root, startValue);
        if (startNode == null) return "";

        Queue<Pair> queue = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        queue.offer(new Pair(startNode, ""));
        visited.add(startNode);

        while (!queue.isEmpty()) {
            Pair curr = queue.poll();
            TreeNode node = curr.node;
            String path = curr.path;

            if (node.val == destValue) {
                return path;
            }

            for (DirNode next : map.getOrDefault(node, Collections.emptyList())) {
                if (!visited.contains(next.node)) {
                    visited.add(next.node);
                    queue.offer(new Pair(next.node, path + next.dir));
                }
            }
        }

        return "";  // No path found
    }

    private void buildGraph(TreeNode node) {
        if (node == null) return;

        if (node.left != null) {
            map.computeIfAbsent(node, k -> new ArrayList<>()).add(new DirNode(L, node.left));
            map.computeIfAbsent(node.left, k -> new ArrayList<>()).add(new DirNode(U, node));
            buildGraph(node.left);
        }

        if (node.right != null) {
            map.computeIfAbsent(node, k -> new ArrayList<>()).add(new DirNode(R, node.right));
            map.computeIfAbsent(node.right, k -> new ArrayList<>()).add(new DirNode(U, node));
            buildGraph(node.right);
        }
    }

    private TreeNode findNode(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) return root;
        TreeNode left = findNode(root.left, val);
        if (left != null) return left;
        return findNode(root.right, val);
    }

    private static class DirNode {
        String dir;
        TreeNode node;

        DirNode(String dir, TreeNode node) {
            this.dir = dir;
            this.node = node;
        }
    }

    private static class Pair {
        TreeNode node;
        String path;

        Pair(TreeNode node, String path) {
            this.node = node;
            this.path = path;
        }
    }
}

2603. Collect Coins in a Tree

Approach

Prune all useless leaf nodes recursively:
- Start by removing leaf nodes that do not contain coins.
- When you remove a leaf, its parent might become a leaf.
- If that new leaf also has no coin, remove it as well.
- Repeat this process until all remaining leaves have coins.
Simulate collecting coins from grandparent nodes:
- Once only coin-containing leaves remain, we assume the coins can be collected from 2 hops away.
- So, we remove the leaves and their direct parents, since we don’t need to walk all the way to the leaves.
Count remaining edges:
- After the pruning steps, count the remaining edges.
- Since we count both directions (a → b and b → a), we multiply the remaining edge count by 2.

Complexity

Time Complexity: O(n) — each node and edge is processed at most a few times.
Space Complexity: O(n) — for adjacency lists, degree counts, and queues.

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        int n = coins.size();
        vector<set<int>> graph(n);

        // Build the adjacency list
        for (const auto& e : edges) {
            graph[e[0]].insert(e[1]);
            graph[e[1]].insert(e[0]);
        }

        queue<int> leaves;
        int totalEdges = edges.size() * 2;
        int deletedEdges = 0;

        // Remove all leaves with no coins
        for (int i = 0; i < n; ++i) {
            if (graph[i].size() == 1 && coins[i] == 0) {
                leaves.push(i);
            }
        }

        while (!leaves.empty()) {
            int leaf = leaves.front();
            leaves.pop();

            if (graph[leaf].empty()) continue;  // Already removed

            int parent = *graph[leaf].begin();

            graph[parent].erase(leaf);
            graph[leaf].erase(parent);
            deletedEdges += 2;
            if (graph[parent].size() == 1) {
            // If the parent becomes a leaf and has no coin, schedule it for removal
            if (graph[parent].size() == 1 && coins[parent] == 0) {
                leaves.push(parent);
            }
        }
            }

            // If the parent becomes a leaf and has no coin, schedule it for removal
            if (graph[parent].size() == 1 && coins[parent] == 0) {
                leaves.push(parent);
            }
        }

        // Collect remaining leaves (they must have coins)
        for (int i = 0; i < n; ++i) {
            if (graph[i].size() == 1) {
                leaves.push(i);
            }
        }

        // Remove leaves and their immediate parents (2 steps)
        for (int step = 0; step < 2; ++step) {
            int size = leaves.size();
            while (size--) {
                int leaf = leaves.front();
                leaves.pop();

                if (graph[leaf].empty()) continue;

                int parent = *graph[leaf].begin();

                graph[parent].erase(leaf);
                graph[leaf].erase(parent);
                deletedEdges += 2;

                if (graph[parent].size() == 1) {
                    leaves.push(parent);
                }
            }
        }
        return totalEdges - deletedEdges;
    }
};

int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
    int n = coins.size();
    vector<vector<int>> adj(n);  // Adjacency list

    // Build the graph
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    vector<int> degree(n), steps(n, 30000);  // degree: number of neighbors; steps: pruning marker
    vector<int> queue;

    // Initialize degrees and identify leaf nodes
    for (int i = 0; i < n; ++i) {
        degree[i] = adj[i].size();
        if (degree[i] == 1) {
            queue.push_back(i);
        }
    }

    int remainingNodes = n;

    // Prune nodes from the leaves inward
    while (!queue.empty()) {
        int node = queue.back(); queue.pop_back();

        if (--steps[node]) {  // If this node can still be removed
            --remainingNodes;
            for (int neighbor : adj[node]) {
                // Propagate step value: 2 if coin exists, otherwise large number
                steps[neighbor] = min(steps[neighbor], min(steps[node], coins[node] ? 2 : 30000));
                if (--degree[neighbor] == 1) {
                    queue.push_back(neighbor);
                }
            }
        }
    }

    // Final result: number of remaining edges * 2
    return 2 * max(0, remainingNodes - 1);
}

PreviousGreedy NextDFS

Last updated 5 months ago

Was this helpful?