Queues, Deques, BFS foundations

A queue is First-In-First-Out. Python's collections.deque gives you O(1) push/pop at both ends — always prefer it over list.pop(0) which is O(n).

Why BFS?

Breadth-First Search explores by distance from the source. On an unweighted graph or grid, the first time you reach a node is via the shortest path. That's the theoretical foundation for:

• Shortest path in a maze / grid
• Word-ladder (edit-distance-1 chains)
• Number of steps to spread infection
• Minimum knight moves on a chessboard

The BFS template

def bfs(start, is_goal, neighbors):
    seen = {start}
    q = deque([(start, 0)])
    while q:
        node, dist = q.popleft()
        if is_goal(node):
            return dist
        for n in neighbors(node):
            if n not in seen:
                seen.add(n)
                q.append((n, dist + 1))
    return -1  # unreachable

Copy that shape for every BFS problem. Change only neighbors and is_goal.

Deque as a monotonic queue

When you slide a window and need max/min of the window in O(1):

• Keep a deque of indices whose values are monotonically decreasing (for max).
• On push: drop from the tail while smaller than the new element.
• On slide: drop from the head if out of window.

The front of the deque is always the current window max.

Common traps

• seen set update timing. Add to seen when you enqueue, not when you dequeue — otherwise you enqueue the same node many times.
• Bidirectional BFS is a real speedup on huge graphs — start from both ends, meet in the middle.
• Grid neighbors — 4-connected vs 8-connected. Ask the interviewer if unclear.

Try it

1. Given a grid grid[[0..], [0..]] (0 = walkable, 1 = wall), find the shortest path length from (0,0) to (n-1, m-1).
2. Implement a queue using two stacks. (Classic interview warm-up.)