Breadth-First Search LeetCode Problems: All 223,
With Python Solutions

Every problem in this library that LeetCode tags Breadth-First Search. 178 of them carry a complete Python solution, a worked example and the time and space complexity of the approach.

Get Stealth Interview

Easy: 20
Medium: 142
Hard: 61

1 pattern

How Breadth-First Search problems are solved

A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Breadth-First Search problems — each one explains the approach, gives a Python template and states its complexity.

Breadth-First SearchExpand outward level by level, so the first time you arrive is the shortest way.

Eyes only

When the Breadth-First Search 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+

Breadth-First Search problems by difficulty

Showing the first 200 of 223 problems. Problems with a complete Python solution are listed first, then by ascending problem number.

Easy (19)

Easy problems
No.	Problem	Topics
0100	Same Tree	Tree, Depth-First Search, Breadth-First Search +1
0101	Symmetric Tree	Tree, Depth-First Search, Breadth-First Search +1
0104	Maximum Depth of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0111	Minimum Depth of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0112	Path Sum	Tree, Depth-First Search, Breadth-First Search +1
0226	Invert Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0404	Sum of Left Leaves	Tree, Depth-First Search, Breadth-First Search +1
0463	Island Perimeter	Depth-First Search, Breadth-First Search, Array +1
0530	Minimum Absolute Difference in BST	Tree, Depth-First Search, Breadth-First Search +2
0559	Maximum Depth of N-ary Tree	Tree, Depth-First Search, Breadth-First Search
0617	Merge Two Binary Trees	Tree, Depth-First Search, Breadth-First Search +1
0637	Average of Levels in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0653	Two Sum IV - Input is a BST	Tree, Depth-First Search, Breadth-First Search +4
0733	Flood Fill	Depth-First Search, Breadth-First Search, Array +1
0783	Minimum Distance Between BST Nodes	Tree, Depth-First Search, Breadth-First Search +2
0965	Univalued Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0993	Cousins in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1379	Find a Corresponding Node of a Binary Tree in a Clone of That Tree	Tree, Depth-First Search, Breadth-First Search +1
1971	Find if Path Exists in Graph	Depth-First Search, Breadth-First Search, Union Find +1

Medium (123)

Medium problems
No.	Problem	Topics
0102	Binary Tree Level Order Traversal	Tree, Breadth-First Search, Binary Tree
0103	Binary Tree Zigzag Level Order Traversal	Tree, Breadth-First Search, Binary Tree
0107	Binary Tree Level Order Traversal II	Tree, Breadth-First Search, Binary Tree
0116	Populating Next Right Pointers in Each Node	Tree, Depth-First Search, Breadth-First Search +2
0117	Populating Next Right Pointers in Each Node II	Tree, Depth-First Search, Breadth-First Search +2
0130	Surrounded Regions	Depth-First Search, Breadth-First Search, Union Find +2
0133	Clone Graph	Depth-First Search, Breadth-First Search, Graph +1
0199	Binary Tree Right Side View	Tree, Depth-First Search, Breadth-First Search +1
0200	Number of Islands	Depth-First Search, Breadth-First Search, Union Find +2
0207	Course Schedule	Depth-First Search, Breadth-First Search, Graph +1
0210	Course Schedule II	Depth-First Search, Breadth-First Search, Graph +1
0279	Perfect Squares	Breadth-First Search, Math, Dynamic Programming
0310	Minimum Height Trees	Depth-First Search, Breadth-First Search, Graph +1
0322	Coin Change	Breadth-First Search, Array, Dynamic Programming
0365	Water and Jug Problem	Depth-First Search, Breadth-First Search, Math
0399	Evaluate Division	Depth-First Search, Breadth-First Search, Union Find +4
0417	Pacific Atlantic Water Flow	Depth-First Search, Breadth-First Search, Array +1
0429	N-ary Tree Level Order Traversal	Tree, Breadth-First Search
0433	Minimum Genetic Mutation	Breadth-First Search, Hash Table, String
0449	Serialize and Deserialize BST	Tree, Depth-First Search, Breadth-First Search +4
0513	Find Bottom Left Tree Value	Tree, Depth-First Search, Breadth-First Search +1
0515	Find Largest Value in Each Tree Row	Tree, Depth-First Search, Breadth-First Search +1
0529	Minesweeper	Depth-First Search, Breadth-First Search, Array +1
0542	01 Matrix	Breadth-First Search, Array, Dynamic Programming +1
0547	Number of Provinces	Depth-First Search, Breadth-First Search, Union Find +1
0623	Add One Row to Tree	Tree, Depth-First Search, Breadth-First Search +1
0655	Print Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0662	Maximum Width of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
0672	Bulb Switcher II	Bit Manipulation, Depth-First Search, Breadth-First Search +1
0684	Redundant Connection	Depth-First Search, Breadth-First Search, Union Find +1
0690	Employee Importance	Tree, Depth-First Search, Breadth-First Search +2
0695	Max Area of Island	Depth-First Search, Breadth-First Search, Union Find +2
0721	Accounts Merge	Depth-First Search, Breadth-First Search, Union Find +4
0743	Network Delay Time	Depth-First Search, Breadth-First Search, Graph +2
0752	Open the Lock	Breadth-First Search, Array, Hash Table +1
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
0863	All Nodes Distance K in Binary Tree	Tree, Depth-First Search, Breadth-First Search +2
0865	Smallest Subtree with all the Deepest Nodes	Tree, Depth-First Search, Breadth-First Search +2
0886	Possible Bipartition	Depth-First Search, Breadth-First Search, Union Find +1
0909	Snakes and Ladders	Breadth-First Search, Array, Matrix
0919	Complete Binary Tree Inserter	Tree, Breadth-First Search, Design +1
0934	Shortest Bridge	Depth-First Search, Breadth-First Search, Array +1
0958	Check Completeness of a Binary Tree	Tree, Breadth-First Search, Binary Tree
0959	Regions Cut By Slashes	Depth-First Search, Breadth-First Search, Union Find +3
0967	Numbers With Same Consecutive Differences	Breadth-First Search, Backtracking
0994	Rotting Oranges	Breadth-First Search, Array, Matrix
1020	Number of Enclaves	Depth-First Search, Breadth-First Search, Union Find +2
1034	Coloring A Border	Depth-First Search, Breadth-First Search, Array +1
1042	Flower Planting With No Adjacent	Depth-First Search, Breadth-First Search, Graph
1091	Shortest Path in Binary Matrix	Breadth-First Search, Array, Matrix
1123	Lowest Common Ancestor of Deepest Leaves	Tree, Depth-First Search, Breadth-First Search +2
1129	Shortest Path with Alternating Colors	Breadth-First Search, Graph
1161	Maximum Level Sum of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1162	As Far from Land as Possible	Breadth-First Search, Array, Dynamic Programming +1
1202	Smallest String With Swaps	Depth-First Search, Breadth-First Search, Union Find +4
1254	Number of Closed Islands	Depth-First Search, Breadth-First Search, Union Find +2
1261	Find Elements in a Contaminated Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
1267	Count Servers that Communicate	Depth-First Search, Breadth-First Search, Union Find +3
1302	Deepest Leaves Sum	Tree, Depth-First Search, Breadth-First Search +1
1306	Jump Game III	Depth-First Search, Breadth-First Search, Array
1311	Get Watched Videos by Your Friends	Breadth-First Search, Graph, Array +2
1315	Sum of Nodes with Even-Valued Grandparent	Tree, Depth-First Search, Breadth-First Search +1
1319	Number of Operations to Make Network Connected	Depth-First Search, Breadth-First Search, Union Find +1
1361	Validate Binary Tree Nodes	Tree, Depth-First Search, Breadth-First Search +3
1376	Time Needed to Inform All Employees	Tree, Depth-First Search, Breadth-First Search
1391	Check if There is a Valid Path in a Grid	Depth-First Search, Breadth-First Search, Union Find +2
1443	Minimum Time to Collect All Apples in a Tree	Tree, Depth-First Search, Breadth-First Search +1
1448	Count Good Nodes in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1457	Pseudo-Palindromic Paths in a Binary Tree	Bit Manipulation, Tree, Depth-First Search +2
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
1519	Number of Nodes in the Sub-Tree With the Same Label	Tree, Depth-First Search, Breadth-First Search +2
1559	Detect Cycles in 2D Grid	Depth-First Search, Breadth-First Search, Union Find +2
1609	Even Odd Tree	Tree, Breadth-First Search, Binary Tree
1625	Lexicographically Smallest String After Applying Operations	Depth-First Search, Breadth-First Search, String +1
1631	Path With Minimum Effort	Depth-First Search, Breadth-First Search, Union Find +4
1654	Minimum Jumps to Reach Home	Breadth-First Search, Array, Dynamic Programming
1765	Map of Highest Peak	Breadth-First Search, Array, Matrix
1905	Count Sub Islands	Depth-First Search, Breadth-First Search, Union Find +2
1926	Nearest Exit from Entrance in Maze	Breadth-First Search, Array, Matrix
1992	Find All Groups of Farmland	Depth-First Search, Breadth-First Search, Array +1
1993	Operations on Tree	Tree, Depth-First Search, Breadth-First Search +3
2039	The Time When the Network Becomes Idle	Breadth-First Search, Graph, Array
2059	Minimum Operations to Convert Number	Breadth-First Search, Array
2101	Detonate the Maximum Bombs	Depth-First Search, Breadth-First Search, Graph +3
2146	K Highest Ranked Items Within a Price Range	Breadth-First Search, Array, Matrix +2
2192	All Ancestors of a Node in a Directed Acyclic Graph	Depth-First Search, Breadth-First Search, Graph +1
2316	Count Unreachable Pairs of Nodes in an Undirected Graph	Depth-First Search, Breadth-First Search, Union Find +1
2368	Reachable Nodes With Restrictions	Tree, Depth-First Search, Breadth-First Search +4
2385	Amount of Time for Binary Tree to Be Infected	Tree, Depth-First Search, Breadth-First Search +2
2415	Reverse Odd Levels of Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
2467	Most Profitable Path in a Tree	Tree, Depth-First Search, Breadth-First Search +2
2471	Minimum Number of Operations to Sort a Binary Tree by Level	Tree, Breadth-First Search, Binary Tree
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
2556	Disconnect Path in a Binary Matrix by at Most One Flip	Depth-First Search, Breadth-First Search, Array +2
2583	Kth Largest Sum in a Binary Tree	Tree, Breadth-First Search, Binary Tree +1
2596	Check Knight Tour Configuration	Depth-First Search, Breadth-First Search, Array +2
2641	Cousins in Binary Tree II	Tree, Depth-First Search, Breadth-First Search +2
2658	Maximum Number of Fish in a Grid	Depth-First Search, Breadth-First Search, Union Find +2
2685	Count the Number of Complete Components	Depth-First Search, Breadth-First Search, Union Find +1
2812	Find the Safest Path in a Grid	Breadth-First Search, Union Find, Array +3
2850	Minimum Moves to Spread Stones Over Grid	Breadth-First Search, Array, Dynamic Programming +1
2998	Minimum Number of Operations to Make X and Y Equal	Breadth-First Search, Memoization, Dynamic Programming
0261	Graph Valid TreePremium	Depth-First Search, Breadth-First Search, Union Find +1
0286	Walls and GatesPremium	Breadth-First Search, Array, Matrix
0314	Binary Tree Vertical Order TraversalPremium	Tree, Depth-First Search, Breadth-First Search +3
0323	Number of Connected Components in an Undirected GraphPremium	Depth-First Search, Breadth-First Search, Union Find +1
0339	Nested List Weight SumPremium	Depth-First Search, Breadth-First Search
0364	Nested List Weight Sum IIPremium	Stack, Depth-First Search, Breadth-First Search
0490	The MazePremium	Depth-First Search, Breadth-First Search, Array +1
0505	The Maze IIPremium	Depth-First Search, Breadth-First Search, Graph +4
0582	Kill ProcessPremium	Tree, Depth-First Search, Breadth-First Search +2
0694	Number of Distinct IslandsPremium	Depth-First Search, Breadth-First Search, Union Find +2
0737	Sentence Similarity IIPremium	Depth-First Search, Breadth-First Search, Union Find +3
0742	Closest Leaf in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
1087	Brace ExpansionPremium	Stack, Breadth-First Search, String +2
1102	Path With Maximum Minimum ValuePremium	Depth-First Search, Breadth-First Search, Union Find +4
1197	Minimum Knight MovesPremium	Breadth-First Search

Hard (58)

Hard problems
No.	Problem	Topics
0126	Word Ladder II	Breadth-First Search, Hash Table, String +1
0127	Word Ladder	Breadth-First Search, Hash Table, String
0297	Serialize and Deserialize Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
0301	Remove Invalid Parentheses	Breadth-First Search, String, Backtracking
0329	Longest Increasing Path in a Matrix	Depth-First Search, Breadth-First Search, Graph +5
0407	Trapping Rain Water II	Breadth-First Search, Array, Matrix +1
0488	Zuma Game	Stack, Breadth-First Search, Memoization +2
0514	Freedom Trail	Depth-First Search, Breadth-First Search, String +1
0675	Cut Off Trees for Golf Event	Breadth-First Search, Array, Matrix +1
0685	Redundant Connection II	Depth-First Search, Breadth-First Search, Union Find +1
0749	Contain Virus	Depth-First Search, Breadth-First Search, Array +2
0765	Couples Holding Hands	Greedy, Depth-First Search, Breadth-First Search +2
0773	Sliding Puzzle	Breadth-First Search, Memoization, Array +3
0778	Swim in Rising Water	Depth-First Search, Breadth-First Search, Union Find +4
0815	Bus Routes	Breadth-First Search, Array, Hash Table
0827	Making A Large Island	Depth-First Search, Breadth-First Search, Union Find +2
0839	Similar String Groups	Depth-First Search, Breadth-First Search, Union Find +3
0847	Shortest Path Visiting All Nodes	Bit Manipulation, Breadth-First Search, Graph +2
0854	K-Similar Strings	Breadth-First Search, Hash Table, String
0864	Shortest Path to Get All Keys	Bit Manipulation, Breadth-First Search, Array +1
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
0987	Vertical Order Traversal of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +3
1036	Escape a Large Maze	Depth-First Search, Breadth-First Search, Array +1
1096	Brace Expansion II	Stack, Breadth-First Search, Hash Table +3
1203	Sort Items by Groups Respecting Dependencies	Depth-First Search, Breadth-First Search, Graph +1
1210	Minimum Moves to Reach Target with Rotations	Breadth-First Search, Array, Matrix
1263	Minimum Moves to Move a Box to Their Target Location	Breadth-First Search, Array, Matrix +1
1284	Minimum Number of Flips to Convert Binary Matrix to Zero Matrix	Bit Manipulation, Breadth-First Search, Array +2
1293	Shortest Path in a Grid with Obstacles Elimination	Breadth-First Search, Array, Matrix
1298	Maximum Candies You Can Get from Boxes	Breadth-First Search, Graph, Array
1345	Jump Game IV	Breadth-First Search, Array, Hash Table
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
1483	Kth Ancestor of a Tree Node	Bit Manipulation, Tree, Depth-First Search +4
1568	Minimum Number of Days to Disconnect Island	Depth-First Search, Breadth-First Search, Array +2
1970	Last Day Where You Can Still Cross	Depth-First Search, Breadth-First Search, Union Find +3
2045	Second Minimum Time to Reach Destination	Breadth-First Search, Graph, Shortest Path
2092	Find All People With Secret	Depth-First Search, Breadth-First Search, Union Find +2
2258	Escape the Spreading Fire	Breadth-First Search, Array, Binary Search +1
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
2458	Height of Binary Tree After Subtree Removal Queries	Tree, Depth-First Search, Breadth-First Search +2
2493	Divide Nodes Into the Maximum Number of Groups	Depth-First Search, Breadth-First Search, Union Find +1
2503	Maximum Number of Points From Grid Queries	Breadth-First Search, Union Find, Array +4
2577	Minimum Time to Visit a Cell In a Grid	Breadth-First Search, Graph, Array +3
2608	Shortest Cycle in a Graph	Breadth-First Search, Graph
2612	Minimum Reverse Operations	Breadth-First Search, Union Find, Array +2
2617	Minimum Number of Visited Cells in a Grid	Stack, Breadth-First Search, Union Find +5
2858	Minimum Edge Reversals So Every Node Is Reachable	Depth-First Search, Breadth-First Search, Graph +1
0269	Alien DictionaryPremium	Depth-First Search, Breadth-First Search, Graph +3
0302	Smallest Rectangle Enclosing Black PixelsPremium	Depth-First Search, Breadth-First Search, Array +2
0317	Shortest Distance from All BuildingsPremium	Breadth-First Search, Array, Matrix
0428	Serialize and Deserialize N-ary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
0431	Encode N-ary Tree to Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
0499	The Maze IIIPremium	Depth-First Search, Breadth-First Search, Graph +5
0711	Number of Distinct Islands IIPremium	Depth-First Search, Breadth-First Search, Union Find +2

How Breadth-First Search problems are solved

When the Breadth-First Search problem arrives live.

Approach

Approach

Approach

Breadth-First Search problems by difficulty

Easy (19)19

Medium (123)123

Hard (58)58

Keep exploring

Easy (19)

Medium (123)

Hard (58)