Pattern 12 of 22

Breadth-First Search Pattern: Template + 233 LeetCode Problems

Expand outward level by level, so the first time you arrive is the shortest way.

Easy: 23
Medium: 148
Hard: 62
Time: O(V + E)

What the breadth-first search pattern is

Breadth-first search visits every node at distance k before any node at distance k+1, and that ordering is the entire reason to prefer it: on an unweighted graph the first time BFS reaches a node is guaranteed to be by a shortest path, so the search can stop the moment the target appears. Distance is tracked either by carrying it in the queue alongside the node, or by draining the queue one full level at a time — the level form is what you want when the answer is per-level, such as a right-side view or the maximum value on each row. Mark nodes as seen when they are enqueued, not when they are dequeued, or the same node enters the queue once per incoming edge and the cost stops being linear. The multi-source variant is worth recognising on sight: seeding the queue with every starting cell at once computes the distance from the nearest source for every cell in one pass, which is how rotting oranges and nearest-zero problems avoid running a separate BFS per source.

When to use it

The question is the minimum number of steps, moves, or transformations.
The graph is unweighted — with weights, this becomes Dijkstra and needs a heap.
The answer is per level: a level order, a right-side view, a level sum.
Distance from the nearest of several sources is needed, which one multi-source pass gives you.

The breadth-first search template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 233 problems listed below.

PythonBreadth-First Search template

from collections import deque

def shortest_steps(graph, start, goal):
    seen = {start}
    queue = deque([(start, 0)])

    while queue:
        node, steps = queue.popleft()
        if node == goal:
            return steps               # first arrival is the shortest one
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)    # mark on ENQUEUE or the queue duplicates
                queue.append((neighbour, steps + 1))

    return -1

Complexity characteristics

Time: O(V + E)
Auxiliary space: O(V)

The same linear traversal cost as depth-first search: the difference is the order of the visits, not the amount of work. The queue holds the widest level rather than the deepest path, which on a wide graph or a filled grid is O(V) and can be considerably more memory than DFS uses on the same input. A multi-source pass costs the same single traversal however many sources are seeded, which is the whole reason to prefer it to one BFS per source.

Eyes only

Meet the breadth-first search problem you did not practise.

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+

All 233 breadth-first search LeetCode problems

Every problem in the library the breadth-first search pattern applies to, grouped by LeetCode's own difficulty rating. 185 of the 233 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Easy (23)

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
0933	Number of Recent Calls	Design, Queue, Data Stream
0346	Moving Average from Data StreamPremium	Design, Queue, 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
1469	Find All The Lonely NodesPremium	Tree, Depth-First Search, Breadth-First Search +1
1971	Find if Path Exists in Graph	Depth-First Search, Breadth-First Search, Union Find +1
2073	Time Needed to Buy Tickets	Queue, Array, Simulation

Medium (148)

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
0622	Design Circular Queue	Design, Queue, Array +1
0623	Add One Row to Tree	Tree, Depth-First Search, Breadth-First Search +1
0641	Design Circular Deque	Design, Queue, Array +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
0787	Cheapest Flights Within K Stops	Depth-First Search, Breadth-First Search, Graph +3
0841	Keys and Rooms	Depth-First Search, Breadth-First Search, Graph
0909	Snakes and Ladders	Breadth-First Search, Array, Matrix
0994	Rotting Oranges	Breadth-First Search, Array, Matrix
1161	Maximum Level Sum of a Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1448	Count Good Nodes in Binary Tree	Tree, Depth-First Search, Breadth-First Search +1
1466	Reorder Routes to Make All Paths Lead to the City Zero	Depth-First Search, Breadth-First Search, Graph
1926	Nearest Exit from Entrance in Maze	Breadth-First Search, Array, Matrix
0261	Graph Valid TreePremium	Depth-First Search, Breadth-First Search, Union Find +1
0281	Zigzag IteratorPremium	Design, Queue, Array +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
0752	Open the Lock	Breadth-First Search, Array, Hash Table +1
0785	Is Graph Bipartite?	Depth-First Search, Breadth-First Search, Union Find +1
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
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
0919	Complete Binary Tree Inserter	Tree, Breadth-First Search, Design +1
0934	Shortest Bridge	Depth-First Search, Breadth-First Search, Array +1
0950	Reveal Cards In Increasing Order	Queue, Array, Sorting +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
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
1087	Brace ExpansionPremium	Stack, Breadth-First Search, String +2
1091	Shortest Path in Binary Matrix	Breadth-First Search, Array, Matrix
1102	Path With Maximum Minimum ValuePremium	Depth-First Search, Breadth-First Search, Union Find +4
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
1162	As Far from Land as Possible	Breadth-First Search, Array, Dynamic Programming +1
1197	Minimum Knight MovesPremium	Breadth-First Search
1202	Smallest String With Swaps	Depth-First Search, Breadth-First Search, Union Find +4
1215	Stepping NumbersPremium	Breadth-First Search, Math, Backtracking
1236	Web CrawlerPremium	Depth-First Search, Breadth-First Search, String +1
1242	Web Crawler MultithreadedPremium	Depth-First Search, Breadth-First Search, Concurrency
1245	Tree DiameterPremium	Tree, Depth-First Search, Breadth-First Search +2
1254	Number of Closed Islands	Depth-First Search, Breadth-First Search, Union Find +2
1257	Smallest Common RegionPremium	Tree, Depth-First Search, Breadth-First Search +3
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
1273	Delete Tree NodesPremium	Tree, Depth-First Search, Breadth-First Search +1
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
1430	Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
1443	Minimum Time to Collect All Apples in a 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
1485	Clone Binary Tree With Random PointerPremium	Tree, Depth-First Search, Breadth-First Search +2
1490	Clone N-ary TreePremium	Tree, Depth-First Search, Breadth-First Search +1
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
1602	Find Nearest Right Node in Binary TreePremium	Tree, Breadth-First Search, Binary Tree
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
1660	Correct a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
1670	Design Front Middle Back Queue	Design, Queue, Array +2
1730	Shortest Path to Get FoodPremium	Breadth-First Search, Array, Matrix
1740	Find Distance in a Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +2
1765	Map of Highest Peak	Breadth-First Search, Array, Matrix
1778	Shortest Path in a Hidden GridPremium	Depth-First Search, Breadth-First Search, Array +2
1810	Minimum Path Cost in a Hidden GridPremium	Depth-First Search, Breadth-First Search, Graph +5
1823	Find the Winner of the Circular Game	Recursion, Queue, Array +2
1905	Count Sub Islands	Depth-First Search, Breadth-First Search, Union Find +2
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
2174	Remove All Ones With Row and Column Flips IIPremium	Bit Manipulation, Breadth-First Search, Array +1
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
2445	Number of Nodes With Value OnePremium	Tree, Depth-First Search, Breadth-First Search +2
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
2773	Height of Special Binary TreePremium	Tree, Depth-First Search, Breadth-First Search +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
2852	Sum of Remoteness of All CellsPremium	Depth-First Search, Breadth-First Search, Union Find +3
2998	Minimum Number of Operations to Make X and Y Equal	Breadth-First Search, Memoization, Dynamic Programming

Hard (62)

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
0778	Swim in Rising Water	Depth-First Search, Breadth-First Search, Union Find +4
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
0765	Couples Holding Hands	Greedy, Depth-First Search, Breadth-First Search +2
0773	Sliding Puzzle	Breadth-First Search, Memoization, Array +3
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
2204	Distance to a Cycle in Undirected GraphPremium	Depth-First Search, Breadth-First Search, Union Find +1
2258	Escape the Spreading Fire	Breadth-First Search, Array, Binary Search +1
2277	Closest Node to Path in TreePremium	Tree, Depth-First Search, Breadth-First 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
2534	Time Taken to Cross the DoorPremium	Queue, Array, Simulation
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
2814	Minimum Time Takes to Reach Destination Without DrowningPremium	Breadth-First Search, Array, Matrix
2858	Minimum Edge Reversals So Every Node Is Reachable	Depth-First Search, Breadth-First Search, Graph +1

Breadth-First Search pattern FAQ

What is the breadth-first search pattern?

How many LeetCode problems use the breadth-first search pattern?

This page lists 233 LeetCode problems that the breadth-first search pattern applies to: 23 Easy, 148 Medium and 62 Hard. 185 of them carry a complete Python solution with complexity analysis.

What is the time complexity of the breadth-first search pattern?

O(V + E) time and O(V) space. The same linear traversal cost as depth-first search: the difference is the order of the visits, not the amount of work. The queue holds the widest level rather than the deepest path, which on a wide graph or a filled grid is O(V) and can be considerably more memory than DFS uses on the same input. A multi-source pass costs the same single traversal however many sources are seeded, which is the whole reason to prefer it to one BFS per source.

When should I use the breadth-first search pattern in an interview?

The question is the minimum number of steps, moves, or transformations. The graph is unweighted — with weights, this becomes Dijkstra and needs a heap.

Which breadth-first search problem should I start with?

LeetCode 100. Same Tree is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.

What patterns are related to breadth-first search?

Depth-First Search, Matrix and Grid, Topological Sort, Heap / Priority Queue. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.

More ways in: all 22 patterns, the curated study lists, or the full problem list.

What the breadth-first search pattern is

When to use it

The breadth-first search template in Python

Complexity characteristics

Meet the breadth-first search problem you did not practise.

Approach

Approach

Approach

All 233 breadth-first search LeetCode problems

Easy (23)23

Medium (148)148

Hard (62)62

Related patterns

Breadth-First Search pattern FAQ

What is the breadth-first search pattern?

How many LeetCode problems use the breadth-first search pattern?

What is the time complexity of the breadth-first search pattern?

When should I use the breadth-first search pattern in an interview?

Which breadth-first search problem should I start with?

What patterns are related to breadth-first search?

Easy (23)

Medium (148)

Hard (62)