Introduction
Graphs are probably the most important topic to understand. They are the most generic problems that can be inspired from real life contexts. When given any problem, one of the first questions you should think of is: can I model this using a graph? Once you model a problem using a graph, you reduce the problem to the tools we can use to approach graph problems, such as SSSP, (single source shortest path) BFS, DFS, etc.
Graphs are simple, just a list of vertices and edges. Imagine the vertices as 'nodes' and edges are pairs of vertices that indicate that vertex a and vertex b are 'connected'. This implies a graph forms an entity network of connections. Some examples of interpreting/modelling a graph: social networks, (vertex = friends, connection = friendship) maps, (vertex = city, connection = road) or even more abstract like dependency chains. (vertex = system, edge = dependency)
Common use cases of graphs: find shortest path from node x to node y, (don't just think of this as simply distance or time, can manifest into many abstract concepts.) is it possible to take these courses in order and graduate, (topological order) or cycle detection.
There a few types, undirected vs directed means are the edges pointed in both directions or a single direction. (undirected examples mean you can travel from both a->b and b->a, such as a road in both directions. Or maybe marriages imply both a loves b and b loves a. Directed examples might include course prerequisites, only course a requires course b in order to take a, not vice versa. Or a one-way street.)
Also, weighted and unweighted. A weighted graph means all edges have a number associated with it. Maybe it represents the time or distance it takes for a car to travel from city a to city b. Or the cost in $ for that trip. Unweighted means all edges have a weight of 1.
Four Main Concepts:
- BFS - Graph traversal algorithm. Iterative. In unweighted graphs, it gives you the shortest path from node a to all other nodes.
- DFS - Graph traversal algorithm. Recursive. Nice for recursive structures, such as trees. Not really used for shortest path, mainly for connectivity checks.
- Topological sort - Produces an ordering of nodes in a linear chain such that there is no backwards edge from a node later in the chain to a node earlier in the chain. If such an ordering exists, that means you can process all nodes in that order without running into any dependency problems. (think about course prerequisite scheduling) Similar to BFS.
- Dijkstra's - Shortest paths in non-negative weighted graphs.
There are many others, but they aren't as important to know: MST (Prims, Kruskals), SCC (Tarjans), Euler Tour, Union Find, 0-1 BFS (we cover this).
Graph Setup
Before diving into algorithms, you need to know how to set up graphs in code.
Undirected Graphs
adjList = defaultdict(list)
for u,v in edges:
adjList[u].append(v)
adjList[v].append(u)Directed Graphs
adjList = defaultdict(list)
for u,v in edges:
adjList[u].append(v)Weighted Undirected Graphs
adjList = defaultdict(list)
for u,v,w in edges:
adjList[u].append((v,w))
adjList[v].append((u,w))Weighted Directed Graphs
adjList = defaultdict(list)
for u,v,w in edges:
adjList[u].append((v,w))Grids
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
m,n = len(grid), len(grid[0])
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < nBFS (Breadth First Search)
BFS stands for breadth first search. Intuitively, imagine expanding outwards from the source node, layer by layer. Think of something like the inside of a rose. Each 'level/layer' of the bfs refers to the shortest number of edges to reach that node. So if a node is processed on level 3, the number of edges from the source node of the bfs to that node is 3 edges. We use a deque so we can popleft containing the nodes currently being processed. We process level by level. If the node is the goal, or we reach some termination condition, we stop. We then do a visited check. Last, we always consider the neighbours, and append them if we satisfy some condition to the queue, to process them on the next level.
When we need some graph traversal algorithm to explore and find certain nodes, we can use BFS or DFS. When we require shortest path to nodes in an undirected graph, you should use BFS, DFS by default won't work as you can visit a node for the first time using a non-direct path. Coupled with the fact that it is easier to debug BFS because it is iterative rather than recursive, I generally recommend coding BFS if you have the option. It is less prone to bugs in an interview where time and correctness are crucial. But it is important to know both BFS and DFS, as being able to solve the same problem in multiple approaches is what separates a hire from a strong hire in an interview. (DFS is often fewer lines of code, so if you are more comfortable with recursion it can save some time)
O(n+m) time and O(n) space. N = number of nodes, M = number of edges. Note, that adjList is O(n+m) time and space to construct.
O(n+m)O(n)BFS Template
def bfs(i,j):
q = deque([node])
visited = set()
level = 0
while q:
for _ in range(len(q)):
node = q.popleft()
if node == goal: return level
if node in visited: continue
visited.add(node)
for nbr in adjList[node]:
if isXYZ(nbr):
q.append(nbr)
level += 1DFS (Depth First Search)
DFS stands for depth first search. This is how you would search a maze. You go all the way down a path, and backtrack up when you reach the end. If you recall from trees, the pre-order, in-order, post-order traversals were all forms of dfs.
A trick for dfs problems, is to carefully define the recursion. Does your dfs return something, or not return something but modify some global state like res? If you have a careful definition or invariant for what dfs() does, you can abstract it and easily use it in your logic.
First our base case of the recursion is if the node is already visited or invalid, we stop the recursion. (recursions must always have a base case) Otherwise, add to visited. Now we simply process all neighbours recursively.
O(n+m) time and O(n) space. (recursive stack space is worst case all n nodes in the case of a linear graph)
O(n+m)O(n)DFS Template
def dfs(node):
if node in visited or invalid:
return
visited.add(node)
for nbr in adjList[node]:
dfs(nbr)Basic BFS/DFS Problems
Classic problems demonstrating BFS and DFS traversal patterns.
01Number of IslandsMedium
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
# BFS Solution
def numIslands(self, grid: List[List[str]]) -> int:
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
m,n = len(grid), len(grid[0])
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
def bfs(i,j):
q = deque([(i,j)])
while q:
for _ in range(len(q)):
i,j = q.popleft()
grid[i][j] = -1
for x,y in dirs:
ii,jj = i+x,j+y
if isInBounds(ii,jj) and grid[ii][jj] == '1':
q.append((ii,jj))
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
res += 1
bfs(i, j)
return res
# DFS Solution
def numIslands(self, grid: List[List[str]]) -> int:
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
m,n = len(grid), len(grid[0])
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
def dfs(i, j):
if not isInBounds(i,j) or grid[i][j] != '1':
return
grid[i][j] = -1 # mark visited
for x,y in dirs:
dfs(i + x, j + y)
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
res += 1
dfs(i, j)
return resO(m*n)O(m*n)BFS will TLE, (prefer dfs solution in this case) but this works. As you can see we leverage the bfs template: instead of maintaining a visited set we can simply set the grid[i][j] as -1, and instead of adjlist for neighbours for grid graph problems we can simply use a directions array. (what would a diagonals dirs look like, or one that could move in the direction of knights on a chess board?) It is also common to have an isInBounds() function.
We still need to iterate over the grid, and run BFS for all 1's. Note that we will only run bfs once for each island, because for each island we will visit all neighbouring 1's in that island, and set them to -1. We skip 0's as well.
02Clone GraphMedium
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
# BFS Solution
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node: return None
node_map = {node: Node(node.val)}
q = deque([node])
visited = set()
while q:
curr = q.popleft()
if curr in visited: continue
visited.add(curr)
for nbr in curr.neighbors:
if nbr not in node_map:
node_map[nbr] = Node(nbr.val)
node_map[curr].neighbors.append(node_map[nbr])
q.append(nbr)
return node_map[node]
# DFS Solution
def cloneGraph(self, node: 'Node') -> 'Node':
old_to_new = {}
def dfs(n):
if n in old_to_new:
return old_to_new[n]
clone = Node(n.val)
old_to_new[n] = clone
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node) if node else NoneO(n+m)O(n)This is similar to the clone linked list question. Basically we need a map from old nodes to new nodes. We use BFS to traverse the graph, and if this is neighbour is an old node we haven't created a new node for yet, we create it and update the map. We then update the current new nodes neighbour with the new node of that neighbour.
Try to compare with the DFS solution. Why must we initialize the dict with the source node in bfs, but not in dfs? Because in bfs, we need to add the new neighbouring node. If we add the current node to the map we won't have access to the neighbour node in the map, so we have to initialize the map with the source and add neighbouring nodes to the map. Another nice thing about the dfs solution, is that we are using the map as the visited set as well! Ie. if the node is in the map, it was definitely visited before. Think about what dfs(node) means, it returns the new node of the given 'node' in the new graph, so we can use it recursively clone.neighbors.append(dfs(neighbor))
03Remove Invalid ParenthesesHard
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.
def removeInvalidParentheses(self, s: str) -> List[str]:
def isValid(s):
stack = 0 # count of opening paren
for c in s:
if c == '(':
stack += 1
elif c == ')':
if stack == 0: return False
stack -= 1
else:
continue
return stack == 0
visited = set()
q = deque([s])
while q:
res = []
for _ in range(len(q)):
curr = q.popleft()
if curr in visited: continue
visited.add(curr)
if isValid(curr):
res.append(curr)
for i in range(len(curr)): # remove curr[i]
q.append(curr[:i] + curr[i+1:])
if res: return res
return [-1]O(2^n)O(2^n)Refer to the parenthesis chapter for the isValid() function. This question seems difficult, but it actually can be solved with a straightforward brute force bfs. The hint to use BFS is in the 'minimum number of removals', because when bfs reaches a node, it is guaranteed to be at the shortest distance. The interesting part is we can model each node in this graph as a string of parenthesis, and we make edges between strings if you can reach the other by removing a parenthesis. The idea is given the original string, we brute force try removing all parenthesis in a bfs manner, until we find the level where there is a valid parenthesis string, and then return all valid parenthesis strings on that level.
04Evaluate DivisionMedium
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
# BFS Solution
def calcEquation(self, equations: List[List[str]], values: List[float],
queries: List[List[str]]) -> List[float]:
graph = defaultdict(list)
# Build the graph
for (a, b), val in zip(equations, values):
graph[a].append((b, val))
graph[b].append((a, 1 / val))
def bfs(start, end):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0
queue = deque([(start, 1.0)])
visited = set()
while queue:
node, curr_product = queue.popleft()
if node == end: return curr_product
if node in visited: continue
visited.add(node)
for neighbor, value in graph[node]:
new_product = curr_product * value
queue.append((neighbor, new_product))
return -1.0
# Process all queries
return [bfs(x, y) for x, y in queries]
# DFS Solution
def calcEquation(self, equations, values, queries):
graph = defaultdict(dict)
# Step 1: Build the graph
for (a, b), val in zip(equations, values):
graph[a][b] = val
graph[b][a] = 1 / val
def dfs(start, end, visited):
if start not in graph or end not in graph:
return -1.0
if start == end:
return 1.0
visited.add(start)
for neighbor, weight in graph[start].items():
if neighbor in visited: continue
res = dfs(neighbor, end, visited)
if res != -1.0:
return weight * res
return -1.0
# Step 2: Evaluate each query
result = []
for x, y in queries:
result.append(dfs(x, y, set()))
return resultO(Q * (V + E))O(V + E)We run a BFS/DFS for each query, where each node in the graph represents a variable, and a directed edge from A -> B has weight A / B. With this construction, we have that a path from A to B to C represents: A / C = (A / B) * (B / C), WHEN we multiply the edges together!
Just make sure that A -> B has weight values[i], and so B -> A has weight 1 / values[i]. We can use any graph traversal algorithm to find a path from X to Y. Try to compare the bfs and dfs solutions!
05The MazeMedium
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, return true if the ball can stop at the destination, otherwise return false.
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
m, n = len(maze), len(maze[0])
visited = [[False]*n for _ in range(m)]
queue = deque([tuple(start)])
directions = [(-1,0), (1,0), (0,-1), (0,1)] # up, down, left, right
while queue:
x, y = queue.popleft()
if [x, y] == destination:
return True
if visited[x][y]:
continue
visited[x][y] = True
for dx, dy in directions:
nx, ny = x, y
# Roll in the current direction until hitting a wall
while 0 <= nx+dx < m and 0 <= ny+dy < n and maze[nx+dx][ny+dy] == 0:
nx += dx
ny += dy
# Only add stopping point if not visited
if not visited[nx][ny]:
queue.append((nx, ny))
return FalseO(m*n)O(m*n)Standard BFS. DFS also works here.
06Number of Connected Components in an Undirected GraphMedium
You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.
Return the number of connected components in the graph.
def countComponents(self, n: int, edges: List[List[int]]) -> int:
adjList = defaultdict(list)
for u,v in edges:
adjList[u].append(v)
adjList[v].append(u)
visited = set()
ccs = []
def dfs(i, cc):
if i in visited: return
visited.add(i)
cc.append(i)
for nbr in adjList[i]:
dfs(nbr, cc)
for i in range(n):
if i in visited: continue
cc = []
dfs(i, cc)
ccs.append(cc)
return len(ccs)O(n+m)O(n+m)This is actually a really important concept to know. Connected component is basically like an island.
07Minimum Genetic MutationMedium
A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.
Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.
There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.
Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.
def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
bank_set = set(bank)
if endGene not in bank_set:
return -1
q = deque([(startGene, 0)])
genes = ['A', 'C', 'G', 'T']
while q:
gene, steps = q.popleft()
if gene == endGene:
return steps
for i in range(len(gene)):
for c in genes:
if gene[i] == c:
continue
mutated = gene[:i] + c + gene[i+1:]
if mutated in bank_set:
q.append((mutated, steps + 1))
bank_set.remove(mutated) # Mark as visited
return -1O(n * L * 4)O(n)This is just brute force BFS. We try all mutations from our given state string.
Bitmask BFS
Sometimes we need to track additional state in our BFS, such as which items we've collected. When the number of items is small (up to ~20), we can use a bitmask to efficiently represent this state.
Practice: Word Ladder I and II. (127, 126)
01Minimum Moves to Clean the ClassroomHard
Given a classroom grid with litter (L), energy restore points (R), obstacles (X), and a start position (S), find the minimum moves to collect all litter.
def minMoves(self, classroom: List[str], energy: int) -> int:
m,n = len(classroom), len(classroom[0])
q = deque()
count_litter = 0
litter_bitmask = 0
litter_map = defaultdict(int) # (i,j) -> index of litter
for i in range(m):
for j in range(n):
if classroom[i][j] == 'L':
litter_bitmask |= 1 << count_litter
litter_map[(i,j)] = count_litter
count_litter += 1
if count_litter == 0: return 0
visited = defaultdict(lambda: -inf)
for i in range(m):
for j in range(n):
if classroom[i][j] == 'S':
visited[(i,j,litter_bitmask)] = energy
q.append((i,j,energy, litter_bitmask))
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
level = 0
while q:
for _ in range(len(q)):
i,j,e,litter_bitmask= q.popleft()
litter_remaining = litter_bitmask.bit_count()
if litter_remaining == 0: return level
for x,y in dirs:
ii,jj = i+x,j+y
if not isInBounds(ii,jj) or classroom[ii][jj] == 'X': continue
can_collect_litter = classroom[ii][jj] == 'L' and (1 << litter_map[(ii,jj)]) & litter_bitmask > 0
can_restore_energy = classroom[ii][jj] == 'R'
if e-1 < 0: continue
e_ = energy if can_restore_energy else e-1
if visited[(ii,jj,litter_bitmask)] >= e_: continue
visited[(ii,jj,litter_bitmask)] = e_
q.append((ii,jj, e_, litter_bitmask ^ (1 << litter_map[(ii,jj)]) if can_collect_litter else litter_bitmask))
level += 1
return -1O(m*n*2^L*E)O(m*n*2^L)Since L is up to 10, we can use a bitmask. We use this as an efficient way to track which litters we have already picked up as part of our state in the BFS. Note we also need a litter map from (i,j) -> index of the litter, in order to determine which bit in our litter bitmask represents the current litter. Our state is: (i,j,e, litter_bitmask, level), ie. the current location i,j, the current energy e, the litter we have remaining, and level represents the number of moves to reach this state. We use XOR (^) to flip a 1 bit to 0, indicating we have collected this litter.
The visited set is actually a dictionary mapping (i,j,litter_bitmask) to the maximum energy required to reach this triple. We do not need level, because if we re-visit this (i,j,litter_bitmask) state with a higher level, it is redundant. Also, by removing energy <= 50 from the tuple we save a lot of time/space in visited. This is possible, because if we reach (i,j,litter_bitmask) with a lower energy, it is a greedily suboptimal state.
Multi-source BFS
There are cases when we want to start our bfs queue with multiple sources, and expand outwards from all of them in parallel.
BFS Practice: 909. Snakes and Ladders
01Rotting OrangesMedium
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Step 1: Initialize queue with all rotten oranges
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # (row, col, time)
elif grid[r][c] == 1:
fresh += 1
# Step 2: BFS to rot adjacent fresh oranges
time = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
r, c, t = queue.popleft()
time = t
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # Rot it
fresh -= 1
queue.append((nr, nc, t + 1))
return time if fresh == 0 else -1O(m*n)O(m*n)Clearly, we want to simulate the process by starting at all rotten oranges and rotting the fresh ones. Because we want the minimum number of moves, this process is best simulated via BFS.
02Shortest Distance from All BuildingsHard
You are given an m x n grid grid of values 0, 1, or 2, where:
- each 0 marks an empty land that you can pass by freely,
- each 1 marks a building that you cannot pass through, and
- each 2 marks an obstacle that you cannot pass through.
You want to build a house on an empty land that reaches all buildings in the shortest total travel distance.
Return the shortest travel distance for such a house. If it is not possible to build such a house according to the above rules, return -1.
def shortestDistance(self, grid):
if not grid or not grid[0]:
return -1
m, n = len(grid), len(grid[0])
totalDist = [[0] * n for _ in range(m)]
reach = [[0] * n for _ in range(m)]
buildingCount = sum(cell == 1 for row in grid for cell in row)
def bfs(start_i, start_j):
visited = [[False] * n for _ in range(m)]
q = deque([(start_i, start_j, 0)])
visited[start_i][start_j] = True
while q:
i, j, dist = q.popleft()
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
ni, nj = i + dx, j + dy
if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj] and grid[ni][nj] == 0:
visited[ni][nj] = True
totalDist[ni][nj] += dist + 1
reach[ni][nj] += 1
q.append((ni, nj, dist + 1))
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
bfs(i, j)
result = float('inf')
for i in range(m):
for j in range(n):
if grid[i][j] == 0 and reach[i][j] == buildingCount:
result = min(result, totalDist[i][j])
return result if result != float('inf') else -1O(B * m * n)O(m*n)This is pretty interesting. The naive solution of BFS from every empty land cell to all the buildings is too slow and will TLE. We can reverse the problem, let's BFS from every building and update the min distance to every empty land cell. We maintain totalDist for this, as well as reach array representing how many buildings can be reached by this land cell. After the BFS, we collect the optimal empty.
DFS Focused Problems
Problems that are particularly well-suited for DFS solutions.
01All Paths From Source to TargetMedium
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i.
# just dfs. since this is a DAG -> cache works!
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
@cache
def dfs(i): # returns a list of all paths from i to n-1.
if i == len(graph)-1:
return [[i]]
res = []
for nbr in graph[i]:
for nbr_path in dfs(nbr):
res.append([i] + nbr_path)
return res
return dfs(0)O(2^n * n)O(2^n * n)Honestly DP and dfs are very similar. For DAG's, I would argue they are identical. (if there are cycles in a graph, DP won't work…)
Just define the dp definition, the base case, and think about how to use the recursive call dfs(nbr) to create the current output.
02Keys and RoomsMedium
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
# dfs. visited
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = set()
def dfs(room):
if room in visited: return
visited.add(room)
for key in rooms[room]:
dfs(key)
dfs(0)
return len(visited) == len(rooms)O(n + k)O(n)Very simple.
03Number of ProvincesMedium
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
visited = set()
def dfs(city):
for neighbor in range(n):
if isConnected[city][neighbor] == 1 and neighbor not in visited:
visited.add(neighbor)
dfs(neighbor)
provinces = 0
for city in range(n):
if city not in visited:
visited.add(city)
dfs(city)
provinces += 1
return provincesO(n^2)O(n)This is the same as the connected components question.
Islands Theme
A collection of problems involving island-based graph traversal on grids.
01Maximum Number of Fish in a GridMedium
You are given a 0-indexed 2D matrix grid of size m x n, where (r, c) represents:
- A land cell if grid[r][c] = 0, or
- A water cell containing grid[r][c] fish, if grid[r][c] > 0.
A fisher can start at any water cell (r, c) and can do the following operations any number of times:
- Catch all the fish at cell (r, c), or
- Move to any adjacent water cell.
Return the maximum number of fish the fisher can catch if he chooses his starting cell optimally, or 0 if no water cell exists.
def findMaxFish(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
def dfs(i,j):
if not (0 <= i < m and 0 <= j < n) or grid[i][j] == 0: return 0
tmp = grid[i][j]
grid[i][j] = 0 # mark visited
return tmp + sum(dfs(i+x,j+y) for x,y in [(0,1),(1,0),(-1,0),(0,-1)])
return max(dfs(i,j) for i in range(m) for j in range(n))O(m*n)O(m*n)Pretty standard dfs. We basically want the sum of values in each island, and return the max sum island.
02Max Area of IslandMedium
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m,n,res = len(grid), len(grid[0]), 0
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
def dfs(i,j):
if not (0 <= i < m and 0 <= j < n) or grid[i][j] == 0: return 0
grid[i][j] = 0
return 1 + sum(dfs(i+x,j+y) for x,y in dirs)
return max(dfs(i,j) for i in range(m) for j in range(n))O(m*n)O(m*n)Almost exact same problem as above, except we want the size of the island instead of sum of values in the island.
03Count Sub IslandsMedium
You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.
An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.
Return the number of islands in grid2 that are considered sub-islands.
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
dirs = [(0,1),(1,0),(-1,0), (0,-1)]
m,n = len(grid1), len(grid1[0])
def dfs(i, j):
if not (0 <= i < m and 0 <= j < n) or grid2[i][j] != 1: return True
grid2[i][j] = 0
return all([dfs(i+x,j+y) for x,y in dirs]) and grid1[i][j] == 1
return sum(dfs(i,j) for i in range(m) for j in range(n) if grid2[i][j] == 1)O(m*n)O(m*n)Very similar to previous problems. DFS on islands in grid2, and check if grid1 is a super-set island. Note that we have to run dfs for all neighbours in grid2, even if we already know grid1[i][j] != 1. This is because we have to mark this whole island in grid2 as invalid, otherwise we will overcount.
04Pacific Atlantic Water FlowMedium
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
if not heights or not heights[0]:
return []
m, n = len(heights), len(heights[0])
pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]
def dfs(r, c, visited, prevHeight):
if (r < 0 or r >= m or c < 0 or c >= n or
visited[r][c] or heights[r][c] < prevHeight):
return
visited[r][c] = True
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for i in range(m):
dfs(i, 0, pacific, heights[i][0])
dfs(i, n-1, atlantic, heights[i][n-1])
for j in range(n):
dfs(0, j, pacific, heights[0][j])
dfs(m-1, j, atlantic, heights[m-1][j])
res = []
for i in range(m):
for j in range(n):
if pacific[i][j] and atlantic[i][j]:
res.append([i, j])
return resO(m*n)O(m*n)This is an interesting problem. This is kinda similar to trapping rain water 2. The idea is we reverse the problem, instead of dfs from the land, we dfs from the water. We 'hill climb', trying to ascend up from the oceans and marking those hills as land which will flow down to the ocean. If we are ever lower than the previous height, we terminate, as water will collect in this valley and not reach the ocean. Any land cell that is both visited from the pacific and atlantic oceans are feasible.
05Making A Large IslandHard
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
color = 2
area_map = {}
def dfs(x, y, color):
if x < 0 or x >= n or y < 0 or y >= n or grid[x][y] != 1:
return 0
grid[x][y] = color
area = 1
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
area += dfs(x + dx, y + dy, color)
return area
# First pass: color each island and store its area
for i in range(n):
for j in range(n):
if grid[i][j] == 1:
area_map[color] = dfs(i, j, color)
color += 1
max_area = max(area_map.values(), default=0)
has_zero = False
# Second pass: try flipping each 0 to 1
for i in range(n):
for j in range(n):
if grid[i][j] == 0:
has_zero = True
seen = set()
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i + dx, j + dy
if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] > 1:
seen.add(grid[ni][nj])
max_area = max(max_area, 1 + sum(area_map[c] for c in seen))
return max_area if has_zero else n * nO(n^2)O(n^2)Idea: colour each island a certain number. Create a map: colour num -> area of island. At every 0, do 1 + area of unique adjacent islands. Take maximum. O(n^2) time, O(n^2) space for dfs stack. Actually pretty straightforward. Watch out for edge case of no 0's in the grid.
06Surrounded RegionsMedium
You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:
- Connect: A cell is connected to adjacent cells horizontally or vertically.
- Region: To form a region connect every 'O' cell.
- Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.
To capture a surrounded region, replace all 'O's with 'X's in-place within the original board.
def solve(self, board: List[List[str]]) -> None:
if not board or not board[0]:
return
m, n = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != 'O':
return
board[r][c] = 'E' # Mark as escaped
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
# Mark border-connected 'O's
for i in range(m):
if board[i][0] == 'O':
dfs(i, 0)
if board[i][n-1] == 'O':
dfs(i, n-1)
for j in range(n):
if board[0][j] == 'O':
dfs(0, j)
if board[m-1][j] == 'O':
dfs(m-1, j)
# Flip surrounded 'O' -> 'X', and escaped 'E' -> 'O'
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'E':
board[i][j] = 'O'O(m*n)O(m*n)Key Insight: Only 'O's not connected to the border should be flipped. So we mark the border-connected ones first, and flip the rest. Just DFS from border O's, and mark them. All remaining O's can be surrounded to become 'X'. Now, we just need to flip the marked border connected O's back to O.
07Number of Distinct IslandsMedium
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.
Return the number of distinct islands.
def numDistinctIslands(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
seen = set()
def dfs(r, c, direction, path):
if 0 <= r < m and 0 <= c < n and grid[r][c] == 1:
grid[r][c] = 0
path.append(direction)
dfs(r + 1, c, 'D', path)
dfs(r - 1, c, 'U', path)
dfs(r, c + 1, 'R', path)
dfs(r, c - 1, 'L', path)
path.append('B') # Backtrack marker
shapes = set()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
path = []
dfs(i, j, 'S', path) # S = Start
shapes.add(tuple(path))
return len(shapes)O(m*n)O(m*n)Key Idea: We use DFS to record the path signature of each island starting from a fixed point (S for Start), marking movement directions (D, U, R, L), and using B for backtracking to ensure shapes with different traversal structures are distinguishable. This ensures only translation-equivalent shapes are treated the same.
State-Space BFS
Some shortest path problems require BFS over an expanded state, not just over graph nodes. Bitmasks are a common way to encode which requirements have already been satisfied.
01Shortest Path Visiting All NodesHard
You have an undirected, connected graph of n nodes. Return the length of the shortest path that visits every node. You may start and stop at any node, revisit nodes, and reuse edges.
def shortestPathLength(self, graph):
n = len(graph)
target = (1 << n) - 1
q = deque((node, 1 << node) for node in range(n))
seen = set(q)
steps = 0
while q:
for _ in range(len(q)):
node, mask = q.popleft()
if mask == target:
return steps
for nei in graph[node]:
state = (nei, mask | (1 << nei))
if state not in seen:
seen.add(state)
q.append(state)
steps += 1
return -1O(2^n * n^2)O(2^n * n)The BFS state is (current node, visited-node bitmask). Once the bitmask contains every node, the current BFS level is the shortest path length.
Topological Sort
DAG is a directed acyclic graph. DAG's are important, because we can only do dp on DAG's. As well, it can be shown that a graph is a DAG is equivalent to when a graph has a topological ordering.
We can use 'Kahn's Algorithm' to determine whether a graph has a topological ordering. The high level idea is similar to BFS. We start from all nodes with indegree 0, (source nodes) and append them as possible starts of the topological ordering. In doing so, we consider removing the node from the graph. As we do this, we remove all edges involving this node as well, so for all neighbouring nodes we need to decrement their indegree count. And only when these neighbouring nodes have indegree 0 (effectively new source nodes) do we append them to the queue. In this layer by layer traversal you can imagine slowly constructing the topological ordering. When a node has indegree of 0, it clearly can be the next node in the topological ordering, as all previous nodes that had edges towards that node are already in the topological ordering, before it. All nodes x with indegree > 0 may not be considered in the topological ordering yet, because they have some node y that points to it, and so if we place x immediately and y after it, there will be that directed edge y -> x that invalidates the topological ordering.
Note that 'indegree' of x refers to how many directed edges point into node x. Similarly, outdegree refers to how many directed edges point outwards from node x. Ie. (1,2) means indegree[2] = 1, and outdegree[1] = 1.
01Course ScheduleMedium
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
# Kahn's top sort algorithm
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adjList = defaultdict(list)
indegree = [0] * numCourses
for u,v in prerequisites:
adjList[v].append(u)
indegree[u] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
top_order = []
while q:
u = q.popleft()
top_order.append(u)
for nbr in adjList[u]:
indegree[nbr] -= 1
if indegree[nbr] == 0:
q.append(nbr)
return len(top_order) == numCoursesO(V + E)O(V + E)So we construct the directed graph, and indegree array, and initialize the queue as all nodes with indegree 0. We perform bfs. (note that we dont need to iterate for _ in range(len(q)), because we don't necessarily care about the number of levels/layers in the bfs. We can just iterate over each node in the queue) We pop and append the current source node with indegree 0 to the topological order, and consider the neighbours. We decrement indegree and if it becomes a new source, we append to queue. When this bfs is over, if all nodes became sources with indegree 0, this means we have a full, valid topological ordering. This is when len(top_order) == numCourses. (the size of the list is equal to all nodes in the graph)
02Course Schedule IIMedium
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adjList = defaultdict(list)
indegree = [0] * numCourses
for u,v in prerequisites:
adjList[v].append(u)
indegree[u] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
top_order = []
while q:
u = q.popleft()
top_order.append(u)
for nbr in adjList[u]:
indegree[nbr] -= 1
if indegree[nbr] == 0:
q.append(nbr)
return top_order if len(top_order) == numCourses else []O(V + E)O(V + E)This is exactly the same, but instead of a boolean we want to return the topological ordering.
03Course Schedule IVMedium
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course ai first if you want to take course bi.
Prerequisites can also be indirect. If course a is a prerequisite of course b, and course b is a prerequisite of course c, then course a is a prerequisite of course c.
You are also given an array queries where queries[j] = [uj, vj]. For the jth query, you should answer whether course uj is a prerequisite of course vj or not.
Return a boolean array answer, where answer[j] is the answer to the jth query.
def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
pre_reqs = [set() for _ in range(n)]
indegree = defaultdict(int)
adjList = defaultdict(list)
for u,v in prerequisites:
indegree[v] += 1
adjList[u].append(v)
q = deque([i for i in range(n) if indegree[i] == 0]) # sources
while q:
curr = q.popleft()
for nbr in adjList[curr]:
pre_reqs[nbr] |= pre_reqs[curr] | set([curr])
indegree[nbr] -= 1
if indegree[nbr] == 0: q.append(nbr)
return [u in pre_reqs[v] for u,v in queries]O(V^2 + E + Q)O(V^2)This is the same but we need to maintain a list of sets pre_reqs, that contains all pre-req nodes. This is pretty easily updated by the relation: pre_reqs[nbr] |= pre_reqs[curr] | set([curr])
04Alien DictionaryHard
There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.
You are given a list of strings words from the alien language's dictionary. Now it is claimed that the strings in words are sorted lexicographically by the rules of this new language.
If this claim is incorrect, and the given arrangement of string in words cannot correspond to any order of letters, return "".
Otherwise, return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there are multiple solutions, return any of them.
from collections import defaultdict, deque
def alienOrder(self, words):
# Step 1: Initialize graph
graph = defaultdict(set)
in_degree = {char: 0 for word in words for char in word}
# Step 2: Build the graph
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
min_len = min(len(w1), len(w2))
if w1[:min_len] == w2[:min_len] and len(w1) > len(w2):
return "" # Invalid order
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in graph[c1]:
graph[c1].add(c2)
in_degree[c2] += 1
break
# Step 3: Topological sort using BFS
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
char = queue.popleft()
result.append(char)
for neighbor in graph[char]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) < len(in_degree):
return "" # Cycle detected
return "".join(result)O(C)O(1)This is an interesting application for topological sort. It can be tricky to realize we can model this problem as a graph. The intuition is that dictionary ordering can be described as enforcing a graph relationship. For example, the alphabetical ordering of 'abcdef'...' can be represented as a graph of 26 nodes for each letter, with directed edges from a->b, b->c, and so on, meaning that a comes before b… Note that a comes before c, but we don't need a direct edge connecting a->c, since we get that relationship transitively from a->b and b->c. This will improve our efficiency from O(letters^2) to O(letters).
You want to think about the regular english language. When comparing two words, how do you tell if one comes later than the other in the dictionary? You compare letter by letter left to right. At the first difference, the word with the earlier letter comes earlier. If there is no difference, but one is longer, the shorter one comes earlier. We just need to simulate this process, and at the first difference, (a != b) we know that this character a is earlier than the other character b causes the word to be ordered before the other one. So there must be the edge a -> b in this alien dictionary.
You may be asking, why not use Counter() or defaultdict(int) for in_degree? It's generally better to concretely define in_degree for all nodes in the graph, otherwise the queue can be empty, because the keys are not in there.
05Find Eventual Safe StatesMedium
There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
# 1. reverse edges + kahn's top sort
# O(n+m) time and space.
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
rgraph = defaultdict(list)
n = len(graph)
indegree = defaultdict(int) # this is after reversal. ie. outdegree of original graph
for i in range(n):
for nbr in graph[i]:
rgraph[nbr].append(i)
indegree[i] += 1
q = deque([i for i in range(n) if indegree[i] == 0])
safe = set()
while q:
curr = q.popleft()
# add to safe since it is terminal
safe.add(curr)
for nbr in rgraph[curr]:
indegree[nbr] -= 1
if indegree[nbr] == 0: q.append(nbr)
return [i for i in range(n) if i in safe]O(V + E)O(V + E)To solve the problem, we must first consider when a node is safe or unsafe. If we begin at any node and proceed along any path from that node, we will eventually reach either a terminal node or enter a cycle and continue to loop in it without ever reaching a terminal node.
Basically there's cycles that will not lead to a terminal node. If this was a dag answer is every node. We basically just have every node, except the ones in the cycles.
- Reverse edges. Then do top sort. Intuition: start from terminal nodes like 5,6. Visit the nodes that point to them (ex. 2,4). If removing that edge we travelled on makes 2,4 terminal nodes, 2,4 MUST be safe. Continue this.
Basically think of it recursively. Safe nodes are defined recursively. Base case are terminal nodes. Terminal nodes are trivially safe. Consider the nodes that point to terminal nodes. Ignoring those edges, if the node has no more outgoing edges (it is now terminal) it must be safe. Constructs the safe nodes level by level, starting from terminal nodes.
Interesting problem, showcasing how we sometimes need to think in reverse.
Dijkstra's Algorithm
Imagine we want the shortest path in a non-negative weighted graph between start and all other nodes. (if there are negative weights, dijkstras wont work) The idea is to start at the start node. The invariant is that when we first process a node, it will be at its shortest path. We maintain the current minimum distance from start to node i in array d. Of course, d[start] = 0. We maintain a min heap of pairs (min_dist_to_node_curr, node_curr). At each iteration, we pop the min dist path from the heap. We consider all neighbouring nodes to start, and if using this minimum path from start to the current node + this edge w we get a shorter path to nbr than our previous best path d[nbr], we update d[nbr] and add this to the min heap. We need to have a d[curr] < dist visited check, so if we already processed this node with a shorter path there is no reason to process it for a longer path.
The output is the array d, which contains the shortest weighted path from start to all other nodes i.
The high level intuition is to imagine a cloud where every node in the cloud we have already processed their minimum paths. The cloud starts with just start. When we process a new node for the first time, it is newly added to the cloud. What would invalidate this algorithms correctness, is if there was a better path to some node i through a node X not in the cloud. (ie. a path from start to A -> X -> i, where A is the last node in the cloud) But basically because we pop the min path each time from the min heap, this path from start to A -> X must have length >= the min path we computed for node i. And because there are no negative path weights, this total path from start to A -> X -> i has weight >= the min path computed by our algorithm from start to i – so it's impossible for it to be better.
Dijkstra's is fairly similar to dp, so it is commonly applicable for problems that sound like dp. In general, when you are looking for shortest paths from a node to all other nodes in a graph – dijkstra's is a good option.
O((m+n)logn) time. (O(m + nlogn) using fibonacci heap) O(n+m) space. For every edge and node, we could add it to the heap. Each heappop/push is O(logn) time. (ie. the heap has size at most m+n)
O((m+n)log n)O(n+m)Dijkstra's Template
def dijkstra(self, n: int, edges: List[List[int]], start: int, end: int) -> float:
heap = [(0, start)] # min heap
adjList = defaultdict(list)
for u,v,w in edges:
adjList[u].append((v,w))
adjList[v].append((u,w))
d = [inf] * n
d[start] = 0
while heap:
dist, curr = heappop(heap)
if d[curr] < dist: continue # no point, already visited a shorter path through curr.
assert(d[curr] == dist)
for nbr,w in adjList[curr]:
if dist + w < d[nbr]:
d[nbr] = dist + w
heappush(heap, (dist + w, nbr))
return d01Network Delay TimeMedium
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
dist = [float('inf')] * (n + 1)
dist[k] = 0
min_heap = [(0, k)] # (time, node)
while min_heap:
time, u = heapq.heappop(min_heap)
if time > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(min_heap, (dist[v], v))
max_dist = max(dist[1:])
return max_dist if max_dist < float('inf') else -1O((V+E)log V)O(V+E)This is literally the template.
02Cheapest Flights Within K StopsMedium
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
# Dijkstra with extra dimension
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = defaultdict(list)
for u, v, cost in flights:
graph[u].append((v, cost))
# dp[node][stops] = min cost to reach node with stops
dp = [[float('inf')] * (k + 2) for _ in range(n)]
dp[src][0] = 0
# (cost, node, stops)
heap = [(0, src, 0)]
while heap:
cost, node, stops = heapq.heappop(heap)
if node == dst:
return cost
if stops > k:
continue
for nei, price in graph[node]:
new_cost = cost + price
if new_cost < dp[nei][stops + 1]:
dp[nei][stops + 1] = new_cost
heapq.heappush(heap, (new_cost, nei, stops + 1))
return -1
# Alternative: DP solution
def findCheapestPrice(self, n, flights, src, dst, k):
graph = defaultdict(list)
for u, v, cost in flights:
graph[u].append((v, cost))
@cache
def dp(city, stops_remaining):
if city == dst:
return 0
if stops_remaining < 0:
return float('inf')
min_cost = float('inf')
for nei, price in graph[city]:
min_cost = min(min_cost, price + dp(nei, stops_remaining - 1))
return min_cost
ans = dp(src, k)
return -1 if ans == float('inf') else ansO(E * K * log(V * K))O(V * K)Pretty standard problem, we just need another dimension to our distance array to keep track of how many stops we have. Note that 'stops' in our array is actually the number of edges in the path. But the number of 'stop's' is the number of nodes in the path except the start and end, so it's actually the number of edges -1. This is why we need up to index k+2 in the array.
Compare this with the straightforward dp solution.
03Minimum Path SumMedium
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
# DP Solution (more efficient)
def minPathSum(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
@cache
def dp(i,j):
if not (0 <= i < m) or not (0 <= j < n): return float('inf')
rem = min(dp(i+1,j), dp(i,j+1))
return grid[i][j] + (rem if rem != float('inf') else 0)
return dp(0,0)
# Dijkstra's Solution
def minPathSum(self, grid):
m, n = len(grid), len(grid[0])
dist = [[float('inf')] * n for _ in range(m)]
dist[0][0] = grid[0][0]
heap = [(grid[0][0], 0, 0)] # (cost, row, col)
directions = [(1, 0), (0, 1)] # down, right
while heap:
cost, i, j = heapq.heappop(heap)
if (i, j) == (m - 1, n - 1):
return cost
if cost > dist[i][j]:
continue
for dx, dy in directions:
ni, nj = i + dx, j + dy
if 0 <= ni < m and 0 <= nj < n:
new_cost = cost + grid[ni][nj]
if new_cost < dist[ni][nj]:
dist[ni][nj] = new_cost
heapq.heappush(heap, (new_cost, ni, nj))O(m*n)O(m*n)DP is actually more efficient since there is no log factor, but I include both so you can compare. Very standard problem.
04Path with Maximum ProbabilityMedium
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
If there is no path from start to end, return 0.
# dijkstra
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
heap = [(-1, start)] # max heap
adjList = defaultdict(list)
for (u,v),w in zip(edges, succProb):
adjList[u].append((v,w))
adjList[v].append((u,w))
p = defaultdict(int)
p[start] = 1 # all other p[i] are init to 0, as desired.
while heap:
prob, curr = heappop(heap)
prob = - prob
if curr == end: return prob
if p[curr] > prob: continue # no point, already visited a larger prob path through curr.
assert(p[curr] == prob)
for nbr,w in adjList[curr]:
if prob * w > p[nbr]:
p[nbr] = prob * w
heappush(heap, (- p[nbr], nbr))
return 0O((V+E)log V)O(V+E)Pretty standard, just know that we are instead using max path, and we continue the path through multiplication rather than addition of weights.
But wait, dijkstras only works for min paths? You are right. If you use dijkstras to find max paths, it won't work because that is NP complete. The only reason this works is because it is multiplication rather than addition. Let's explain:
Let's say the optimal path P = p1*...*pk
Since log(x) is mono increasing, max P has the same max path as max log(P), and max P is the same as min -logP.
Property of log gives: -logP = -logp1 - …. - logpk.
This means, max P is the same as min the sum of -log of the edge weights. Also, since 0 <= pi <= 1, that means log(pi) <= 0 and -log(pi) >= 0, so we have non-negative edge weights.
What this means, is dijkstras will find the max path P on the -log of the edge weights. We note that we don't take the log of the edge weights in the code, because we showed that the max P problem is the same as min -logP, meaning it is correct, and we can use either approach to solve this problem.
05Path With Maximum Minimum ValueMedium
Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions.
The score of a path is the minimum value in that path.
For example, the score of the path 8 → 4 → 5 → 9 is 4.
# Dijkstra-inspired greedy
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
heap = [(-grid[0][0], 0, 0)]
dirs = [(0,1), (0,-1), (1,0), (-1,0)]
visited = set()
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
while heap:
min_val, i, j = heappop(heap)
min_val = - min_val
if (i,j) == (m-1,n-1): return min_val
if (i,j) in visited: continue
visited.add((i,j))
for x,y in dirs:
ii = i + x
jj = j + y
if isInBounds(ii,jj):
heappush(heap, (- min(min_val, grid[ii][jj]), ii, jj))
return -1
# Binary search + DFS approach
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
dirs = [(0,1), (0,-1), (1,0), (-1,0)]
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
@cache
def dp(i,j, lim):
if not isInBounds(i,j): return False
if grid[i][j] < lim: return False
if (i,j) == (m-1, n-1):
return True
if (i,j) in visited: return False
visited.add((i,j))
return any(dp(i+x,j+y, lim) for x,y in dirs)
l,r = min(v for row in grid for v in row), max(v for row in grid for v in row)
while l < r:
MID = ceil(l + (r-l)/2)
visited = set()
if dp(0, 0, MID):
l = MID
else:
r = MID - 1
return lO(m*n*log(m*n))O(m*n)If you look at the first greedy solution, it actually isn't technically dijkstra's because there is no relaxation step. (d[curr] > dist + w: d[curr] = dist + w) But it is inspired by dijkstra's, and we can add it in if we want, and the proof of correctness is similar. The reason it works is subtle. It's because we are keeping the min value on the heap. So imagine the cloud. The reason it can't work for max paths, is because there could be a really low cost edge out of the cloud, and then a huge cost edge back into the cloud. But in this case, if we go out of the cloud using a low edge, and then back in using a large edge, the min cost of that path is still at most the path we just popped from the max heap.
I also included a dp + binary search approach that is straightforward, by fixing the min path value.
06Path With Minimum EffortMedium
You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
# Binary search approach
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m,n = len(heights),len(heights[0])
l,r = 0, max(max(h) for h in heights) - min(min(h) for h in heights)
dirs = [(0,1),(1,0),(-1,0),(0,-1)]
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
def dfs(i,j,k): # do a dfs/bfs. only move along edges if abs diff is <= k
if (i,j) == (m-1,n-1): return True
if (i,j) in visited: return False
visited.add((i,j))
return any(dfs(i+x,j+y,k) for x,y in dirs if isInBounds(i+x,j+y) and abs(heights[i][j] - heights[i+x][j+y]) <= k)
while l < r:
mid = l+(r-l)//2
visited = set()
if dfs(0,0,mid):
r = mid
else:
l = mid + 1
return l
# Dijkstra's approach
def minimumEffortPath(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
heap = [(0, 0, 0)]
dirs = [(0,1), (0,-1), (1,0), (-1,0)]
visited = set()
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
while heap:
effort, i, j = heappop(heap)
if (i,j) == (m-1,n-1):
return effort
if (i,j) in visited: continue
visited.add((i,j))
for x,y in dirs:
ii = i + x
jj = j + y
if isInBounds(ii,jj):
heappush(heap, (max(effort, abs(grid[ii][jj] - grid[i][j])), ii, jj))
return -1O(m*n*log(max_height))O(m*n)Really similar problem to before. Except we want the min max abs adjacent difference path. This clearly will work with dijkstras because we are taking the min path.
07The Maze IIMedium
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball's start position and the destination, return the shortest distance for the ball to stop at the destination. If the ball cannot stop at destination, return -1.
The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
m, n = len(maze), len(maze[0])
dist = [[float('inf')] * n for _ in range(m)]
dist[start[0]][start[1]] = 0
heap = [(0, start[0], start[1])] # (distance, x, y)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
while heap:
d, x, y = heapq.heappop(heap)
if [x, y] == destination:
return d
if d > dist[x][y]:
continue
for dx, dy in directions:
nx, ny, steps = x, y, 0
# roll the ball until it hits a wall
while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:
nx += dx
ny += dy
steps += 1
if d + steps < dist[nx][ny]:
dist[nx][ny] = d + steps
heapq.heappush(heap, (d + steps, nx, ny))
return -1O(m*n*log(m*n))O(m*n)Very standard.
08Trapping Rain Water IIHard
Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.
def trapRainWater(self, A: List[List[int]]) -> int:
m,n = len(A), len(A[0])
heap = []
border = set()
for i in range(m):
for j in range(n):
if i in [0, m-1] or j in [0, n-1]:
border.add((i,j))
heappush(heap, (A[i][j], i, j))
dirs = [(0,1),(1,0),(-1,0),(0,-1)]
def isInBounds(i,j):
return 0 <= i < m and 0 <= j < n
res = 0
d = [[inf for _ in range(n)] for _ in range(m)]
while heap:
max_height_so_far, i, j = heappop(heap)
if d[i][j] < max_height_so_far: continue
for x,y in dirs:
ii,jj = i+x,j+y
if isInBounds(ii,jj) and (ii,jj) not in border and (dd := max(max_height_so_far, A[ii][jj])) < d[ii][jj]:
d[ii][jj] = dd
res += max(0, max_height_so_far - A[ii][jj])
heappush(heap, (dd, ii, jj))
return resO(m*n*log(m*n))O(m*n)This is actually a really clever usage of dijkstras. Inspired by trapping rain water I, where we needed to min max_prefix, max_suffix paths, here we need the min max values for all paths from the border to that cell.
Basically, for each single cell, we need to know that for all the possible paths to the outside world (where the water will escape to), what is the minimum of all path's weight, and the path's weight should be defined as the highest height value along the path.
The naive approach is to just consider the 4 directions, up, left, down, right in terms of max prefix paths. However, this doesn't work because water paths may zigzag. Imagine water flowing on the grid from the sky, water will flow from the borders and collect in the valleys. For a particular valley/cell, we want to consider all possible paths water could have flowed from the border, and for each path, consider their max height that they encountered on that path and take the minimum max height over all possible paths. This determines the height of the trapped water for this cell, and we simply need to subtract from the height of this cell to get the trapped water amount.
How can we implement finding the minimum max height path out of all paths to reach a certain node? This is precisely what dijkstra's gives us. Dijkstra's guarantees the first time we reach a node, it is with the minimum path.
Guidance: It's a good idea for all problems where you think dijkstra's is applicable, to quickly think about that cloud proof and that counterexample case for 30s-1minute. This will show the interviewer you are rigorous with correctness and not just purely intuitive. Also, this will give you the confidence to invest time into implementing the approach.
0-1 BFS
This is an optimization to dijkstra when the edges are just 0 and 1, so we don't suffer the log(n) factor of using a priority queue.
The idea is simple - just use a regular deque. If the edge is 0, we append left. If the edge is 1, we append right. We always popleft(). This basically simulates exactly what a priority queue would do, in O(1) time, as we ensure the deque always looks like [0,0,...,1,1].
TLDR: in any case where you are using dijkstra's on a graph with only 0 or 1 edge weights, it is more optimal to actually use 0-1 BFS.
Practice: 499. The Maze III, 1928. Minimum Cost to Reach Destination in Time, 3341. Find Minimum Time to Reach Last Room I
Later: Union Find: 1061. Lexicographically Smallest Equivalent String
01Grid Teleportation TraversalMedium
You are given a 2D character grid matrix of size m x n, where matrix[i][j] represents the cell at the intersection of the ith row and jth column. Each cell is one of the following:
- '.' representing an empty cell.
- '#' representing an obstacle.
- An uppercase letter ('A'-'Z') representing a teleportation portal.
You start at the top-left cell (0, 0), and your goal is to reach the bottom-right cell (m - 1, n - 1). You can move from the current cell to any adjacent cell (up, down, left, right) as long as the destination cell is within the grid bounds and is not an obstacle.
If you step on a cell containing a portal letter and you haven't used that portal letter before, you may instantly teleport to any other cell in the grid with the same letter. This teleportation does not count as a move, but each portal letter can be used at most once during your journey.
Return the minimum number of moves required to reach the bottom-right cell. If it is not possible to reach the destination, return -1.
# 0-1 BFS Solution
def minMoves(self, matrix: List[str]) -> int:
m, n = len(matrix), len(matrix[0])
# Collect all portal positions
portals = defaultdict(list)
for i in range(m):
for j in range(n):
c = matrix[i][j]
if 'A' <= c <= 'Z':
portals[c].append((i, j))
# dist[i][j] = best known #moves to reach (i,j)
INF = 10**18
dist = [[INF]*n for _ in range(m)]
dist[0][0] = 0
used = [False]*26 # used[ord(c)-ord('A')] == True once we've teleported via c
dq = deque([(0, 0)])
while dq:
x, y = dq.popleft()
d = dist[x][y]
# If we reached the goal, we're done
if x == m-1 and y == n-1:
return d
# 1) Teleport (cost = 0) — do this first so zero-cost edges are expanded immediately
c = matrix[x][y]
if 'A' <= c <= 'Z':
idx = ord(c) - ord('A')
if not used[idx]:
used[idx] = True
for tx, ty in portals[c]:
if dist[tx][ty] > d:
dist[tx][ty] = d
dq.appendleft((tx, ty))
# 2) Regular moves (cost = 1)
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x+dx, y+dy
if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != '#':
if dist[nx][ny] > d+1:
dist[nx][ny] = d+1
dq.append((nx, ny))
# If unreachable
return -1
# Dijkstra's Solution for comparison
def minMoves(self, matrix: List[str]) -> int:
m, n = len(matrix), len(matrix[0])
# Map each portal letter to its list of positions
portals = defaultdict(list)
for i in range(m):
for j in range(n):
c = matrix[i][j]
if 'A' <= c <= 'Z':
portals[c].append((i, j))
# Distance matrix initialized to "infinite"
INF = float('inf')
dist = [[INF] * n for _ in range(m)]
dist[0][0] = 0
# Track which portal letters have been used for teleport
used_portal = [False] * 26
# Min-heap for Dijkstra: (cost_so_far, x, y)
heap = [(0, 0, 0)]
while heap:
d, x, y = heapq.heappop(heap)
# If we've already found a better way here, skip
if d > dist[x][y]:
continue
# If we reached the target, return the cost
if x == m - 1 and y == n - 1:
return d
# 1) Teleport edges (cost 0)
c = matrix[x][y]
if 'A' <= c <= 'Z':
idx = ord(c) - ord('A')
if not used_portal[idx]:
used_portal[idx] = True
for tx, ty in portals[c]:
if dist[tx][ty] > d:
dist[tx][ty] = d
heapq.heappush(heap, (d, tx, ty))
# 2) Regular adjacent moves (cost 1)
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != '#':
nd = d + 1
if dist[nx][ny] > nd:
dist[nx][ny] = nd
heapq.heappush(heap, (nd, nx, ny))
# If destination is unreachable
return -1O(m*n + P)O(m*n)Added the second dijkstras solution so you can compare.
The 0-1 BFS is pretty standard like I mentioned. The only interesting thing about this question is that we can teleport through portals that do not cost a move, so a 0 cost edge, otherwise moving is a 1 cost edge. And to keep track of which portals we have already used (we can use each at most once) we use a global array, instead of incorporating that into the state on the queue. This works, because think about how we greedily process the lowest cost path to reach the current node i every iteration. (ie. in dijkstra's) If we already used some letter, it doesn't make sense to save it for a later iteration, as that would achieve reaching the same node at a larger cost.
02Minimum Cost to Make at Least One Valid Path in a GridHard
Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:
- 1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
- 2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j - 1])
- 3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
- 4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i - 1][j])
You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1) following the signs on the grid. The valid path does not have to be the shortest.
You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.
Return the minimum cost to make the grid have at least one valid path.
# Dijkstra's approach
def minCost(self, grid: List[List[int]]) -> int:
dirs = [(0,1),(0,-1),(1,0),(-1,0)]
m,n = len(grid), len(grid[0])
pq = [(0,0,0)] # (cost, i,j)
def isInBounds(i,j):
return 0<=i<m and 0<=j<n
while pq:
cost, i,j = heappop(pq)
if grid[i][j] == -1: continue
tmp = grid[i][j]
grid[i][j] = -1
if (i,j) == (m-1,n-1): return cost
# 1/2. combine logic. follow/modify the arrow
for x,y in dirs:
i_,j_ = i+x,j+y
if isInBounds(i_,j_): heappush(pq, (cost+int((x,y) != dirs[tmp-1]), i_, j_))
return -1
# 0-1 BFS (more optimal)
def minCost(self, grid: List[List[int]]) -> int:
dq = deque([(0,0,0)])
while dq:
cost, i,j = dq.popleft()
if grid[i][j] == -1: continue
if (i,j) == ((m:=len(grid))-1,(n:=len(grid[0]))-1): return cost
for k,(x,y) in enumerate([(0,1),(0,-1),(1,0),(-1,0)]):
if 0<=(i_:=i+x)<m and 0<=(j_:=j+y)<n:
if k == grid[i][j]-1: # edge cost is 0, append left
dq.appendleft((cost, i_,j_))
else: # edge cost is 1, append right
dq.append((cost+1, i_,j_))
grid[i][j] = -1O(m*n)O(m*n)I actually don't know why this is a hard problem. It is just a standard dijkstra / 0-1 bfs solution. There are 2 cases, we either modify this cell (cost 1) to some other direction, or we keep the current direction of the arrow. (cost 0) This indicates 0-1 BFS.