Graph LeetCode Problems: All 138,
With Python Solutions

Every problem in this library that LeetCode tags Graph. 106 of them carry a complete Python solution, a worked example and the time and space complexity of the approach.

Get Stealth Interview

Easy: 3
Medium: 64
Hard: 71

1 pattern

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 SearchFollow one path to its end before trying the next — the default way to explore a graph.

Eyes only

When the Graph problem arrives live.

In the live round, Stealth Interview reads the 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 says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

Graph problems by difficulty

Problems with a complete Python solution are listed first, then by ascending problem number.

Easy (3)

Easy problems
No.	Problem	Topics
0997	Find the Town Judge	Graph, Array, Hash Table
1791	Find Center of Star Graph	Graph
1971	Find if Path Exists in Graph	Depth-First Search, Breadth-First Search, Union Find +1

Medium (64)

Medium problems
No.	Problem	Topics
0133	Clone Graph	Depth-First Search, Breadth-First Search, Graph +1
0207	Course Schedule	Depth-First Search, Breadth-First Search, Graph +1
0210	Course Schedule II	Depth-First Search, Breadth-First Search, Graph +1
0310	Minimum Height Trees	Depth-First Search, Breadth-First Search, Graph +1
0399	Evaluate Division	Depth-First Search, Breadth-First Search, Union Find +4
0547	Number of Provinces	Depth-First Search, Breadth-First Search, Union Find +1
0684	Redundant Connection	Depth-First Search, Breadth-First Search, Union Find +1
0743	Network Delay Time	Depth-First Search, Breadth-First Search, Graph +2
0785	Is Graph Bipartite?	Depth-First Search, Breadth-First Search, Union Find +1
0787	Cheapest Flights Within K Stops	Depth-First Search, Breadth-First Search, Graph +3
0797	All Paths From Source to Target	Depth-First Search, Breadth-First Search, Graph +1
0802	Find Eventual Safe States	Depth-First Search, Breadth-First Search, Graph +1
0841	Keys and Rooms	Depth-First Search, Breadth-First Search, Graph
0851	Loud and Rich	Depth-First Search, Graph, Topological Sort +1
0886	Possible Bipartition	Depth-First Search, Breadth-First Search, Union Find +1
0947	Most Stones Removed with Same Row or Column	Depth-First Search, Union Find, Graph +1
0990	Satisfiability of Equality Equations	Union Find, Graph, Array +1
1042	Flower Planting With No Adjacent	Depth-First Search, Breadth-First Search, Graph
1129	Shortest Path with Alternating Colors	Breadth-First Search, Graph
1311	Get Watched Videos by Your Friends	Breadth-First Search, Graph, Array +2
1319	Number of Operations to Make Network Connected	Depth-First Search, Breadth-First Search, Union Find +1
1334	Find the City With the Smallest Number of Neighbors at a Threshold Distance	Graph, Dynamic Programming, Shortest Path
1361	Validate Binary Tree Nodes	Tree, Depth-First Search, Breadth-First Search +3
1462	Course Schedule IV	Depth-First Search, Breadth-First Search, Graph +1
1466	Reorder Routes to Make All Paths Lead to the City Zero	Depth-First Search, Breadth-First Search, Graph
1514	Path with Maximum Probability	Graph, Array, Shortest Path +1
1557	Minimum Number of Vertices to Reach All Nodes	Graph
1584	Min Cost to Connect All Points	Union Find, Graph, Array +1
1615	Maximal Network Rank	Graph
1786	Number of Restricted Paths From First to Last Node	Graph, Topological Sort, Dynamic Programming +2
1976	Number of Ways to Arrive at Destination	Graph, Topological Sort, Dynamic Programming +1
2039	The Time When the Network Becomes Idle	Breadth-First Search, Graph, Array
2101	Detonate the Maximum Bombs	Depth-First Search, Breadth-First Search, Graph +3
2115	Find All Possible Recipes from Given Supplies	Graph, Topological Sort, Array +2
2192	All Ancestors of a Node in a Directed Acyclic Graph	Depth-First Search, Breadth-First Search, Graph +1
2285	Maximum Total Importance of Roads	Greedy, Graph, Sorting +1
2316	Count Unreachable Pairs of Nodes in an Undirected Graph	Depth-First Search, Breadth-First Search, Union Find +1
2359	Find Closest Node to Given Two Nodes	Depth-First Search, Graph
2368	Reachable Nodes With Restrictions	Tree, Depth-First Search, Breadth-First Search +4
2374	Node With Highest Edge Score	Graph, Hash Table
2467	Most Profitable Path in a Tree	Tree, Depth-First Search, Breadth-First Search +2
2477	Minimum Fuel Cost to Report to the Capital	Tree, Depth-First Search, Breadth-First Search +1
2492	Minimum Score of a Path Between Two Cities	Depth-First Search, Breadth-First Search, Union Find +1
2497	Maximum Star Sum of a Graph	Greedy, Graph, Array +2
2662	Minimum Cost of a Path With Special Roads	Graph, Array, Shortest Path +1
2685	Count the Number of Complete Components	Depth-First Search, Breadth-First Search, Union Find +1
2924	Find Champion II	Graph
2976	Minimum Cost to Convert String I	Graph, Array, String +1
0261	Graph Valid TreePremium	Depth-First Search, Breadth-First Search, Union Find +1
0277	Find the CelebrityPremium	Graph, Two Pointers, Interactive
0323	Number of Connected Components in an Undirected GraphPremium	Depth-First Search, Breadth-First Search, Union Find +1
0444	Sequence ReconstructionPremium	Graph, Topological Sort, Array
0505	The Maze IIPremium	Depth-First Search, Breadth-First Search, Graph +4
1059	All Paths from Source Lead to DestinationPremium	Graph, Topological Sort
1135	Connecting Cities With Minimum CostPremium	Union Find, Graph, Minimum Spanning Tree +1
1136	Parallel CoursesPremium	Graph, Topological Sort
1245	Tree DiameterPremium	Tree, Depth-First Search, Breadth-First Search +2
1810	Minimum Path Cost in a Hidden GridPremium	Depth-First Search, Breadth-First Search, Graph +5
1820	Maximum Number of Accepted InvitationsPremium	Depth-First Search, Graph, Array +1
2077	Paths in Maze That Lead to Same RoomPremium	Graph
2093	Minimum Cost to Reach City With DiscountsPremium	Graph, Shortest Path, Heap (Priority Queue)
2297	Jump Game VIIIPremium	Stack, Graph, Array +3
2473	Minimum Cost to Buy ApplesPremium	Graph, Array, Shortest Path +1
2737	Find the Closest Marked NodePremium	Graph, Array, Shortest Path +1

Hard (71)

Hard problems
No.	Problem	Topics
0329	Longest Increasing Path in a Matrix	Depth-First Search, Breadth-First Search, Graph +5
0332	Reconstruct Itinerary	Depth-First Search, Graph, Eulerian Circuit
0685	Redundant Connection II	Depth-First Search, Breadth-First Search, Union Find +1
0753	Cracking the Safe	Depth-First Search, Graph, Eulerian Circuit
0765	Couples Holding Hands	Greedy, Depth-First Search, Breadth-First Search +2
0834	Sum of Distances in Tree	Tree, Depth-First Search, Graph +1
0847	Shortest Path Visiting All Nodes	Bit Manipulation, Breadth-First Search, Graph +2
0882	Reachable Nodes In Subdivided Graph	Graph, Shortest Path, Heap (Priority Queue)
0913	Cat and Mouse	Graph, Topological Sort, Memoization +3
0924	Minimize Malware Spread	Depth-First Search, Breadth-First Search, Union Find +3
0928	Minimize Malware Spread II	Depth-First Search, Breadth-First Search, Union Find +3
1192	Critical Connections in a Network	Depth-First Search, Graph, Biconnected Component
1203	Sort Items by Groups Respecting Dependencies	Depth-First Search, Breadth-First Search, Graph +1
1298	Maximum Candies You Can Get from Boxes	Breadth-First Search, Graph, Array
1368	Minimum Cost to Make at Least One Valid Path in a Grid	Breadth-First Search, Graph, Array +3
1377	Frog Position After T Seconds	Tree, Depth-First Search, Breadth-First Search +1
1489	Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree	Union Find, Graph, Minimum Spanning Tree +2
1494	Parallel Courses II	Bit Manipulation, Graph, Dynamic Programming +1
1579	Remove Max Number of Edges to Keep Graph Fully Traversable	Union Find, Graph
1632	Rank Transform of a Matrix	Union Find, Graph, Topological Sort +3
1697	Checking Existence of Edge Length Limited Paths	Union Find, Graph, Array +2
1719	Number Of Ways To Reconstruct A Tree	Tree, Graph
1728	Cat and Mouse II	Graph, Topological Sort, Memoization +5
1761	Minimum Degree of a Connected Trio in a Graph	Graph, Enumeration
1782	Count Pairs Of Nodes	Graph, Array, Hash Table +4
1857	Largest Color Value in a Directed Graph	Graph, Topological Sort, Memoization +3
1916	Count Ways to Build Rooms in an Ant Colony	Tree, Graph, Topological Sort +3
1928	Minimum Cost to Reach Destination in Time	Graph, Array, Dynamic Programming
2045	Second Minimum Time to Reach Destination	Breadth-First Search, Graph, Shortest Path
2050	Parallel Courses III	Graph, Topological Sort, Array +1
2065	Maximum Path Quality of a Graph	Graph, Array, Backtracking
2076	Process Restricted Friend Requests	Union Find, Graph
2092	Find All People With Secret	Depth-First Search, Breadth-First Search, Union Find +2
2127	Maximum Employees to Be Invited to a Meeting	Depth-First Search, Graph, Topological Sort
2203	Minimum Weighted Subgraph With the Required Paths	Graph, Shortest Path
2242	Maximum Score of a Node Sequence	Graph, Array, Enumeration +1
2246	Longest Path With Different Adjacent Characters	Tree, Depth-First Search, Graph +3
2290	Minimum Obstacle Removal to Reach Corner	Breadth-First Search, Graph, Array +3
2328	Number of Increasing Paths in a Grid	Depth-First Search, Breadth-First Search, Graph +5
2360	Longest Cycle in a Graph	Depth-First Search, Breadth-First Search, Graph +1
2392	Build a Matrix With Conditions	Graph, Topological Sort, Array +1
2421	Number of Good Paths	Tree, Union Find, Graph +3
2493	Divide Nodes Into the Maximum Number of Groups	Depth-First Search, Breadth-First Search, Union Find +1
2508	Add Edges to Make Degrees of All Nodes Even	Graph, Hash Table
2577	Minimum Time to Visit a Cell In a Grid	Breadth-First Search, Graph, Array +3
2603	Collect Coins in a Tree	Tree, Graph, Topological Sort +1
2608	Shortest Cycle in a Graph	Breadth-First Search, Graph
2642	Design Graph With Shortest Path Calculator	Graph, Design, Shortest Path +1
2646	Minimize the Total Price of the Trips	Tree, Depth-First Search, Graph +2
2699	Modify Graph Edge Weights	Graph, Shortest Path, Heap (Priority Queue)
2846	Minimum Edge Weight Equilibrium Queries in a Tree	Tree, Graph, Array +1
2858	Minimum Edge Reversals So Every Node Is Reachable	Depth-First Search, Breadth-First Search, Graph +1
2876	Count Visited Nodes in a Directed Graph	Graph, Memoization, Dynamic Programming
2959	Number of Possible Sets of Closing Branches	Bit Manipulation, Graph, Enumeration +2
2977	Minimum Cost to Convert String II	Graph, Trie, Array +3
0269	Alien DictionaryPremium	Depth-First Search, Breadth-First Search, Graph +3
0499	The Maze IIIPremium	Depth-First Search, Breadth-First Search, Graph +5
0631	Design Excel Sum FormulaPremium	Graph, Design, Topological Sort +4
1153	String Transforms Into Another StringPremium	Graph, Hash Table, String
1168	Optimize Water Distribution in a VillagePremium	Union Find, Graph, Minimum Spanning Tree +1
1548	The Most Similar Path in a GraphPremium	Graph, Dynamic Programming
1591	Strange Printer II	Graph, Topological Sort, Array +1
1724	Checking Existence of Edge Length Limited Paths IIPremium	Union Find, Graph, Minimum Spanning Tree
2097	Valid Arrangement of Pairs	Depth-First Search, Graph, Eulerian Circuit
2123	Minimum Operations to Remove Adjacent Ones in MatrixPremium	Graph, Array, Matrix
2204	Distance to a Cycle in Undirected GraphPremium	Depth-First Search, Breadth-First Search, Union Find +1
2247	Maximum Cost of Trip With K HighwaysPremium	Bit Manipulation, Graph, Dynamic Programming +1
2307	Check for Contradictions in EquationsPremium	Depth-First Search, Union Find, Graph +1
2371	Minimize Maximum Value in a GridPremium	Union Find, Graph, Topological Sort +3
2479	Maximum XOR of Two Non-Overlapping SubtreesPremium	Tree, Depth-First Search, Graph +1
2714	Find Shortest Path with K HopsPremium	Graph, Shortest Path, Heap (Priority Queue)

How Graph problems are solved

When the Graph problem arrives live.

Approach

Approach

Approach

Graph problems by difficulty

Easy (3)3

Medium (64)64

Hard (71)71

Keep exploring

Easy (3)

Medium (64)

Hard (71)