0-1 BFS: The Shortest-Path Trick Interviewers Love to See#

When every edge in a graph has weight 0 or 1, you do not need Dijkstra's priority queue. A double-ended queue (deque) gives you the same correct distances in O(V + E) instead of O((V + E) log V). This comes up more often in coding interviews than people expect, usually disguised as a grid problem.

How to recognise a 0-1 BFS problem#

Look for phrasing like:

The pattern: some moves are free, others cost exactly one unit.

The idea in one sentence#

Pop the front of the deque; for a 0-weight edge push the neighbour to the front, for a 1-weight edge push it to the back. The deque then always holds nodes in non-decreasing distance order (at most two distinct distance values at once), which is exactly the invariant Dijkstra's heap was maintaining for you.

Python template#

from collections import deque

def zero_one_bfs(n, adj, src):
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:          # w is 0 or 1
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

Note there is no visited set. A node can be pushed more than once, but only when its distance actually improves, and that can happen at most twice per node in practice, so the total work stays linear.

Worked example: minimum obstacles to remove#

Grid of 0s (empty) and 1s (obstacle). Moving into an empty cell costs 0, moving into an obstacle costs 1 (you remove it). Answer = distance to the bottom-right cell.

def minimum_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dist = [[float("inf")] * n for _ in range(m)]
    dist[0][0] = 0
    dq = deque([(0, 0)])
    while dq:
        r, c = dq.popleft()
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                w = grid[nr][nc]
                if dist[r][c] + w < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + w
                    (dq.appendleft if w == 0 else dq.append)((nr, nc))
    return dist[m-1][n-1]

Common mistakes interviewers watch for#

  1. Marking nodes visited on push. That is plain-BFS muscle memory and it breaks correctness here, because a cheaper 0-edge path may arrive later.
  2. Using it with weights other than 0/1. For small integer weights up to K, use Dial's algorithm (bucket queue) instead.
  3. Forgetting the complexity argument. Say it out loud: each node's distance only decreases, the deque is ordered, so it is O(V + E).

How to talk about it in the interview#

Start with "this is a shortest path with weights 0 and 1, so Dijkstra works, but a deque-based 0-1 BFS is linear." Then write the template, then adapt it. Interviewers reward that framing more than the code itself: it shows you picked the tool deliberately.

If you practise these patterns out loud, a real-time helper such as Linkjob AI can listen to mock interview questions and suggest structure for your explanation while you rehearse. (Disclosure: I work on Linkjob AI.)

Practice list#

Published with byagent