Series: How to Succeed in Algorithms Interview
Applications of BFS
- Graph, or problems can be converted to graph
- find shortest path, min value
- bfs on matrix or indexes on 2 strings
Starting Points
What to add to the queue:
- edges, boundaries
- same level elements
- all nodes
Multiple Starting Points
- BFS for each point
- Put all points into queue once
- BFS
Implementation Detail
- visited array or set
- queue stores nodes and their status
- current state: {current node, visited nodes}
- bit masks to store visited nodes
- while (!queue.isEmpty())
Enqueue all Points into Queue first
- LeetCode 317 - Shortest Distance from All Buildings
- build a house on an empty land which reaches all buildings in the shortest amount of distance
- LeetCode 542 - 01 Matrix
- the initial items in the queue: 0
- start by adding all the cells with 0s to q.
- If the new calculated distance for neighbour {i,j} is smaller, we add {i,j} to q and update dist[i][j]
- [LeetCode 286 - Walls and Gates]
- Fill each empty room with the distance to its nearest gate
public void wallsAndGates(int[][] rooms) { LinkedList<int[]> list = new LinkedList<int[]>(); for(int i = 0; i < rooms.length; i++) { for(int j = 0; j < rooms[0].length; j++) { if(rooms[i][j] == 0) list.add(new int[]{i,j}); } } int[][] diff = new int[][]{{-1,0,1,0},{0,1,0,-1}}; while(!list.isEmpty()) { int[] pop = list.remove(); for(int i = 0; i < diff[0].length; i++) { int newR = pop[0] + diff[0][i]; int newC = pop[1] + diff[1][i]; if(newR < 0 || newR >= rooms.length || newC < 0 || newC >= rooms[0].length || rooms[newR][newC] != Integer.MAX_VALUE) continue; rooms[newR][newC] = rooms[pop[0]][pop[1]] + 1; list.add(new int[]{newR, newC}); } } }
Tree - Level Order traverse
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root == null) return Collections.emptyList();
Queue<QueueNode> queue = new LinkedList<>();
Map<Integer, List<Integer>> map = new HashMap<>();
queue.add(new QueueNode(root, 0));
int min = 0, max = 0;
while (!queue.isEmpty()) {
TreeNode cur = queue.peek().node;
int depth = queue.poll().depth;
if (!map.containsKey(depth))
map.put(depth, new ArrayList<>());
map.get(depth).add(cur.val);
min = Math.min(min, depth);
max = Math.max(max, depth);
if (cur.left != null)
queue.add(new QueueNode(cur.left, depth - 1));
if (cur.right != null)
queue.add(new QueueNode(cur.right, depth + 1));
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = min; i <= max; i ++)
ans.add(map.get(i));
return ans;
}Level Order traverse but without queue
- LeetCode 116 - Populating Next Right Pointers in Each Node
public void connect(TreeLinkNode root) { if(root==null) return; TreeLinkNode cur = root; TreeLinkNode nextLeftmost = null; while(cur.left!=null){ nextLeftmost = cur.left; // save the start of next level while(cur!=null){ cur.left.next=cur.right; cur.right.next = cur.next==null? null : cur.next.left; cur=cur.next; } cur=nextLeftmost; // point to next level } }
Two(multi) ended bfs
BFS - Unusual
bfs on matrix or indexes on 2 strings
LeetCode 847 - Shortest Path Visiting All Nodes
- BFS: visited = new boolean[n][1 << n], queue stores node and all visied nodes
- BFS: dist = new int[1<<N][N] stores the step
- dp
public int shortestPathLength(int[][] graph) { int n = graph.length; Queue<int[]> queue = new LinkedList<>(); boolean[][] visited = new boolean[n][1 << n]; for (int i = 0; i < n; i++) { queue.offer(new int[]{i, 1 << i}); visited[i][1 << i] = true; } int target = (1 << n) - 1; int step = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int[] curr = queue.poll(); int pos = curr[0], state = curr[1]; for (int neigh : graph[pos]) { int nextState = state | (1 << neigh); if (nextState == target) { return step + 1; } if (visited[neigh][nextState]) { continue; } visited[neigh][nextState] = true; queue.offer(new int[]{neigh, state | (1 << neigh)}); } } step++; } return -1; }LeetCode 97 - Interleaving String: whether s3 is formed by the interleaving of s1 and s2
- dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
- bfs on matrix formed from 2 string
public boolean isInterleave(String s1, String s2, String s3) { if (s1.length() + s2.length() != s3.length()) return false; boolean[][] visited = new boolean[s1.length() + 1][s2.length() + 1]; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); while (!queue.isEmpty()) { int[] p = queue.poll(); if (visited[p[0]][p[1]]) continue; if (p[0] == s1.length() && p[1] == s2.length()) return true; if (p[0] < s1.length() && s1.charAt(p[0]) == s3.charAt(p[0] + p[1])) queue.offer(new int[]{p[0] + 1, p[1]}); if (p[1] < s2.length() && s2.charAt(p[1]) == s3.charAt(p[0] + p[1])) queue.offer(new int[]{p[0], p[1] + 1}); visited[p[0]][p[1]] = true; } return false; }
Put same levels into next level queue
- LeetCode 364 - Nested List Weight Sum II
- two types: integer or NestedInteger
- dfs(List
nestedList, int intSum) - find max depth first
- bfs
Topological sort(BFS)
- indegree, outdegree,
- Remove the leaves, update the degrees of inner vertexes
PriorityQueue + BFS
- Dijkstra single source shortest path
- time complexity: O(ElogV)
Dijkstra
- The completed vertices: visited vertices that have already been removed from the queue.
- The frontier: visited vertices on the queue
- The unvisited vertices: everything else
- If new distance is cheaper in cost, add it again to the queue(don’t remove the old one) ##### LeetCode 778 - Swim in Rising Water
- find a path whose max is minimum
- PQ+BFS: O(N^2logN)
- Bisection + use bfs/dfs to validate
- Bisection + use union find to validate
LeetCode 407 - Trapping Rain Water II
- from the borders, pick the shortest cell visited and check its neighbors:
- if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped add all its neighbors to the queue.
LeetCode 364 - Nested List Weight Sum II
LeetCode 743 - Network Delay Time
LeetCode 787 - Cheapest Flights Within K Stops
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Map<Integer, Map<Integer, Integer>> prices = new HashMap<>();
for (int[] f : flights) {
if (!prices.containsKey(f[0]))
prices.put(f[0], new HashMap<>());
prices.get(f[0]).put(f[1], f[2]);
}
Queue<int[]> pq = new PriorityQueue<>((a, b) -> (Integer.compare(a[0], b[0])));
pq.add(new int[] { 0, src, k + 1 });
while (!pq.isEmpty()) {
int[] top = pq.remove();
int price = top[0];
int city = top[1];
int stops = top[2];
if (city == dst)
return price;
if (stops > 0) {
Map<Integer, Integer> adj = prices.getOrDefault(city, new HashMap<>());
for (int a : adj.keySet()) {
pq.add(new int[] { price + adj.get(a), a, stops - 1 });
}
}
}
return -1;
}Bellman Ford
- F(V, L) = min [over all neighbors N of V] (F(N, L-1) + edge_cost(N, V))
- can handle and detect negative weight edges
- time complexity: O(VE)
int V, E;
Edge edge[];
void BellmanFord(Graph graph,int src)
{
int V = graph.V, E = graph.E;
int dist[] = new int[V];
for (int i=0; i<V; ++i)
dist[i] = Integer.MAX_VALUE;
dist[src] = 0;
for (int i=1; i<V; ++i)
{
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u]!=Integer.MAX_VALUE &&
dist[u]+weight<dist[v])
dist[v]=dist[u]+weight;
}
}
for (int j=0; j<E; ++j)
{
int u = graph.edge[j].src;
int v = graph.edge[j].dest;
int weight = graph.edge[j].weight;
if (dist[u] != Integer.MAX_VALUE &&
dist[u]+weight < dist[v])
System.out.println("Graph contains negative weight cycle");
}
printArr(dist, V);
}BFS + Bit mask
- LeetCode 864 - Shortest Path to Get All Keys
- Status:{int keyStatus, i,j}; int[][][] dist = new int[1 << 6][rows][cols]
- if (key == success) return path;
BFS + Digit
- [LeetCode 967 - Numbers With Same Consecutive Differences]
- LeetCode 688 - Knight Probability in Chessboard
- Return the probability that the knight remains on the board after it has stopped moving
- bfs: slow and mLE
- bfs: use map to compress - same as dp
- dfs+cache or dp
Jumping Window + Fixed Size
- LeetCode 683 - K Empty Slots
- sliding window: find a match when i reaches end of current window
- [O(kn) brute force]
- TreeSet: lower/higher
- Bucket
public int kEmptySlots(int[] flowers, int k) { int[] days = new int[flowers.length]; for (int i = 0; i < flowers.length; i++) days[flowers[i] - 1] = i + 1; int left = 0, right = k + 1, result = Integer.MAX_VALUE; for (int i = 0; right < days.length; i++) { if (days[i] < days[left] || days[i] <= days[right]) { if (i == right) result = Math.min(result, Math.max(days[left], days[right])); left = i; right = k + 1 + i; } } return (result == Integer.MAX_VALUE) ? -1 : result; }
