Problem Description

You have an airplane with exactly n seats and n passengers waiting to board. The first passenger has lost their ticket and will pick a seat randomly. After the first passenger, each subsequent passenger follows this rule:

• If their assigned seat is still available, they will take it
• If their assigned seat is already occupied, they will pick any other available seat randomly

The problem asks you to find the probability that the last passenger (the nth person) will end up sitting in their own assigned seat (seat n).

For example:

• If n = 1: There's only one passenger and one seat, so they must sit in their own seat. Probability = 1.0
• If n = 2: The first passenger randomly picks either seat 1 or seat 2. If they pick seat 1, passenger 2 gets seat 2 (their own seat). If they pick seat 2, passenger 2 must take seat 1. Probability = 0.5

The mathematical analysis reveals that for any n ≥ 2, the probability is always 0.5. This counterintuitive result occurs because throughout the boarding process, either seat 1 or seat n will eventually be taken, and these two outcomes are equally likely. Once one of these "critical" seats is taken, the fate of the last passenger is determined - if seat 1 is taken first, the last passenger gets their own seat; if seat n is taken first, they don't.

Intuition

The key insight is to recognize that only two seats truly matter in this problem: seat 1 (the first passenger's assigned seat) and seat n (the last passenger's assigned seat).

Think about it this way: as passengers board, whenever someone needs to pick a random seat (either the first passenger or anyone who finds their seat taken), they create a "chain reaction." However, this chain will eventually stop when either seat 1 or seat n is taken:

• If seat 1 gets taken at any point, all remaining passengers can sit in their assigned seats (since no one else is assigned to seat 1)
• If seat n gets taken at any point, the last passenger definitely won't get their seat

For passengers 2 through n-1, if their seat is taken, they become "random choosers" just like passenger 1. They're equally likely to pick any available seat, including seats 1 and n.

Here's the crucial realization: throughout the entire boarding process, seat 1 and seat n have equal probability of being chosen first. Why? Because:

1. The first passenger picks randomly among all n seats
2. Any passenger who finds their seat taken also picks randomly among available seats
3. The symmetry between seat 1 and seat n is preserved throughout

Since exactly one of these two outcomes must occur (either seat 1 or seat n gets taken first), and they're equally likely, the probability that seat n remains available for the last passenger is exactly 0.5.

The special case when n = 1 is trivial - with only one passenger and one seat, they must sit in their own seat, giving probability 1.0.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses a mathematical approach to derive the probability formula. Let's define f(n) as the probability that the nth passenger sits in their own seat when there are n passengers.

Base Cases:

• When n = 1: Only one passenger and one seat, so f(1) = 1.0
• When n = 2: First passenger randomly picks from 2 seats with equal probability. If they pick seat 1, passenger 2 gets seat 2. If they pick seat 2, passenger 2 gets seat 1. Therefore, f(2) = 0.5

Recursive Analysis for n > 2:

When the first passenger boards, they randomly choose from n seats:

1. Probability 1/n of choosing seat 1: All subsequent passengers sit in their assigned seats, so P(n gets seat n) = 1.0
2. Probability 1/n of choosing seat n: The last passenger definitely won't get their seat, so P(n gets seat n) = 0.0
3. Probability (n-2)/n of choosing seat i where 2 ≤ i ≤ n-1: Passengers 2 through i-1 sit normally, but passenger i finds their seat taken and must randomly choose from the remaining n-i+1 seats. This reduces the problem to size n-i+1.

This gives us the recursive formula:

f(n) = (1/n) × 1.0 + (1/n) × 0.0 + (1/n) × Σ(i=2 to n-1) f(n-i+1)
f(n) = (1/n) × (1.0 + Σ(i=2 to n-1) f(n-i+1))

Simplification:

By setting up a similar equation for f(n-1) and performing algebraic manipulation:

n × f(n) = 1.0 + Σ(i=2 to n-1) f(n-i+1)
(n-1) × f(n-1) = 1.0 + Σ(i=2 to n-2) f(n-i)

Subtracting these equations and simplifying:

n × f(n) - (n-1) × f(n-1) = f(n-1)
n × f(n) = n × f(n-1)
f(n) = f(n-1)

Since f(2) = 0.5 and f(n) = f(n-1) for all n ≥ 3, we conclude that f(n) = 0.5 for all n ≥ 2.

Final Implementation:

The solution simply returns:

• 1.0 if n = 1
• 0.5 if n ≥ 2

This elegant result shows that regardless of how many passengers board (as long as n ≥ 2), the last passenger has exactly a 50% chance of getting their assigned seat.

Example Walkthrough

Let's walk through a concrete example with n = 4 passengers to illustrate why the probability is 0.5.

Setup: 4 passengers, 4 seats. Passenger 1 lost their ticket, passengers 2-4 have assigned seats 2-4 respectively.

Scenario Analysis:

When passenger 1 boards, they randomly choose from seats {1, 2, 3, 4}:

Case 1: Passenger 1 picks seat 1 (probability 1/4)

• Passenger 2 boards → sits in seat 2 ✓
• Passenger 3 boards → sits in seat 3 ✓
• Passenger 4 boards → sits in seat 4 ✓
• Result: Passenger 4 gets their own seat

Case 2: Passenger 1 picks seat 4 (probability 1/4)

• Passenger 2 boards → sits in seat 2 ✓
• Passenger 3 boards → sits in seat 3 ✓
• Passenger 4 boards → only seat 1 available, must take it
• Result: Passenger 4 does NOT get their own seat

Case 3: Passenger 1 picks seat 2 (probability 1/4)

• Passenger 2 boards → seat 2 taken, randomly picks from {1, 3, 4}
  • If picks seat 1 (prob 1/3): Passengers 3 and 4 sit normally → P4 gets seat 4 ✓
  • If picks seat 4 (prob 1/3): P3 sits normally, P4 forced to seat 1 → P4 doesn't get seat 4
  • If picks seat 3 (prob 1/3): P3 must randomly pick from {1, 4}
    • If P3 picks seat 1 (prob 1/2): P4 gets seat 4 ✓
    • If P3 picks seat 4 (prob 1/2): P4 doesn't get seat 4

Case 4: Passenger 1 picks seat 3 (probability 1/4)

• Similar analysis to Case 3

Calculating the probability:

Notice the pattern - whenever a "random chooser" appears (P1 initially, or any passenger who finds their seat taken), they're equally likely to end the uncertainty by picking either seat 1 or seat 4. Once either of these "critical" seats is taken:

• If seat 1 is taken → P4 gets their seat
• If seat 4 is taken → P4 doesn't get their seat

The key insight: Throughout all possible boarding sequences, seat 1 and seat 4 have equal probability of being chosen first among the two. Since one of them must eventually be chosen, and they determine P4's fate with opposite outcomes, the probability is exactly 0.5.

Verification: P(P4 gets seat 4) = 1/4 × 1 + 1/4 × 0 + 1/4 × (1/3 + 1/3 × 1/2) + 1/4 × (1/3 + 1/3 × 1/2) = 1/4 + 0 + 1/4 × 1/2 + 1/4 × 1/2 = 1/4 + 1/8 + 1/8 = 1/2 = 0.5

This confirms that for n=4 (and indeed any n≥2), the probability is 0.5.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(1) because the function performs a simple conditional check and returns a constant value. Regardless of the input size n, the function executes a fixed number of operations - it checks if n == 1 and returns either 1 or 0.5. No loops or recursive calls are involved.

The space complexity is O(1) because the function uses only a constant amount of additional memory. It doesn't create any data structures that grow with the input size n. The function only stores and returns a single floating-point value, which requires a fixed amount of memory regardless of the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Simulate the Random Process

Many people's first instinct is to simulate the boarding process with random number generation to estimate the probability. This approach has several issues:

• It's computationally expensive for large n
• It provides only an approximation, not the exact answer
• It misses the elegant mathematical insight

Wrong Approach:

import random

def nthPersonGetsNthSeat(n: int) -> float:
    simulations = 10000
    success = 0
  
    for _ in range(simulations):
        seats = [False] * n
        # First passenger picks randomly
        seats[random.randint(0, n-1)] = True
      
        # Other passengers board
        for passenger in range(1, n):
            if not seats[passenger]:  # Their seat is available
                seats[passenger] = True
            else:  # Pick random available seat
                available = [i for i in range(n) if not seats[i]]
                seats[random.choice(available)] = True
      
        # Check if last passenger got their seat
        if seats[n-1]:
            success += 1
  
    return success / simulations

2. Overcomplicating with Dynamic Programming

Some might try to build a complex DP solution tracking all possible states:

Overcomplicated Approach:

def nthPersonGetsNthSeat(n: int) -> float:
    if n == 1:
        return 1.0
  
    # dp[i] = probability that passenger i gets their seat
    dp = [0.0] * (n + 1)
    dp[1] = 1.0
    dp[2] = 0.5
  
    for i in range(3, n + 1):
        # Complex recursive calculation
        dp[i] = (1/i) + sum(dp[j] for j in range(2, i)) / i
  
    return dp[n]

This misses the key insight that the probability stabilizes at 0.5 for all n ≥ 2.

3. Incorrect Base Case Handling

A common error is forgetting the special case when n = 1:

Wrong Implementation:

def nthPersonGetsNthSeat(n: int) -> float:
    return 0.5  # Wrong! Fails for n = 1

4. Misunderstanding the Problem Statement

Some might confuse which passenger picks randomly:

• Correct: Only the first passenger always picks randomly (lost ticket)
• Wrong: Thinking all passengers pick randomly when their seat is taken

5. Trying to Track Individual Seat Assignments

Attempting to calculate probabilities for each specific seat configuration:

Inefficient Approach:

def nthPersonGetsNthSeat(n: int) -> float:
    # Try to track probability of each seat being taken
    seat_probs = [0.0] * n
    # Complex calculations for each passenger...
    # This quickly becomes intractable

Correct Solution

The key insight is recognizing the symmetry between seat 1 and seat n. Throughout the boarding process:

• Either seat 1 or seat n will eventually be taken
• These two outcomes are equally likely (probability 0.5 each)
• Once seat 1 is taken, all remaining passengers sit normally → passenger n gets seat n
• Once seat n is taken, passenger n cannot get seat n

Therefore, the solution is simply:

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

This constant-time solution captures the mathematical elegance of the problem without unnecessary complexity.