Bidirectional BFS and Meet in the Middle

Bidirectional search and meet in the middle are extension topics beyond most interviews; they pay off when a plain BFS or brute force is correct but too slow by an exponential factor, such as word-ladder style searches over huge implicit graphs or subset problems with n around 30 to 40.

Both rest on the same arithmetic: if a search explores about b^d states, two searches that each go halfway explore about 2 * b^(d/2) states, and that square-root saving turns hopeless searches into fast ones.

Intuition

Bidirectional BFS. Run BFS from the start and from the goal at the same time and stop when the two explored regions touch. Each side only needs to go about half the distance. Two rules keep it correct and fast:

• Expand whole layers, one side at a time, and always expand the smaller frontier. Then the first time a newly generated state is found in the other side's frontier, the total number of layers expanded is the shortest distance.
• The backward search must follow edges in reverse. For undirected graphs and reversible moves (changing one letter, turning a lock wheel) the neighbor function is the same in both directions.

Meet in the middle. Split the decisions into two halves. Enumerate every outcome of the first half and every outcome of the second half separately (2^(n/2) each instead of 2^n together), then combine: for each outcome of one half, look up the best matching outcome of the other half with a hash map, binary search or two pointers. Typical combinations:

• Sum equals or is closest to a target: sort one side's sums and binary search for target - s.
• A bit-mask state must reach a target state: hash map from mask to the cheapest way to reach it, and look up target ^ mask.
• Counting pairs: a hash map of counts (the four-arrays-sum-to-zero question is the smallest example: pair sums of two arrays against pair sums of the other two).

When to use it in interviews / OAs

• Shortest transformation sequences in huge implicit graphs where one-sided BFS times out: word ladder, open the lock, gene mutation, puzzle states.
• Subset or assignment problems with n between roughly 25 and 40, where 2^n is too many but 2^(n/2), about 10^6, is fine: closest subsequence sum, partition into two halves with minimum difference, toggling switches.
• Problems that can be split into two independent halves whose results combine through one equation (a + b = target, x ^ y = target).

Template

Bidirectional BFS

def bidirectional_bfs(start, goal, neighbors) -> int:
    """Fewest moves from start to goal in an undirected (or reversible) graph, or -1."""
    if start == goal:
        return 0
    front, back = {start}, {goal}
    seen = {start, goal}
    steps = 0
    while front and back:
        if len(front) > len(back):
            front, back = back, front  # always expand the smaller frontier
        steps += 1
        next_layer = set()
        for state in front:
            for t in neighbors(state):
                if t in back:  # the two searches meet
                    return steps
                if t not in seen:
                    seen.add(t)
                    next_layer.add(t)
        front = next_layer
    return -1

steps counts layers expanded on both sides combined, which is the length of the path through the meeting point. For word ladder, which counts words rather than moves, add one.

Meet in the middle on sums

The minimum of |sum(subset) - goal| over all subsets, for n up to about 40:

from bisect import bisect_left


def subset_sums(nums: list[int]) -> list[int]:
    sums = [0]
    for x in nums:
        sums += [s + x for s in sums]  # every old subset, with and without x
    return sums


def closest_subset_sum(nums: list[int], goal: int) -> int:
    half = len(nums) // 2
    left = subset_sums(nums[:half])
    right = sorted(subset_sums(nums[half:]))
    best = abs(goal)  # the empty subset
    for s in left:
        i = bisect_left(right, goal - s)
        for j in (i - 1, i):  # the closest values on either side of goal - s
            if 0 <= j < len(right):
                best = min(best, abs(s + right[j] - goal))
    return best

Meet in the middle on bit masks

n lights start off; pressing switch i toggles light i and every light connected to it. Find the fewest presses that turn every light on (n up to 35). Each half maps a resulting light pattern to the fewest presses producing it; a full solution pairs patterns whose XOR is "all on":

def min_switch_presses(n: int, edges: list[tuple[int, int]]) -> int:
    effect = [1 << i for i in range(n)]  # lights toggled by each switch
    for u, v in edges:
        effect[u] |= 1 << v
        effect[v] |= 1 << u
    target = (1 << n) - 1

    def best_by_pattern(switches) -> dict[int, int]:
        best = {0: 0}  # light pattern -> fewest presses
        for i in switches:
            for pattern, presses in list(best.items()):  # snapshot: press i at most once
                new = pattern ^ effect[i]
                if presses + 1 < best.get(new, n + 1):
                    best[new] = presses + 1
        return best

    left = best_by_pattern(range(n // 2))
    right = best_by_pattern(range(n // 2, n))
    total = min((p + left[target ^ q] for q, p in right.items() if target ^ q in left), default=-1)
    return total

Complexity

• Bidirectional BFS: about O(b^(d/2)) states instead of O(b^d), for branching factor b and distance d, in time and memory. In the worst case (for example, when one side has nothing to meet) it is no worse than one-sided BFS.
• Closest subset sum: O(2^(n/2) * n) to build and sort the halves, O(2^(n/2) * n) for the binary searches.
• Switch presses: O(2^(n/2)) states per half with dictionary operations.
• Memory is the real limit for meet in the middle: 2^20 is about 10^6 entries, fine; 2^25 in Python is already heavy.

Common pitfalls

• Expanding single states instead of whole layers in bidirectional BFS, which can report a path that is not the shortest.
• Directed graphs: the backward search needs reversed edges; reusing the forward neighbor function is wrong.
• Off-by-one in the answer: decide whether you count moves (edges) or states (nodes).
• Forgetting the empty subset (sum 0) on either side.
• Uneven split: put the extra element on one side, but keep both halves near n/2; a 10/30 split loses the benefit.
• Combining in O(m^2): pair the two lists with sorting plus binary search, two pointers or a hash map, never with a double loop.
• Constraints on the combination, such as "exactly n/2 elements on each side": group each half's sums by how many elements were chosen, and combine matching groups.

Interview variations

• Word ladder and minimum genetic mutation: bidirectional BFS over one-character changes.
• Open the lock: bidirectional BFS; dead ends are simply never generated.
• 4Sum II (count quadruples summing to 0 across four arrays): hash the pair sums of two arrays and look up the negated pair sums of the other two, O(n^2).
• Closest subsequence sum: the template above.
• Partition array into two arrays to minimize sum difference (2n elements, each side gets n): meet in the middle with sums grouped by count.
• Subset sum or knapsack with n about 40 and huge values, where DP over values is impossible: meet in the middle with sorting and prefix maxima.