Graph LeetCode Problems: All 138, With Python Solutions
Every problem in this library that LeetCode tags Graph — 138 in total, 106 of them with a complete Python solution, a worked example and the time and space complexity of the approach.
- 138 problems
- 3 Easy
- 64 Medium
- 71 Hard
How Graph problems are solved
A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Graph problems — each one explains the approach, gives a Python template and states its complexity.
- Depth-First Search — Follow one path to its end before trying the next — the default way to explore a graph.
Graph problems by difficulty
Problems with a complete Python solution are listed first, then by ascending problem number.
Easy (3)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 997 | Find the Town Judge | Easy | Graph, Array, Hash Table |
| 1791 | Find Center of Star Graph | Easy | Graph |
| 1971 | Find if Path Exists in Graph | Easy | Depth-First Search, Breadth-First Search, Union Find +1 |
Medium (64)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 133 | Clone Graph | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 207 | Course Schedule | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 210 | Course Schedule II | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 310 | Minimum Height Trees | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 399 | Evaluate Division | Medium | Depth-First Search, Breadth-First Search, Union Find +4 |
| 547 | Number of Provinces | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 684 | Redundant Connection | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 743 | Network Delay Time | Medium | Depth-First Search, Breadth-First Search, Graph +2 |
| 785 | Is Graph Bipartite? | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 787 | Cheapest Flights Within K Stops | Medium | Depth-First Search, Breadth-First Search, Graph +3 |
| 797 | All Paths From Source to Target | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 802 | Find Eventual Safe States | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 841 | Keys and Rooms | Medium | Depth-First Search, Breadth-First Search, Graph |
| 851 | Loud and Rich | Medium | Depth-First Search, Graph, Topological Sort +1 |
| 886 | Possible Bipartition | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 947 | Most Stones Removed with Same Row or Column | Medium | Depth-First Search, Union Find, Graph +1 |
| 990 | Satisfiability of Equality Equations | Medium | Union Find, Graph, Array +1 |
| 1042 | Flower Planting With No Adjacent | Medium | Depth-First Search, Breadth-First Search, Graph |
| 1129 | Shortest Path with Alternating Colors | Medium | Breadth-First Search, Graph |
| 1311 | Get Watched Videos by Your Friends | Medium | Breadth-First Search, Graph, Array +2 |
| 1319 | Number of Operations to Make Network Connected | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 1334 | Find the City With the Smallest Number of Neighbors at a Threshold Distance | Medium | Graph, Dynamic Programming, Shortest Path |
| 1361 | Validate Binary Tree Nodes | Medium | Tree, Depth-First Search, Breadth-First Search +3 |
| 1462 | Course Schedule IV | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 1466 | Reorder Routes to Make All Paths Lead to the City Zero | Medium | Depth-First Search, Breadth-First Search, Graph |
| 1514 | Path with Maximum Probability | Medium | Graph, Array, Shortest Path +1 |
| 1557 | Minimum Number of Vertices to Reach All Nodes | Medium | Graph |
| 1584 | Min Cost to Connect All Points | Medium | Union Find, Graph, Array +1 |
| 1615 | Maximal Network Rank | Medium | Graph |
| 1786 | Number of Restricted Paths From First to Last Node | Medium | Graph, Topological Sort, Dynamic Programming +2 |
| 1976 | Number of Ways to Arrive at Destination | Medium | Graph, Topological Sort, Dynamic Programming +1 |
| 2039 | The Time When the Network Becomes Idle | Medium | Breadth-First Search, Graph, Array |
| 2101 | Detonate the Maximum Bombs | Medium | Depth-First Search, Breadth-First Search, Graph +3 |
| 2115 | Find All Possible Recipes from Given Supplies | Medium | Graph, Topological Sort, Array +2 |
| 2192 | All Ancestors of a Node in a Directed Acyclic Graph | Medium | Depth-First Search, Breadth-First Search, Graph +1 |
| 2285 | Maximum Total Importance of Roads | Medium | Greedy, Graph, Sorting +1 |
| 2316 | Count Unreachable Pairs of Nodes in an Undirected Graph | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2359 | Find Closest Node to Given Two Nodes | Medium | Depth-First Search, Graph |
| 2368 | Reachable Nodes With Restrictions | Medium | Tree, Depth-First Search, Breadth-First Search +4 |
| 2374 | Node With Highest Edge Score | Medium | Graph, Hash Table |
| 2467 | Most Profitable Path in a Tree | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 2477 | Minimum Fuel Cost to Report to the Capital | Medium | Tree, Depth-First Search, Breadth-First Search +1 |
| 2492 | Minimum Score of a Path Between Two Cities | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2497 | Maximum Star Sum of a Graph | Medium | Greedy, Graph, Array +2 |
| 2662 | Minimum Cost of a Path With Special Roads | Medium | Graph, Array, Shortest Path +1 |
| 2685 | Count the Number of Complete Components | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2924 | Find Champion II | Medium | Graph |
| 2976 | Minimum Cost to Convert String I | Medium | Graph, Array, String +1 |
| 261 | Graph Valid TreePremium | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 277 | Find the CelebrityPremium | Medium | Graph, Two Pointers, Interactive |
| 323 | Number of Connected Components in an Undirected GraphPremium | Medium | Depth-First Search, Breadth-First Search, Union Find +1 |
| 444 | Sequence ReconstructionPremium | Medium | Graph, Topological Sort, Array |
| 505 | The Maze IIPremium | Medium | Depth-First Search, Breadth-First Search, Graph +4 |
| 1059 | All Paths from Source Lead to DestinationPremium | Medium | Graph, Topological Sort |
| 1135 | Connecting Cities With Minimum CostPremium | Medium | Union Find, Graph, Minimum Spanning Tree +1 |
| 1136 | Parallel CoursesPremium | Medium | Graph, Topological Sort |
| 1245 | Tree DiameterPremium | Medium | Tree, Depth-First Search, Breadth-First Search +2 |
| 1810 | Minimum Path Cost in a Hidden GridPremium | Medium | Depth-First Search, Breadth-First Search, Graph +5 |
| 1820 | Maximum Number of Accepted InvitationsPremium | Medium | Depth-First Search, Graph, Array +1 |
| 2077 | Paths in Maze That Lead to Same RoomPremium | Medium | Graph |
| 2093 | Minimum Cost to Reach City With DiscountsPremium | Medium | Graph, Shortest Path, Heap (Priority Queue) |
| 2297 | Jump Game VIIIPremium | Medium | Stack, Graph, Array +3 |
| 2473 | Minimum Cost to Buy ApplesPremium | Medium | Graph, Array, Shortest Path +1 |
| 2737 | Find the Closest Marked NodePremium | Medium | Graph, Array, Shortest Path +1 |
Hard (71)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 329 | Longest Increasing Path in a Matrix | Hard | Depth-First Search, Breadth-First Search, Graph +5 |
| 332 | Reconstruct Itinerary | Hard | Depth-First Search, Graph, Eulerian Circuit |
| 685 | Redundant Connection II | Hard | Depth-First Search, Breadth-First Search, Union Find +1 |
| 753 | Cracking the Safe | Hard | Depth-First Search, Graph, Eulerian Circuit |
| 765 | Couples Holding Hands | Hard | Greedy, Depth-First Search, Breadth-First Search +2 |
| 834 | Sum of Distances in Tree | Hard | Tree, Depth-First Search, Graph +1 |
| 847 | Shortest Path Visiting All Nodes | Hard | Bit Manipulation, Breadth-First Search, Graph +2 |
| 882 | Reachable Nodes In Subdivided Graph | Hard | Graph, Shortest Path, Heap (Priority Queue) |
| 913 | Cat and Mouse | Hard | Graph, Topological Sort, Memoization +3 |
| 924 | Minimize Malware Spread | Hard | Depth-First Search, Breadth-First Search, Union Find +3 |
| 928 | Minimize Malware Spread II | Hard | Depth-First Search, Breadth-First Search, Union Find +3 |
| 1192 | Critical Connections in a Network | Hard | Depth-First Search, Graph, Biconnected Component |
| 1203 | Sort Items by Groups Respecting Dependencies | Hard | Depth-First Search, Breadth-First Search, Graph +1 |
| 1298 | Maximum Candies You Can Get from Boxes | Hard | Breadth-First Search, Graph, Array |
| 1368 | Minimum Cost to Make at Least One Valid Path in a Grid | Hard | Breadth-First Search, Graph, Array +3 |
| 1377 | Frog Position After T Seconds | Hard | Tree, Depth-First Search, Breadth-First Search +1 |
| 1489 | Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree | Hard | Union Find, Graph, Minimum Spanning Tree +2 |
| 1494 | Parallel Courses II | Hard | Bit Manipulation, Graph, Dynamic Programming +1 |
| 1579 | Remove Max Number of Edges to Keep Graph Fully Traversable | Hard | Union Find, Graph |
| 1632 | Rank Transform of a Matrix | Hard | Union Find, Graph, Topological Sort +3 |
| 1697 | Checking Existence of Edge Length Limited Paths | Hard | Union Find, Graph, Array +2 |
| 1719 | Number Of Ways To Reconstruct A Tree | Hard | Tree, Graph |
| 1728 | Cat and Mouse II | Hard | Graph, Topological Sort, Memoization +5 |
| 1761 | Minimum Degree of a Connected Trio in a Graph | Hard | Graph, Enumeration |
| 1782 | Count Pairs Of Nodes | Hard | Graph, Array, Hash Table +4 |
| 1857 | Largest Color Value in a Directed Graph | Hard | Graph, Topological Sort, Memoization +3 |
| 1916 | Count Ways to Build Rooms in an Ant Colony | Hard | Tree, Graph, Topological Sort +3 |
| 1928 | Minimum Cost to Reach Destination in Time | Hard | Graph, Array, Dynamic Programming |
| 2045 | Second Minimum Time to Reach Destination | Hard | Breadth-First Search, Graph, Shortest Path |
| 2050 | Parallel Courses III | Hard | Graph, Topological Sort, Array +1 |
| 2065 | Maximum Path Quality of a Graph | Hard | Graph, Array, Backtracking |
| 2076 | Process Restricted Friend Requests | Hard | Union Find, Graph |
| 2092 | Find All People With Secret | Hard | Depth-First Search, Breadth-First Search, Union Find +2 |
| 2127 | Maximum Employees to Be Invited to a Meeting | Hard | Depth-First Search, Graph, Topological Sort |
| 2203 | Minimum Weighted Subgraph With the Required Paths | Hard | Graph, Shortest Path |
| 2242 | Maximum Score of a Node Sequence | Hard | Graph, Array, Enumeration +1 |
| 2246 | Longest Path With Different Adjacent Characters | Hard | Tree, Depth-First Search, Graph +3 |
| 2290 | Minimum Obstacle Removal to Reach Corner | Hard | Breadth-First Search, Graph, Array +3 |
| 2328 | Number of Increasing Paths in a Grid | Hard | Depth-First Search, Breadth-First Search, Graph +5 |
| 2360 | Longest Cycle in a Graph | Hard | Depth-First Search, Breadth-First Search, Graph +1 |
| 2392 | Build a Matrix With Conditions | Hard | Graph, Topological Sort, Array +1 |
| 2421 | Number of Good Paths | Hard | Tree, Union Find, Graph +3 |
| 2493 | Divide Nodes Into the Maximum Number of Groups | Hard | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2508 | Add Edges to Make Degrees of All Nodes Even | Hard | Graph, Hash Table |
| 2577 | Minimum Time to Visit a Cell In a Grid | Hard | Breadth-First Search, Graph, Array +3 |
| 2603 | Collect Coins in a Tree | Hard | Tree, Graph, Topological Sort +1 |
| 2608 | Shortest Cycle in a Graph | Hard | Breadth-First Search, Graph |
| 2642 | Design Graph With Shortest Path Calculator | Hard | Graph, Design, Shortest Path +1 |
| 2646 | Minimize the Total Price of the Trips | Hard | Tree, Depth-First Search, Graph +2 |
| 2699 | Modify Graph Edge Weights | Hard | Graph, Shortest Path, Heap (Priority Queue) |
| 2846 | Minimum Edge Weight Equilibrium Queries in a Tree | Hard | Tree, Graph, Array +1 |
| 2858 | Minimum Edge Reversals So Every Node Is Reachable | Hard | Depth-First Search, Breadth-First Search, Graph +1 |
| 2876 | Count Visited Nodes in a Directed Graph | Hard | Graph, Memoization, Dynamic Programming |
| 2959 | Number of Possible Sets of Closing Branches | Hard | Bit Manipulation, Graph, Enumeration +2 |
| 2977 | Minimum Cost to Convert String II | Hard | Graph, Trie, Array +3 |
| 269 | Alien DictionaryPremium | Hard | Depth-First Search, Breadth-First Search, Graph +3 |
| 499 | The Maze IIIPremium | Hard | Depth-First Search, Breadth-First Search, Graph +5 |
| 631 | Design Excel Sum FormulaPremium | Hard | Graph, Design, Topological Sort +4 |
| 1153 | String Transforms Into Another StringPremium | Hard | Graph, Hash Table, String |
| 1168 | Optimize Water Distribution in a VillagePremium | Hard | Union Find, Graph, Minimum Spanning Tree +1 |
| 1548 | The Most Similar Path in a GraphPremium | Hard | Graph, Dynamic Programming |
| 1591 | Strange Printer II | Hard | Graph, Topological Sort, Array +1 |
| 1724 | Checking Existence of Edge Length Limited Paths IIPremium | Hard | Union Find, Graph, Minimum Spanning Tree |
| 2097 | Valid Arrangement of Pairs | Hard | Depth-First Search, Graph, Eulerian Circuit |
| 2123 | Minimum Operations to Remove Adjacent Ones in MatrixPremium | Hard | Graph, Array, Matrix |
| 2204 | Distance to a Cycle in Undirected GraphPremium | Hard | Depth-First Search, Breadth-First Search, Union Find +1 |
| 2247 | Maximum Cost of Trip With K HighwaysPremium | Hard | Bit Manipulation, Graph, Dynamic Programming +1 |
| 2307 | Check for Contradictions in EquationsPremium | Hard | Depth-First Search, Union Find, Graph +1 |
| 2371 | Minimize Maximum Value in a GridPremium | Hard | Union Find, Graph, Topological Sort +3 |
| 2479 | Maximum XOR of Two Non-Overlapping SubtreesPremium | Hard | Tree, Depth-First Search, Graph +1 |
| 2714 | Find Shortest Path with K HopsPremium | Hard | Graph, Shortest Path, Heap (Priority Queue) |
Keep exploring
All LeetCode topicsEvery tag with a page of its own, with the number of problems behind each.LeetCode patternsThe techniques themselves, with a Python template and complexity for each.Curated study listsBlind 75, NeetCode 150 and three more, grouped by pattern.Easy problemsStart here when the data structure is new rather than the problem.
Other topics
- Array1,569
- String672
- Hash Table588
- Math485
- Dynamic Programming481
- Sorting392
- Greedy346
- Depth-First Search289
- Binary Search253
- Database249
- Tree225
- Breadth-First Search223
- Matrix216
- Two Pointers201
- Bit Manipulation194
- Binary Tree174
- Heap (Priority Queue)163
- Prefix Sum157
- Stack157
- Simulation144
- Counting126
- Design122
- Sliding Window116
- Backtracking105
When the Graph problem arrives live
Stealth Interview is a desktop app for macOS and Windows. It reads the coding problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer is saying — while staying invisible to screen sharing.