LeetCode 1227 - Airplane Seat Assignment Probability

LeetCode Problem 1227

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Brainteaser, Probability and Statistics

Solution

Problem Understanding

This problem involves a scenario with n passengers and n seats on an airplane. Each passenger has a designated seat, but the first passenger has lost their ticket and picks a seat randomly. Every subsequent passenger will either take their own seat if it is unoccupied or select a random available seat if their seat is already taken. The problem asks for the probability that the last, or nth, passenger ends up sitting in their own assigned seat.

The input n represents the total number of passengers (and seats), and it can range from 1 to 100,000. The output should be a floating-point number between 0 and 1 that represents the probability that the nth passenger gets their own seat.

The constraints suggest that a brute-force simulation checking every possible seating arrangement is infeasible for large n because the number of permutations grows factorially. Important edge cases include n = 1, where the probability is trivially 1, and n = 2, where randomness comes into play for the first passenger. The problem guarantees that n >= 1, so we do not need to handle zero or negative passengers.

Approaches

A brute-force approach would simulate all possible seating arrangements recursively or using dynamic programming, keeping track of which seats are taken and counting scenarios where the nth passenger ends up in their seat. While this is correct, the time complexity is factorial, which is infeasible for n up to 100,000.

The key insight is that the problem has a surprisingly simple pattern. For any n > 1, the probability that the nth passenger gets their seat is always 0.5. This is because only two events affect the last seat: either the first passenger sits in the nth seat directly (probability 1/n), or eventually, the chain of displaced passengers leaves the last seat for the nth passenger. Recursive reasoning or induction shows that this stabilizes to 0.5 for all n >= 2. For n = 1, the probability is 1.

This insight allows for an O(1) solution without simulation or recursion.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Simulates all seat arrangements recursively; infeasible for large n
Optimal	O(1)	O(1)	Uses the observation that probability is 1 for n = 1 and 0.5 for n >= 2

Algorithm Walkthrough

1. Check if n equals 1. If so, return 1.0 because the only passenger must sit in their seat.
2. For all n >= 2, return 0.5. This is based on the invariant that the first passenger introduces exactly two possible outcomes for the last seat: either taken by the first passenger or left for the nth passenger after a chain of displacements.
3. Return the probability as a floating-point number.

Why it works: The first passenger creates a scenario where the last seat can either be chosen immediately by the first passenger or remain until the last passenger boards. Recursive reasoning shows that every intermediate passenger either preserves or randomly redistributes the available seats in a way that, by symmetry, makes the probability of the nth passenger getting their own seat exactly 0.5 for all n >= 2.

Python Solution

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        if n == 1:
            return 1.0
        return 0.5

This implementation checks if n is 1 and handles that trivial case with probability 1. For all other cases, it returns 0.5, capturing the probabilistic pattern established by the first passenger’s random choice. There is no need for loops or recursion, making it extremely efficient.

Go Solution

func nthPersonGetsNthSeat(n int) float64 {
    if n == 1 {
        return 1.0
    }
    return 0.5
}

The Go implementation mirrors the Python logic. There are no special data structures, and all cases are handled with a simple conditional. The function returns a float64 to match the problem’s requirement.

Worked Examples

Example 1: n = 1

Since there is only one passenger and one seat, they must sit in their seat. The output is 1.0.

Step	Passenger	Action	Notes
1	1	Takes seat 1	Only seat available
Result	-	-	Probability = 1.0

Example 2: n = 2

The first passenger picks a random seat. Two possibilities exist: they take seat 1 (probability 0.5) or seat 2 (probability 0.5). Only in the first scenario does the second passenger get their seat. The output is 0.5.

Step	Passenger	Action	Notes
1	1	Takes seat 1 or 2	Random
2	2	Takes own seat if available	Probability = 0.5
Result	-	-	Probability = 0.5

Example 3: n = 3

Either the first passenger picks seat 1 (good), seat 2 (displaces 2), or seat 3 (bad for 3). Recursive probability analysis still yields 0.5 for the third passenger.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	No loops or recursion; single conditional check
Space	O(1)	Constant space; no data structures used

The reasoning is straightforward: the solution requires only a single conditional check and a constant return value, independent of n.

Test Cases

# test cases
sol = Solution()
assert sol.nthPersonGetsNthSeat(1) == 1.0  # trivial case
assert sol.nthPersonGetsNthSeat(2) == 0.5  # smallest non-trivial case
assert sol.nthPersonGetsNthSeat(3) == 0.5  # small n, check pattern
assert sol.nthPersonGetsNthSeat(10) == 0.5 # arbitrary n
assert sol.nthPersonGetsNthSeat(100000) == 0.5 # large n

Test	Why
1	Trivial case where only one passenger exists
2	First non-trivial case where randomness affects probability
3	Confirms pattern holds for small n
4	Validates correctness for arbitrary moderate n
5	Confirms solution works efficiently for maximum input constraint

Edge Cases

Single Passenger: When n = 1, the probability is trivially 1. A naive implementation that does not handle this might incorrectly return 0.5.

Two Passengers: When n = 2, the first passenger introduces randomness that directly affects the second passenger. Ensuring that this probability is correctly calculated is critical for correctness.

Large n: For n up to 100,000, a brute-force or recursive solution would be too slow and exceed memory limits. The optimal solution avoids iteration entirely, making it safe for extreme input sizes without overflow or performance issues.