Bridge Crossing Puzzle: Four People, One Flashlight, 17 Minutes

The Bridge Crossing Puzzle: Four People, One Flashlight, 17 Minutes

The bridge-crossing puzzle is a classic interview question that appears at consulting interviews, FAANG behavioral rounds, and quant trading firms. The setup: four people must cross a bridge at night; only two can cross at a time; the flashlight (required) must travel with each crossing; people walk at different speeds. The naive answer (always escort the slowest) gives 19 minutes; the optimal answer uses a clever pairing trick to achieve 17 minutes. This guide covers the standard problem, the optimal solution, and the variants interviewers ask as follow-ups.

Problem Statement

Four people need to cross a narrow bridge at night.

• Person A: 1 minute to cross
• Person B: 2 minutes
• Person C: 5 minutes
• Person D: 10 minutes

Constraints:

• The bridge supports only 2 people at a time.
• One flashlight; whoever crosses must carry it.
• When two people cross together, they walk at the slower person’s pace.
• Find the minimum total crossing time.

The Naive Answer (19 Minutes)

“Always send the fastest person to escort each slow person across.” Walk through:

1. A and D cross (10 min, since D’s pace dominates). Time elapsed: 10.
2. A returns (1 min). Time elapsed: 11.
3. A and C cross (5 min). Time elapsed: 16.
4. A returns (1 min). Time elapsed: 17.
5. A and B cross (2 min). Time elapsed: 19.

Total: 19 minutes. Most candidates stop here. There’s a better answer.

The Optimal Answer (17 Minutes)

The trick: the two slow people (C and D) should cross together, so their combined pace is wasted on a single trip. Walk through:

1. A and B cross (2 min). Time elapsed: 2.
2. A returns (1 min). Time elapsed: 3.
3. C and D cross (10 min, since D’s pace dominates). Time elapsed: 13.
4. B returns (2 min). Time elapsed: 15.
5. A and B cross (2 min). Time elapsed: 17.

Total: 17 minutes.

Why this is better: in the naive answer, A escorts each slow person, meaning the two slowest people each cross with A — incurring D’s 10 minutes once and C’s 5 minutes once. In the optimal answer, the two slow people cross together (10 minutes), so the slow penalty is incurred only once for the combined trip.

Why the Optimal Answer Works

The strategy is to pair the two slowest people on a single trip. Their pace is wasted on one trip rather than two. To get them across, you need a “ferry” mechanism: have the two fastest cross first to set up flashlight returns, send the two slowest, then bring the flashlight back with one of the fast people for the final crossing.

The two strategies differ in when you “pay” for the slowest person’s pace:

• Naive: 1 + 10 + 1 + 5 + 1 + 2 = 20… wait, let me recount: 10 (A+D) + 1 (A back) + 5 (A+C) + 1 (A back) + 2 (A+B) = 19.
• Optimal: 2 (A+B) + 1 (A back) + 10 (C+D) + 2 (B back) + 2 (A+B) = 17.

Difference: 19 – 17 = 2 minutes. The savings come from sending C and D together (saving the second escort trip), at the cost of an extra 1-minute trip for B’s return.

Generalization to N People

For N people with crossing times t₁ ≤ t₂ ≤ … ≤ tₙ, two strategies exist for moving the two slowest across:

Strategy 1: Fastest person escorts

Cost = t₁ + t₂ + (any return) + … — fast person makes round trips.

For two slowest tₙ₋₁ and tₙ via fastest: t₁ + tₙ₋₁ + t₁ + tₙ.

Strategy 2: Two fastest set up a relay

Cost = 2t₂ + t₁ + tₙ.

Choose whichever is smaller. For the canonical 4-person problem with t = [1, 2, 5, 10]:

• Strategy 1: 1 + 5 + 1 + 10 = 17 (for moving C and D and the next-slowest)
• Strategy 2: 2(2) + 1 + 10 = 15 (then 2(1) for the final)

The dynamic programming generalization: at each step, pick the cheapest way to move the two slowest still on the start side. For arbitrary N, this is computed bottom-up.

def min_crossing_time(times: list[int]) -> int:
    """Minimum time for n people to cross with one flashlight."""
    times = sorted(times)
    n = len(times)
    if n == 0:
        return 0
    if n == 1:
        return times[0]
    if n == 2:
        return times[1]
    if n == 3:
        return times[0] + times[1] + times[2]

    # DP: ways to move k people across optimally
    # Move 2 slowest: either via fastest escort or two-fastest relay
    total = 0
    while n > 3:
        opt1 = times[0] + times[n - 1] + times[0] + times[n - 2]
        opt2 = times[1] + times[n - 1] + times[0] + times[1]
        total += min(opt1, opt2)
        n -= 2
    if n == 3:
        total += times[0] + times[1] + times[2]
    return total


# Test
print(min_crossing_time([1, 2, 5, 10]))     # 17
print(min_crossing_time([1, 2, 5, 10, 20])) # 31

Common Variations

Different times

The puzzle works with any 4 distinct times. The optimal strategy depends on whether t₁ + t₃ ≤ 2t₂ (use strategy 1) or not (use strategy 2). Some interviewers ask candidates to find the threshold.

Five or more people

Apply the DP. For 5 people with times [1, 2, 3, 4, 5], the answer is 1 + 5 + 1 + 4 + 1 + 3 + 2 = 17? Walk through carefully — or use the algorithm.

Three flashlights

Different problem. With multiple flashlights, the constraint loosens; the optimal time approaches the maximum single time (since people can spread out).

Probabilistic version

“Each person has a probability of falling off the bridge proportional to time spent.” Becomes an optimization problem balancing time against safety. Outside scope of typical interviews.

What Interviewers Test

• Recognize that the naive “fastest escort” approach isn’t optimal
• Find the trick (slowest two travel together)
• Verbalize the time-savings reasoning
• Compute the answer correctly

If you’ve heard the puzzle before, say so. The interviewer will pivot to a variation (different times, more people, or ask you to derive the threshold formula).

Frequently Asked Questions

See also: Burning Ropes Puzzle • Two-Eggs / 80-Floor Building • Fruit Jar Labeling Problem