Graphs
A graph is dots (nodes) joined by lines (edges): cities and roads, people and friendships, courses and prerequisites. Grids are graphs too. You explore with DFS (go deep) or BFS (go ring by ring, which finds shortest paths) and a visited set so you never loop forever.
After this topic: You can model a problem as a graph, traverse grids and adjacency lists, order tasks with topological sort and group nodes with union-find.
Do these first: Backtracking
Step 1 · Read the lesson
Model relationships as nodes and edges; traverse with a visited set.
Step 2 · Solve the problems in order
Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.
Each island is one connected blob of land. How do you make sure you count a blob only once?
Scan the grid; on unseen land increment the count and flood-fill (DFS/BFS) the whole island, marking cells visited.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func numIslands(grid [][]byte) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Graphs: BFS / DFS / Topological Sort lesson page.
// NumIslands (LeetCode 200): every cell is a node, its 4 neighbours are the edges. // Each unvisited land cell starts a new island; DFS sinks the whole island. func NumIslands(grid [][]byte) int { count := 0 var sink func(r, c int) sink = func(r, c int) { if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[r]) || grid[r][c] != '1' { return } grid[r][c] = '0' // mark visited by overwriting (the grid is our visited set) sink(r+1, c) sink(r-1, c) sink(r, c+1) sink(r, c-1) } for r := range grid { for c := range grid[r] { if grid[r][c] == '1' { count++ sink(r, c) } } } return count }The same flood fill, but now it should report how big the blob was.
DFS returns 1 + the sizes of its four neighbours; track the maximum over all starting cells.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func maxAreaOfIsland(grid [][]int) intTested with go test. Try it yourself first, then compare.
// MaxAreaOfIsland: flood-fill each island and report its size. Sinking a visited cell (setting it to 0) // doubles as the "visited" mark. func MaxAreaOfIsland(grid [][]int) int { var area func(r, c int) int area = func(r, c int) int { if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] == 0 { return 0 } grid[r][c] = 0 return 1 + area(r+1, c) + area(r-1, c) + area(r, c+1) + area(r, c-1) } best := 0 for r := range grid { for c := range grid[r] { best = max(best, area(r, c)) } } return best }Cycles mean you will meet the same node again. How do you reuse the copy you already made?
Map original → clone. DFS: if node is in the map return its clone; else create it, store it, then clone all neighbours.
Target: O(V + E) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func cloneGraph(node *Node) *NodeTested with go test. Try it yourself first, then compare. It is explained step by step on the Graphs: BFS / DFS / Topological Sort lesson page.
// Node is the LeetCode graph node. type Node struct { Val int Neighbors []*Node } // CloneGraph (LeetCode 133): the map from old node to its copy is also the visited set. func CloneGraph(node *Node) *Node { if node == nil { return nil } copies := map[*Node]*Node{} var clone func(n *Node) *Node clone = func(n *Node) *Node { if c, ok := copies[n]; ok { return c } c := &Node{Val: n.Val} copies[n] = c // register BEFORE recursing, or cycles recurse forever for _, nb := range n.Neighbors { c.Neighbors = append(c.Neighbors, clone(nb)) } return c } return clone(node) }Instead of searching from every room to a gate, search from every gate outward at once.
Multi-source BFS: push all gates (distance 0) into the queue, expand to neighbouring empty rooms setting distance+1.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func wallsAndGates(rooms [][]int)Tested with go test. Try it yourself first, then compare.
// WallsAndGates fills every empty room (2147483647) with its distance to the nearest gate (0). Walls are -1. // Search from ALL gates at once: a multi-source BFS expands one ring per step, so the first time a room is // reached is by its nearest gate. func WallsAndGates(rooms [][]int) { const empty = 2147483647 type cell struct{ r, c int } var queue []cell for r := range rooms { for c := range rooms[r] { if rooms[r][c] == 0 { queue = append(queue, cell{r, c}) } } } for len(queue) > 0 { cur := queue[0] queue = queue[1:] for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} { r, c := cur.r+d[0], cur.c+d[1] if r >= 0 && c >= 0 && r < len(rooms) && c < len(rooms[0]) && rooms[r][c] == empty { rooms[r][c] = rooms[cur.r][cur.c] + 1 queue = append(queue, cell{r, c}) } } } }All rotten oranges spread at the same time. Each minute is one ring of spreading outward.
Multi-source BFS from all rotten oranges, counting layers; at the end if any fresh orange remains return −1.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func orangesRotting(grid [][]int) intTested with go test. Try it yourself first, then compare.
// OrangesRotting returns the minutes until no fresh orange is left, or -1 if one can never rot. // All rotten oranges spread at the same moment, so each BFS layer is one minute. func OrangesRotting(grid [][]int) int { type cell struct{ r, c int } var queue []cell fresh := 0 for r := range grid { for c := range grid[r] { switch grid[r][c] { case 2: queue = append(queue, cell{r, c}) case 1: fresh++ } } } minutes := 0 for len(queue) > 0 && fresh > 0 { minutes++ for size := len(queue); size > 0; size-- { // one layer = one minute cur := queue[0] queue = queue[1:] for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} { r, c := cur.r+d[0], cur.c+d[1] if r >= 0 && c >= 0 && r < len(grid) && c < len(grid[0]) && grid[r][c] == 1 { grid[r][c] = 2 fresh-- queue = append(queue, cell{r, c}) } } } } if fresh > 0 { return -1 } return minutes }Reverse the question: start from the oceans and go uphill.
DFS/BFS from all Pacific border cells to cells that are equal or higher; same for Atlantic; answer is the intersection.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func pacificAtlantic(heights [][]int) [][]intTested with go test. Try it yourself first, then compare.
// PacificAtlantic: instead of asking where each cell's water goes, start from each ocean's border and walk // UPHILL (to neighbours that are equal or higher). Cells reached from both oceans are the answer. func PacificAtlantic(heights [][]int) [][]int { rows, cols := len(heights), len(heights[0]) pacific, atlantic := make([][]bool, rows), make([][]bool, rows) for i := range pacific { pacific[i], atlantic[i] = make([]bool, cols), make([]bool, cols) } var climb func(seen [][]bool, r, c int) climb = func(seen [][]bool, r, c int) { seen[r][c] = true for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} { nr, nc := r+d[0], c+d[1] if nr >= 0 && nc >= 0 && nr < rows && nc < cols && !seen[nr][nc] && heights[nr][nc] >= heights[r][c] { climb(seen, nr, nc) } } } for r := 0; r < rows; r++ { climb(pacific, r, 0) climb(atlantic, r, cols-1) } for c := 0; c < cols; c++ { climb(pacific, 0, c) climb(atlantic, rows-1, c) } out := [][]int{} for r := 0; r < rows; r++ { for c := 0; c < cols; c++ { if pacific[r][c] && atlantic[r][c] { out = append(out, []int{r, c}) } } } return out }Which O cells are definitely safe? The ones touching the border and anything connected to them.
Flood-fill from border O cells marking them safe; then flip every remaining O to X and restore the safe ones.
Target: O(m·n) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func solve(board [][]byte)Tested with go test. Try it yourself first, then compare.
// Solve flips every 'O' region that is completely surrounded by 'X'. The regions that must NOT flip are the ones // touching the border, so mark those safe first ('S'), then flip what is left and restore the safe ones. func Solve(board [][]byte) { rows, cols := len(board), len(board[0]) var mark func(r, c int) mark = func(r, c int) { if r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] != 'O' { return } board[r][c] = 'S' mark(r+1, c) mark(r-1, c) mark(r, c+1) mark(r, c-1) } for r := 0; r < rows; r++ { mark(r, 0) mark(r, cols-1) } for c := 0; c < cols; c++ { mark(0, c) mark(rows-1, c) } for r := range board { for c := range board[r] { switch board[r][c] { case 'O': board[r][c] = 'X' // surrounded case 'S': board[r][c] = 'O' // touched the border: restore } } } }You can finish all courses exactly when the prerequisite graph has no cycle.
Topological sort (Kahn): count in-degrees, queue courses with 0, remove edges as you process; all processed ⇒ no cycle. (Or DFS with three colours.)
Target: O(V + E) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func canFinish(numCourses int, prerequisites [][]int) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Graphs: BFS / DFS / Topological Sort lesson page.
// CanFinish (LeetCode 207): Kahn's topological sort. prerequisites[i] = {course, mustTakeFirst}. // Repeatedly take courses with no unmet prerequisites; if some are never taken, there is a cycle. func CanFinish(numCourses int, prerequisites [][]int) bool { adj := make([][]int, numCourses) indegree := make([]int, numCourses) for _, p := range prerequisites { adj[p[1]] = append(adj[p[1]], p[0]) // edge: prerequisite -> course indegree[p[0]]++ } queue := []int{} for i, d := range indegree { if d == 0 { queue = append(queue, i) } } taken := 0 for len(queue) > 0 { node := queue[0] queue = queue[1:] taken++ for _, next := range adj[node] { indegree[next]-- if indegree[next] == 0 { queue = append(queue, next) } } } return taken == numCourses }Same detection as before — now record the order in which courses come out.
Kahn's algorithm and append each popped course; if fewer than n courses were output there is a cycle, return [].
Target: O(V + E) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func findOrder(numCourses int, prerequisites [][]int) []intTested with go test. Try it yourself first, then compare.
// FindOrder returns one valid order to take all courses, or nil if the prerequisites contain a cycle. // Kahn's algorithm: repeatedly take a course with no unmet prerequisites; if some courses can never be // taken, they sit on a cycle. func FindOrder(numCourses int, prerequisites [][]int) []int { after := make([][]int, numCourses) // after[a] = courses unlocked by a need := make([]int, numCourses) // number of unmet prerequisites for _, p := range prerequisites { after[p[1]] = append(after[p[1]], p[0]) need[p[0]]++ } var queue, order []int for c, n := range need { if n == 0 { queue = append(queue, c) } } for len(queue) > 0 { c := queue[0] queue = queue[1:] order = append(order, c) for _, next := range after[c] { if need[next]--; need[next] == 0 { queue = append(queue, next) } } } if len(order) != numCourses { return nil } return order }A tree has no cycles. Which edge is the first one that connects two nodes that are already connected?
Union-find: for each edge, if both endpoints already share a root that edge closes the cycle; otherwise union them.
Target: O(n α(n)) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func findRedundantConnection(edges [][]int) []intTested with go test. Try it yourself first, then compare. It is explained step by step on the Graphs: BFS / DFS / Topological Sort lesson page.
// FindRedundantConnection (LeetCode 684): the edge that closes a cycle in a graph that was a tree plus one extra edge. // The input has n nodes and n edges, so nodes 1..n fit in n+1 slots. If both ends are already connected, this edge makes the cycle. func FindRedundantConnection(edges [][]int) []int { u := NewUF(len(edges) + 1) // nodes are labelled 1..n for _, e := range edges { if !u.Union(e[0], e[1]) { return e } } return nil }Start with n separate groups. What happens to the count each time an edge joins two different groups?
Union-find: components = n; every successful union decrements it. (Or DFS and count the starts.)
Target: O(V + E) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func countComponents(n int, edges [][]int) intTested with go test. Try it yourself first, then compare. It is explained step by step on the Graphs: BFS / DFS / Topological Sort lesson page.
// CountComponents (LeetCode 323): number of connected components in an undirected graph of n nodes. func CountComponents(n int, edges [][]int) int { u := NewUF(n) for _, e := range edges { u.Union(e[0], e[1]) } return u.groups }A tree on n nodes has exactly n−1 edges and is fully connected.
Check edges == n−1, then confirm connectivity with DFS/BFS or that union-find never finds a cycle.
Target: O(V + E) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func validTree(n int, edges [][]int) boolTested with go test. Try it yourself first, then compare. It is explained step by step on the Graphs: BFS / DFS / Topological Sort lesson page.
// ValidTree (LeetCode 261): n nodes form a tree if there are exactly n-1 edges and no edge closes a cycle. func ValidTree(n int, edges [][]int) bool { if len(edges) != n-1 { return false } u := NewUF(n) for _, e := range edges { if !u.Union(e[0], e[1]) { return false } } return true }Words are nodes; two words are connected if they differ by one letter. You want the fewest hops.
BFS from beginWord, generating neighbours by changing one letter (or via wildcard buckets like h*t) that exist in the word set; the layer count is the answer.
Target: O(N · L²) time
Types such as ListNode, TreeNode and Node are already defined in the LeetCode editor.
func ladderLength(beginWord string, endWord string, wordList []string) intTested with go test. Try it yourself first, then compare.
// LadderLength: words are nodes, and two words are connected when they differ by one letter. // BFS from beginWord counts the fewest words in a transformation sequence. Neighbours are found by trying all // 26 letters in each position and keeping those in the word list; each word is removed once seen. func LadderLength(beginWord, endWord string, wordList []string) int { words := make(map[string]bool, len(wordList)) for _, w := range wordList { words[w] = true } if !words[endWord] { return 0 } queue := []string{beginWord} delete(words, beginWord) for steps := 1; len(queue) > 0; steps++ { for size := len(queue); size > 0; size-- { cur := queue[0] queue = queue[1:] if cur == endWord { return steps } b := []byte(cur) for i := range b { orig := b[i] for ch := byte('a'); ch <= 'z'; ch++ { b[i] = ch if next := string(b); words[next] { delete(words, next) // visited queue = append(queue, next) } } b[i] = orig } } } return 0 }