Airplane Seat Assignment Probability: Mathematical Insight

There are n passengers boarding a plane with n seats numbered from 1 to n. The first passenger has lost their ticket and picks a random seat. Each subsequent passenger sits in their own assigned seat if it is available, or picks a random seat from the remaining empty seats. Return the probability that the nth passenger sits in their own seat.

This is LeetCode 1227: Airplane Seat Assignment Probability, and it is one of the best examples of a problem where mathematical insight collapses an apparently complex simulation into a single elegant observation.

Why this problem matters

At first glance, this looks like it requires a full probability simulation. You might think about tracking every possible permutation of seat assignments, computing conditional probabilities at each step, or writing a dynamic programming recurrence over subsets. That instinct is not wrong, but it leads to unnecessary complexity.

The real lesson here is recognizing when a problem has a closed-form answer. Many interview problems in the math/probability category reward you for stepping back and looking for patterns in small cases before jumping into code. Once you see the pattern, the solution is trivial. The skill is in the mathematical reasoning, not the implementation.

This type of pattern recognition shows up in problems like "Nim Game" (LeetCode 292), "Bulb Switcher" (LeetCode 319), and "Stone Game" (LeetCode 877), where the answer simplifies dramatically once you identify the underlying structure.

The key insight

Think about what happens when passenger 1 picks a random seat. There are only three outcomes that matter:

1. Passenger 1 picks seat 1 (their own seat). Now everyone else sits in their assigned seat, and passenger n gets seat n. This happens with probability 1/n.

2. Passenger 1 picks seat n (the last passenger's seat). Passenger n is guaranteed to lose their seat. This also happens with probability 1/n.

3. Passenger 1 picks seat k (where 1 < k < n). Passengers 2 through k-1 all find their assigned seats available and sit normally. Passenger k is the first person displaced. They now face the exact same problem: pick randomly from the remaining seats. The only seats that matter are seat 1 and seat n, because every other displaced person will eventually reduce the problem to the same binary choice.

By induction, whenever someone is displaced, the probability that the chain ends with seat 1 being taken (good for passenger n) equals the probability that seat n is taken (bad for passenger n). These two outcomes are symmetric, giving exactly 1/2.

For n = 1, the answer is 1 because there is only one passenger and one seat. For any n >= 2, the answer is always 1/2.

The solution

def nth_person_gets_nth_seat(n: int) -> float:
    if n == 1:
        return 1.0
    return 0.5

That is the entire solution. Let's walk through why.

The function checks whether n is 1. If so, the single passenger has only one seat to pick, which is their own. The probability is 1.0.

For any n >= 2, the recursive reasoning shows that the probability is always 0.5. The symmetry argument holds regardless of how many passengers there are: the last seat to be resolved is always equally likely to be seat 1 or seat n.

You can also arrive at this through a DP recurrence. Define f(n) as the probability the last passenger gets their seat. You get f(n) = (1/n) * 1 + (1/n) * 0 + sum over k from 2 to n-1 of (1/n) * f(n-k+1). Working through this recurrence, it simplifies to f(n) = 1/2 for all n >= 2. But knowing the closed form means you do not need to compute anything.

Visual walkthrough

Let's trace through how the probability works out for small values of n, building up to the general pattern.

The key observation across all cases is the symmetry: every displaced passenger creates a sub-problem where the "good" outcome (seat 1 gets taken, freeing up the chain) and the "bad" outcome (seat n gets taken) are equally likely. This symmetry is what makes the answer exactly 1/2, regardless of n.

Complexity analysis

Time is O(1). The answer is a constant lookup based on whether n equals 1 or not. No iteration, no recursion, no simulation.

Space is O(1). No data structures are needed. The function returns a floating point number directly.

You could also solve this with DP in O(n) time and O(n) space, but there is no reason to once you know the closed-form answer.

The building blocks

1. Recognizing closed-form patterns

def check_small_cases(n_max: int) -> list[float]:
    results = []
    for n in range(1, n_max + 1):
        prob = simulate(n, trials=100000)
        results.append(round(prob, 2))
    return results

Before trying to prove anything, simulate or hand-trace the first few cases. If f(2) = 0.5, f(3) = 0.5, f(4) = 0.5, that is your signal. This "guess and verify" approach is a building block for many math problems. You identify the pattern empirically, then confirm it with induction or algebraic manipulation.

2. Symmetry arguments in probability

def nth_person_gets_nth_seat(n: int) -> float:
    if n == 1:
        return 1.0
    return 0.5

The core technique is the symmetry argument: seat 1 and seat n are the only two seats that determine the final outcome, and they are equally likely to be the last one taken. This "two critical items" reasoning shows up whenever a random process has a binary terminal state. You will see it in card shuffling problems, random walk problems, and game theory questions.

Edge cases

Before submitting, think through these scenarios:

• n = 1: Only one passenger and one seat. They always get their own seat. Return 1.0.
• n = 2: Passenger 1 picks randomly between 2 seats. Passenger 2 gets their seat with probability 1/2. Return 0.5.
• Very large n: The answer is still 0.5. No overflow, no precision issues with a constant return value.
• n = 100: Even with 100 passengers, the probability is exactly 0.5. The chain of displaced passengers always resolves to the same symmetric outcome.

From understanding to recall

You have seen why the answer is 1/2 for all n >= 2: the symmetry between seat 1 and seat n makes the outcome a fair coin flip no matter how many passengers are in between. The proof is elegant, and the code is two lines.

But the challenge in an interview is not knowing the answer exists. It is arriving at it under pressure. The trap is diving into a DP table or a simulation when the problem is asking you to think, not code. Spaced repetition helps you build the reflex of checking small cases first, spotting constant patterns, and reaching for symmetry arguments. After a few practice rounds, you see "random process with a binary outcome" and immediately think "check for symmetry."

Related posts

• Climbing Stairs - Another problem where the recursive structure reveals a clean pattern
• Coin Change - DP problem where understanding the recurrence is the hard part
• Nim Game - Game theory problem with a closed-form solution based on modular arithmetic

CodeBricks breaks Airplane Seat Assignment Probability into its mathematical reasoning and pattern recognition building blocks, then drills them independently with spaced repetition. You practice identifying closed-form solutions and symmetry arguments from scratch until the approach is automatic. When a math problem shows up in your interview, you do not simulate. You think.