NeetCode 150 · Graphs

Graphs Problems

DFS, BFS, topological sort, and Union-Find. Graphs appear in island problems, dependency ordering, and connected component questions.

Problems: 13
Easy: 0
Medium: 12
Hard: 1
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Medium ArrayDFSBFSUnion Find
Given binary grid of '1's (land) and '0's (water), count the number of islands.
Test Cases
numIslands([['1','1','1','1','0'],['1','1','0','1','0'],['1','1','0','0','0'],['0','0','0','0','0']]) → 1 numIslands([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]) → 3
DFS flood fillmark visited by mutationO(m·n)
For each unvisited '1', run DFS to mark all connected land cells as visited ('0'). Count how many times you start a DFS.
Python Solution
def numIslands(grid): rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r, c): if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1': return grid[r][c] = '0' # mark visited dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1) for r in range(rows): for c in range(cols): if grid[r][c] == '1': dfs(r, c) count += 1 return count
Key idea: DFS flood fill. When we find a '1', increment the count and flood-fill it (marking all connected '1's as '0') so we don't count them again.
Time: O(m·n).
Space: O(m·n) worst case recursion.
02 Medium DFSBFSGraphHash Map
Given a reference to a node in a connected undirected graph, return a deep copy of the graph.
Test Cases
# Node has .val and .neighbors list # Input: node representing graph [[2,4],[1,3],[2,4],[1,3]] # Output: deep copy with same adjacency
BFSold→new mapO(V+E)
Use a hash map from old node to new node. BFS/DFS to traverse; create new nodes on first visit, link neighbors using the map.
Python Solution
from collections import deque class Node: def __init__(self, val=0, neighbors=None): self.val = val self.neighbors = neighbors or [] def cloneGraph(node): if not node: return None clone_map = {node: Node(node.val)} queue = deque([node]) while queue: curr = queue.popleft() for neighbor in curr.neighbors: if neighbor not in clone_map: clone_map[neighbor] = Node(neighbor.val) queue.append(neighbor) clone_map[curr].neighbors.append(clone_map[neighbor]) return clone_map[node]
Key idea: BFS traversal. First visit: create a new node and store in the map. Every visit: link the cloned current node to the cloned neighbor using the map.
Time: O(V+E).
Space: O(V) for the map.
03 Medium ArrayDFSBFSUnion Find
Given binary integer grid (0=water, 1=land), find the maximum area of an island. Area = number of connected 1's.
Test Cases
maxAreaOfIsland([[0,0,1,0,0],[0,1,1,0,0],[0,0,0,1,1],[0,0,0,1,0]]) → 3
DFS countmark visitedO(m·n)
DFS from each unvisited '1'. Count cells visited in this DFS (the island area). Return the maximum area found.
Python Solution
def maxAreaOfIsland(grid): rows, cols = len(grid), len(grid[0]) def dfs(r, c): if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1: return 0 grid[r][c] = 0 # mark visited return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1) return max((dfs(r,c) for r in range(rows) for c in range(cols)), default=0)
Key idea: DFS returns the count of cells in the island. Mark cells as 0 to avoid revisiting. Take the max across all islands.
Time: O(m·n).
Space: O(m·n).
04 Medium ArrayDFSBFSMatrix
Rain water can flow to the Pacific (top/left borders) and Atlantic (bottom/right borders). Find cells from which water can reach both oceans.
Test Cases
pacificAtlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]) → [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
reverse BFS from bordersset intersectionO(m·n)
Reverse the problem: BFS from Pacific borders uphill — cells reachable going uphill from Pacific. Same for Atlantic. Answer = intersection.
Python Solution
from collections import deque def pacificAtlantic(heights): rows, cols = len(heights), len(heights[0]) def bfs(starts): visited = set(starts) queue = deque(starts) while queue: r, c = queue.popleft() for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc = r+dr, c+dc if (0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in visited and heights[nr][nc] >= heights[r][c]): visited.add((nr,nc)) queue.append((nr,nc)) return visited pacific_starts = [(r,0) for r in range(rows)] + [(0,c) for c in range(cols)] atlantic_starts = [(r,cols-1) for r in range(rows)] + [(rows-1,c) for c in range(cols)] return sorted(bfs(pacific_starts) & bfs(atlantic_starts))
Key idea: Instead of simulating flow downhill, BFS uphill from each ocean's borders. A cell is in the answer if water from it can reach both oceans — i.e., it's reachable (going uphill) from both borders.
Time: O(m·n).
Space: O(m·n).
05 Medium ArrayDFSBFSUnion Find
Given m×n board of 'X' and 'O', capture all regions of 'O' fully surrounded by 'X' (replace with 'X'). 'O' on borders or connected to border 'O' are NOT captured.
Test Cases
solve([['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]) → [['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]
DFS from borderssentinel 'S'O(m·n)
Mark all 'O's connected to the border as safe ('S'). Then flip remaining 'O' to 'X', and 'S' back to 'O'.
Python Solution
def solve(board): rows, cols = len(board), len(board[0]) def dfs(r, c): if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O': return board[r][c] = 'S' # safe — connected to border dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1) # Mark border-connected O's for r in range(rows): dfs(r, 0); dfs(r, cols-1) for c in range(cols): dfs(0, c); dfs(rows-1, c) # Flip: O→X (captured), S→O (safe) for r in range(rows): for c in range(cols): if board[r][c] == 'O': board[r][c] = 'X' elif board[r][c] == 'S': board[r][c] = 'O'
Key idea: Two-phase approach. First, mark all 'O's reachable from borders as 'S' (safe). Then, convert remaining 'O's to 'X' and restore 'S' to 'O'.
Time: O(m·n).
Space: O(m·n).
06 Medium ArrayBFSMatrix
Grid has 0 (empty), 1 (fresh), 2 (rotten). Each minute, rotten oranges make adjacent fresh ones rotten. Return minutes until no fresh oranges remain, or -1.
Test Cases
orangesRotting([[2,1,1],[1,1,0],[0,1,1]]) → 4 orangesRotting([[2,1,1],[0,1,1],[1,0,1]]) → -1 orangesRotting([[0,2]]) → 0
multi-source BFStrack fresh countO(m·n)
Start BFS from ALL rotten oranges simultaneously. Track fresh count — decrement as oranges rot. Answer is the time when fresh reaches 0.
Python Solution
from collections import deque def orangesRotting(grid): rows, cols = len(grid), len(grid[0]) queue = deque() fresh = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 2: queue.append((r, c, 0)) elif grid[r][c] == 1: fresh += 1 minutes = 0 while queue: r, c, t = queue.popleft() for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc = r+dr, c+dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 minutes = max(minutes, t + 1) queue.append((nr, nc, t + 1)) return minutes if fresh == 0 else -1
Key idea: Multi-source BFS seeded with all initial rotten oranges. As we spread, we track elapsed time per cell and count fresh oranges. If fresh reaches 0, return the max time seen.
Time: O(m·n).
Space: O(m·n).
07 Medium ArrayBFSMatrix
Fill each empty room in a grid with its distance to the nearest gate. Gates=0, Walls=-1, Empty=INF.
Test Cases
INF = 2147483647 rooms = [[INF,-1,0,INF],[INF,INF,INF,-1],[INF,-1,INF,-1],[0,-1,INF,INF]] wallsAndGates(rooms) → [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]
multi-source BFS from gatesdistance propagationO(m·n)
Start BFS from all gates simultaneously. For each reachable empty room, set distance = parent's distance + 1.
Python Solution
from collections import deque def wallsAndGates(rooms): rows, cols = len(rooms), len(rooms[0]) INF = 2147483647 queue = deque() for r in range(rows): for c in range(cols): if rooms[r][c] == 0: queue.append((r, c)) while queue: r, c = queue.popleft() for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc = r+dr, c+dc if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == INF: rooms[nr][nc] = rooms[r][c] + 1 queue.append((nr, nc))
Key idea: Multi-source BFS from all gates at once. Each BFS level represents one unit of distance. Fill rooms as we expand — this guarantees shortest distance from a gate.
Time: O(m·n).
Space: O(m·n).
08 Medium DFSBFSGraphTopological Sort
Given numCourses and list of [course, prerequisite] pairs, return True if you can finish all courses (i.e., no cycles exist).
Test Cases
canFinish(2, [[1,0]]) → True canFinish(2, [[1,0],[0,1]]) → False
Kahn's algorithmin-degreetopological sort
Build a directed graph. If a topological ordering exists (no cycles), return True. Use Kahn's algorithm: repeatedly process nodes with in-degree 0.
Python Solution
from collections import defaultdict, deque def canFinish(numCourses, prerequisites): graph = defaultdict(list) in_degree = [0] * numCourses for course, pre in prerequisites: graph[pre].append(course) in_degree[course] += 1 queue = deque(i for i in range(numCourses) if in_degree[i] == 0) count = 0 while queue: node = queue.popleft() count += 1 for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return count == numCourses
Key idea: Kahn's topological sort. Nodes with in-degree 0 have no prerequisites. Process them and reduce neighbors' in-degrees. If we process all nodes, there's no cycle.
Time: O(V+E).
Space: O(V+E).
09 Medium DFSBFSGraphTopological Sort
Return the order in which to finish all numCourses given prerequisites. Return empty array if impossible.
Test Cases
findOrder(2, [[1,0]]) → [0,1] findOrder(4, [[1,0],[2,0],[3,1],[3,2]]) → [0,2,1,3] or [0,1,2,3]
Kahn's with order listO(V+E)
Same as Course Schedule but also track the order nodes are processed. Return order if it equals numCourses.
Python Solution
from collections import defaultdict, deque def findOrder(numCourses, prerequisites): graph = defaultdict(list) in_degree = [0] * numCourses for course, pre in prerequisites: graph[pre].append(course) in_degree[course] += 1 queue = deque(i for i in range(numCourses) if in_degree[i] == 0) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return order if len(order) == numCourses else []
Key idea: Kahn's algorithm, same as Course Schedule, but also collect nodes in the order they're processed. That order is a valid topological sort.
Time: O(V+E).
Space: O(V+E).
10 Medium DFSBFSGraphUnion Find
Given graph that starts as a tree with one extra edge added, find and return that redundant edge.
Test Cases
findRedundantConnection([[1,2],[1,3],[2,3]]) → [2,3] findRedundantConnection([[1,2],[2,3],[3,4],[1,4],[1,5]]) → [1,4]
Union-Findpath compressionO(n α(n))
Use Union-Find. For each edge, try to union the two nodes. If they're already in the same component, this edge is the redundant one.
Python Solution
def findRedundantConnection(edges): parent = list(range(len(edges) + 1)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # path compression x = parent[x] return x def union(x, y): px, py = find(x), find(y) if px == py: return False # already connected — redundant edge parent[py] = px return True for u, v in edges: if not union(u, v): return [u, v]
Key idea: Union-Find with path compression. Process edges one by one. If both endpoints are already in the same component, the edge creates a cycle — it's the redundant one.
Time: O(n α(n)) ≈ O(n).
Space: O(n).
11 Medium DFSBFSGraphUnion Find
Given n nodes (0 to n-1) and edges list, return the number of connected components.
Test Cases
countComponents(5, [[0,1],[1,2],[3,4]]) → 2 countComponents(5, [[0,1],[1,2],[2,3],[3,4]]) → 1
Union-Findcomponents counterO(n α(n))
Use Union-Find. Start with n components. For each edge, if union succeeds (nodes were in different components), decrement component count.
Python Solution
def countComponents(n, edges): parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x, y): px, py = find(x), find(y) if px == py: return 0 parent[py] = px return 1 components = n for u, v in edges: components -= union(u, v) return components
Key idea: Start with n components (each node isolated). For each edge, union the endpoints. If they were in different components, decrement the count. The final count is the answer.
Time: O(n α(n)).
Space: O(n).
12 Medium DFSBFSGraphUnion Find
Given n nodes and edges, return True if the edges form a valid tree (connected + no cycles).
Test Cases
validTree(5, [[0,1],[0,2],[0,3],[1,4]]) → True validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]) → False
n-1 edges checkUnion-Find cycle detectionO(n)
A valid tree has exactly n-1 edges and no cycles. Check edge count first. Then use Union-Find to detect cycles.
Python Solution
def validTree(n, edges): if len(edges) != n - 1: return False # trees have exactly n-1 edges parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for u, v in edges: pu, pv = find(u), find(v) if pu == pv: return False # cycle detected parent[pv] = pu return True
Key idea: Two conditions for a valid tree: (1) exactly n-1 edges, (2) no cycles. Check condition 1 upfront. Use Union-Find for condition 2.
Time: O(n α(n)).
Space: O(n).
13 Hard BFSHash SetString
Given beginWord, endWord, and word list, find shortest transformation sequence length. Each step changes exactly one letter; each intermediate word must be in the list.
Test Cases
ladderLength('hit','cog',['hot','dot','dog','lot','log','cog']) → 5 ladderLength('hit','cog',['hot','dot','dog','lot','log']) → 0
BFStry all 26 lettersO(M·N·26)
BFS where each node is a word. From each word, generate all one-letter variations; if in the word set and unvisited, add to queue.
Python Solution
from collections import deque def ladderLength(beginWord, endWord, wordList): wordSet = set(wordList) if endWord not in wordSet: return 0 queue = deque([(beginWord, 1)]) visited = {beginWord} while queue: word, steps = queue.popleft() for i in range(len(word)): for ch in 'abcdefghijklmnopqrstuvwxyz': new_word = word[:i] + ch + word[i+1:] if new_word == endWord: return steps + 1 if new_word in wordSet and new_word not in visited: visited.add(new_word) queue.append((new_word, steps + 1)) return 0
Key idea: BFS on the implicit graph of words. Generate all one-letter mutations. If a mutation is in the word set and unvisited, add to queue. BFS guarantees the shortest path.
Time: O(M²·N) — M=word length, N=wordList size.
Space: O(M·N).
← Prev Category Next Category →