Get started

Breadth-First Search Coding Problems: 65 Questions with Solutions

65 breadth-first search coding problems — 2 easy · 48 medium · 15 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 65
  • By difficulty: 2 easy · 48 medium · 15 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

Breadth-first search explores a graph or grid one layer at a time from a start, so the first time it reaches a node is along a shortest path in edges. Shortest paths in an unweighted maze, level-order traversal, the minimum number of moves, and "rotting oranges"-style spreading processes are all BFS with a queue and a visited set; these problems practise setting that up cleanly.

How breadth-first search works, step by step

Ad=0Bd=1Cd=1Dd=2Ed=2Fd=3Gd=4queueempty
Breadth-first search from A, level by level. Example: edges = A–B, A–C, B–D, C–D, C–E, D–F, E–F, F–G; start = A
  1. Start at A: its distance is 0, it is marked as seen, and it is the only node in the queue. The queue is what keeps the search in order of distance.
  2. Take A off the front (distance 0). Its unseen neighbours B and C are marked at distance 1 and joined the back of the queue.
  3. Take B off the front (distance 1). Its unseen neighbour D is marked at distance 2 and joined the back of the queue; A was already seen and is skipped.
  4. Take C off the front (distance 1). Its unseen neighbour E is marked at distance 2 and joined the back of the queue; A and D were already seen and are skipped.
  5. Take D off the front (distance 2). Its unseen neighbour F is marked at distance 3 and joined the back of the queue; B and C were already seen and are skipped.
  6. Take E off the front (distance 2). Every neighbour (C and F) is already marked, so nothing is added.
  7. Take F off the front (distance 3). Its unseen neighbour G is marked at distance 4 and joined the back of the queue; D and E were already seen and are skipped.
  8. Take G off the front (distance 4). Every neighbour (F) is already marked, so nothing is added.
  9. The queue is empty and every node has its shortest distance from A in edges — G is the farthest at 4. The marked edges are the BFS tree: following them back from any node gives a shortest path. Each node and edge was handled once: O(V + E).

Breadth-First Search study plan

12 of the 65 Breadth-First Search problems (2 easy, 7 medium and 3 hard) over 8 days, about 7 h 30 min in all — the pattern first, then easiest to hardest. After that, the other 53 in the full list below are practice at your own pace. Then move on to Depth-First Search.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

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.

Next topic: Depth-First Search

Breadth-First Search: the essentials

When to reach for it

"The minimum number of moves, steps or transformations" where every move costs the same; something spreading from several sources at once (fire, infection, the distance to the nearest exit); and nodes that are generated rather than given — words one letter apart, lock combinations, board states. Once edges carry different weights, BFS stops giving shortest paths: use Dijkstra's algorithm, or a deque-based 0-1 BFS when the weights are only 0 and 1.

The pattern

Put the start, or every source, in a queue and mark it seen. Pop a node and push each unseen neighbour, marking it the moment it is pushed. Distances fall out of the order: everything at distance d leaves the queue before anything at d + 1. Graphs given as edges need an adjacency list first — see Graph.

from collections import deque

def bfs(start, neighbours):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in neighbours(node):
            if nxt not in dist:     # mark on push, not on pop
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

Cost

O(V + E) time and O(V) space; on an m × n grid with four moves per cell, O(m × n).

Common mistakes

  • Marking a node when it is popped instead of when it is pushed, so it enters the queue many times.
  • Using list.pop(0) in Python or shift() in JavaScript as the dequeue, which can cost O(n) per pop; use a deque or a head index.
  • Running a multi-source problem once per source instead of seeding the queue with all of them.
  • Counting the start as step 1 instead of step 0.

Start with

All breadth-first search problems

Easy (2)

Medium (48)

Hard (15)

Companies that ask breadth-first search problems

  • Amazon 59 problems on breadth-first search
  • Google 57 problems on breadth-first search
  • Microsoft 20 problems on breadth-first search
  • Meta 17 problems on breadth-first search
  • Uber 5 problems on breadth-first search
  • Adobe 3 problems on breadth-first search
  • Apple 2 problems on breadth-first search
  • Flipkart 2 problems on breadth-first search
  • LinkedIn 2 problems on breadth-first search
  • Salesforce 2 problems on breadth-first search
  • Swiggy 2 problems on breadth-first search
  • Accenture 1 problem on breadth-first search

Next topic: Depth-First Search