Graph Coding Problems: 107 Questions with Solutions
107 graph coding problems — 5 easy · 60 medium · 42 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 107
- By difficulty: 5 easy · 60 medium · 42 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Nodes and edges: build the adjacency list, then traverse it. These problems cover the representation choices (list, matrix, edge list), reachability and components, cycle detection in directed and undirected graphs, and the traversals that everything else is built on. Shortest paths and topological order have their own pages.
New to graph? Read the Graph Data Structure tutorial first.
How graph works, step by step
n = 5, edges = [[0,1], [0,2], [1,2], [1,3], [2,4], [3,4]]- An edge list names the joined pairs, but finding one node's neighbours would mean scanning all 6 edges. An adjacency list gives each of the 5 nodes its own list instead, filled in a single pass over the edges.
- Read edge 0–1: append 1 to adj[0], now [1], and 0 to adj[1], now [0]. The graph is undirected, so every edge is written twice, once from each end.
- Read edge 0–2: append 2 to adj[0], now [1, 2], and 0 to adj[2], now [0]. 2 had no neighbours until now; appending to the end of a list is O(1), however long it is.
- Read edge 1–2: append 2 to adj[1], now [0, 2], and 1 to adj[2], now [0, 1]. 1 and 2 were already linked through 1–0–2, so this edge closes a cycle; the lists still only record direct neighbours.
- Read edge 1–3: append 3 to adj[1], now [0, 2, 3], and 1 to adj[3], now [1]. A list's length is its node's degree: 1 now has 3 neighbours, while 3 gets its first.
- Read edge 2–4: append 4 to adj[2], now [0, 1, 4], and 2 to adj[4], now [2]. Only the two lists the edge names are touched, which is why the whole pass costs O(V + E).
- Read edge 3–4: append 4 to adj[3], now [1, 4], and 3 to adj[4], now [2, 3]. This closes a second cycle, 3–1–2–4–3, and is stored exactly like any other edge.
- All 6 edges are in, each stored twice, so the lists hold 12 entries: the degrees add up to 2E. Building took O(V + E), and now 1's neighbours are one lookup, adj[1] = [0, 2, 3], in O(degree) instead of an O(E) scan.
Graph study plan
14 of the 107 Graph problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 93 in the full list below are practice at your own pace. Then move on to Breadth-First Search.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Find Champion I Easy
- Keys and Rooms Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Number of Provinces Medium
- Course Schedule Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Course Schedule II Medium
- Redundant Connection Medium
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Graph: the essentials
When to reach for it
Anything with pairwise relationships — roads between cities, prerequisites, friendships, trust, network links — even when the word "graph" never appears. Inputs usually arrive as an edge list ([[u, v], …]) or an adjacency matrix. Before writing anything, settle three things: are edges directed, do they carry weights, and are nodes numbered from 0 or from 1?
The pattern
Convert to an adjacency list, then choose the traversal: Breadth-First Search for the fewest edges, depth-first search for reachability and structure, union-find when edges arrive one at a time and only connectivity matters. Some questions need no traversal at all: in Find the Town Judge, the judge is the node with in-degree n − 1 and out-degree 0.
def build(n, edges, directed=False):
adj = [[] for _ in range(n)] # nodes 0..n-1
for u, v in edges:
adj[u].append(v)
if not directed:
adj[v].append(u)
return adj
Cost
An adjacency list takes O(V + E) space and a full traversal O(V + E) time. An adjacency matrix takes O(V²) space and makes every traversal O(V²); it pays off only for dense graphs or constant-time edge checks.
Common mistakes
- Adding an undirected edge in one direction only.
- Missing isolated nodes: loop over
range(n), not over the nodes that appear in edges, when counting components. - Undirected cycle detection that treats the edge back to the parent as a cycle.
- Traversing from node 0 and assuming that reaches the whole graph.
Start with
- Find the Town Judge: degrees instead of a traversal.
- Find if Path Exists in Graph: build the list, then search.
- Is Graph Bipartite?: two-colouring every component.
All graph problems
Easy (5)
- Find Champion II
- Find Champion I Array, Matrix
- Find if Path Exists in Graph Union Find, Breadth-First Search
- Find the Town Judge Hash Table
- Find Center of Star Graph
Medium (60)
- Minimize Maximum Component Cost Binary Search, Union Find, Sorting
- Minimum Time for K Connected Components Binary Search, Union Find, Sorting
- Power Grid Maintenance Array, Hash Table, Depth-First Search
- Minimum Time to Reach Destination in Directed Graph Heap (Priority Queue), Shortest Path
- Unit Conversion I Depth-First Search, Breadth-First Search
- Digit Operations to Make Two Integers Equal Math, Heap (Priority Queue), Number Theory
- Find Minimum Time to Reach Last Room II Array, Heap (Priority Queue), Matrix
- Find Minimum Time to Reach Last Room I Array, Heap (Priority Queue), Matrix
- Remove Methods From Project Depth-First Search, Breadth-First Search
- Find a Safe Walk Through a Grid Array, Breadth-First Search, Heap (Priority Queue)
- Shortest Distance After Road Addition Queries I Array, Breadth-First Search
- Minimum Cost to Convert String I Array, String, Shortest Path
- Minimum Cost of a Path With Special Roads Array, Heap (Priority Queue), Shortest Path
- Validate Binary Tree Nodes Tree, Depth-First Search, Breadth-First Search
- Water Connection Problem Depth-First Search
- Minimum Spanning Tree Union Find, Minimum Spanning Tree, Greedy
- Floyd Warshall Dynamic Programming, Shortest Path
- Most Profitable Path in a Tree Array, Tree, Depth-First Search
- All Ancestors of a Node in a Directed Acyclic Graph Depth-First Search, Breadth-First Search, Topological Sort
- The Time When the Network Becomes Idle Array, Breadth-First Search
- Find the City With the Smallest Number of Neighbors at a Threshold Distance Shortest Path, Dynamic Programming
- Most Stones Removed with Same Row or Column Union Find, Depth-First Search
- The Celebrity Problem Array, Stack, Two Pointers
- Node With Highest Edge Score Hash Table
- Number of Ways to Arrive at Destination Dynamic Programming, Shortest Path, Topological Sort
- Course Schedule IV Topological Sort, Depth-First Search, Breadth-First Search
- Parallel Courses Topological Sort, Breadth-First Search
- Detonate the Maximum Bombs Array, Math, Depth-First Search
- The Maze II Array, Matrix, Breadth-First Search
- Loud and Rich Array, Topological Sort, Depth-First Search
- Shortest Path with Alternating Colors Breadth-First Search
- Number of Nodes in the Sub-Tree With the Same Label Hash Table, Tree, Depth-First Search
- Minimum Fuel Cost to Report to the Capital Tree, Depth-First Search, Breadth-First Search
- Maximum Star Sum of a Graph Array, Greedy, Sorting
- Count the Number of Complete Components Union Find, Depth-First Search, Breadth-First Search
- Minimum Score of a Path Between Two Cities Union Find, Depth-First Search, Breadth-First Search
- Reachable Nodes With Restrictions Array, Tree, Depth-First Search
- Minimum Swaps to Sort Array, Sorting
- Count Unreachable Pairs of Nodes in an Undirected Graph Depth-First Search, Breadth-First Search, Union Find
- Maximum Total Importance of Roads Greedy, Sorting, Heap
- Find Closest Node to Given Two Nodes Depth-First Search
- Maximal Network Rank
- Reorder Routes to Make All Paths Lead to the City Zero Depth-First Search, Breadth-First Search
- Possible Bipartition Depth-First Search, Breadth-First Search, Union Find
- Minimum Height Trees Depth-First Search, Breadth-First Search, Topological Sort
- Number of Operations to Make Network Connected Depth-First Search, Breadth-First Search, Union Find
- Minimum Number of Vertices to Reach All Nodes
- Find Eventual Safe States Depth-First Search, Breadth-First Search, Topological Sort
- All Paths From Source to Target Backtracking, Depth-First Search, Breadth-First Search
- Keys and Rooms Depth-First Search, Breadth-First Search
- Is Graph Bipartite? Depth-First Search, Breadth-First Search, Union Find
- Graph Valid Tree Depth-First Search, Breadth-First Search, Union Find
- Number of Connected Components in an Undirected Graph Depth-First Search, Breadth-First Search, Union Find
- Min Cost to Connect All Points Minimum Spanning Tree, Union Find
- Cheapest Flights Within K Stops Dynamic Programming, Shortest Path
- Network Delay Time Shortest Path, Heap
- Redundant Connection Union Find
- Course Schedule II Topological Sort, Heap
- Course Schedule Topological Sort, Depth-First Search
- Number of Provinces Depth-First Search, Union Find
Hard (42)
- Rank Transform of a Matrix Array, Union Find, Topological Sort
- Shortest Distance After Road Addition Queries II Array, Ordered Set
- Time Taken to Mark All Nodes Tree, Depth-First Search, Dynamic Programming
- Number of Possible Sets of Closing Branches Bit Manipulation, Heap (Priority Queue), Shortest Path
- Count Visited Nodes in a Directed Graph Dynamic Programming, Memoization
- Minimum Edge Reversals So Every Node Is Reachable Dynamic Programming, Depth-First Search, Breadth-First Search
- Minimum Edge Weight Equilibrium Queries in a Tree Array, Tree
- Minimize the Total Price of the Trips Array, Dynamic Programming, Tree
- Collect Coins in a Tree Array, Tree, Topological Sort
- Add Edges to Make Degrees of All Nodes Even Hash Table
- Maximum Score of a Node Sequence Array, Sorting, Enumeration
- Minimum Weighted Subgraph With the Required Paths Shortest Path, Heap (Priority Queue)
- Strange Printer II Array, Topological Sort, Matrix
- Maximum Candies You Can Get from Boxes Array, Breadth-First Search
- Minimize Malware Spread II Array, Hash Table, Depth-First Search
- Cat and Mouse Topological Sort, Memoization, Math
- Reachable Nodes In Subdivided Graph Heap (Priority Queue), Shortest Path
- Articulation Points in a Graph Depth-First Search
- Strongly Connected Components (Kosaraju's Algorithm) Depth-First Search
- Minimum Cost to Make at Least One Valid Path in a Grid Breadth-First Search, Matrix, Shortest Path
- Remove Max Number of Edges to Keep Graph Fully Traversable Union Find, Greedy
- Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Union Find, Minimum Spanning Tree, Sorting
- Minimize Malware Spread Array, Hash Table, Union Find
- Sum of Distances in Tree Tree, Depth-First Search, Dynamic Programming
- Shortest Cycle in a Graph Breadth-First Search
- Divide Nodes Into the Maximum Number of Groups Breadth-First Search, Union Find
- Maximum Employees to Be Invited to a Meeting Topological Sort, Depth-First Search
- Second Minimum Time to Reach Destination Breadth-First Search, Shortest Path
- Parallel Courses III Array, Topological Sort, Dynamic Programming
- Largest Color Value in a Directed Graph Topological Sort, Dynamic Programming, Memoization
- Redundant Connection II Union Find, Depth-First Search
- Couples Holding Hands Greedy, Union Find
- Parallel Courses II Dynamic Programming, Bit Manipulation, Bitmask
- Minimum Time to Visit a Cell In a Grid Array, Matrix, Breadth-First Search
- Checking Existence of Edge Length Limited Paths Array, Union Find, Sorting
- Find All People With Secret Union Find, Depth-First Search, Breadth-First Search
- Minimum Obstacle Removal to Reach Corner Array, Matrix, Breadth-First Search
- Number of Good Paths Array, Tree, Union Find
- Critical Connections in a Network Depth-First Search, Biconnected Component
- Number of Restricted Paths From First to Last Node Dynamic Programming, Shortest Path, Heap (Priority Queue)
- Shortest Path Visiting All Nodes Bit Manipulation, Breadth-First Search, Bitmask
- Longest Cycle in a Graph Depth-First Search, Topological Sort
Companies that ask graph problems
- Amazon 89 problems on graph
- Google 85 problems on graph
- Microsoft 17 problems on graph
- Meta 9 problems on graph
- Flipkart 6 problems on graph
- Adobe 4 problems on graph
- Uber 4 problems on graph
- Airbnb 3 problems on graph
- Samsung 3 problems on graph
- Atlassian 2 problems on graph
- Intuit 2 problems on graph
- LiveRamp 2 problems on graph
Next topic: Breadth-First Search