#1227

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Airplane Seat Assignment Probability

Calculate the probability that the last passenger sits in their assigned seat using state transition dynamic programming for airplanes.

math dynamic programming brainteaser probability and statistics

Problem Statement

n passengers board a plane with exactly n seats. The first passenger has lost their ticket and picks a seat at random. Each subsequent passenger takes their assigned seat if available, or a random remaining seat if their seat is occupied. Determine the probability that the last passenger ends up in their own seat.

Given 1 <= n <= 105, return the probability as a floating-point number. For example, if n = 1, the output is 1.00000 since the first passenger only has one choice. For n = 2, the probability is 0.50000 because the first passenger randomly selects a seat, possibly displacing the second passenger.

Examples

Example 1

Input: n = 1

Output: 1.00000

The first person can only get the first seat.

Example 2

Input: n = 2

Output: 0.50000

The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

Constraints

1 <= n <= 105

Solution Approach

Recursive State Transition

Define f(n) as the probability the nth passenger gets their seat. Base cases: f(1) = 1 and f(2) = 0.5. For n > 2, the first passenger can choose either their own seat, the nth seat, or any other. Use f(n) = 1/n + (n-2)/n * f(n-1) to recursively compute probabilities.

Iterative Dynamic Programming

Instead of recursion, build up from f(1) and f(2) iteratively. Maintain a single probability value and update in O(n) time. This avoids call stack overhead while following the same state transition logic, reflecting the chain of random seat selections.

Mathematical Simplification

Observe that for n >= 2, the probability converges to 0.5. The random first choice either immediately blocks or leaves the last seat untouched, making the closed-form solution f(n) = 0.5 for n > 1. This insight reduces computation and directly applies the pattern of state-dependent probabilities.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for iterative or recursive computation but reduces to O(1) using the mathematical simplification. Space complexity is O(1) if storing only the current probability value, otherwise O(n) for full DP array.

What Interviewers Usually Probe

Check if the candidate identifies the base cases f(1) and f(2) quickly.
Look for recognition of the state transition pattern in seat selection probabilities.
Evaluate if the candidate can simplify to the constant probability insight for n > 1.

Common Pitfalls or Variants

Common pitfalls

Ignoring the first passenger's random choice effect on subsequent probabilities.
Attempting full permutation simulation, which is unnecessary and inefficient.
Failing to correctly implement the state transition formula f(n) = 1/n + (n-2)/n * f(n-1).

Follow-up variants

Compute the probability if the first k passengers choose randomly instead of only the first passenger.
Determine the expected number of displaced passengers using similar DP state transitions.
Extend the problem to a plane with multiple seat classes affecting passenger choices.

FAQ

What is the pattern used in Airplane Seat Assignment Probability?

The pattern is a state transition dynamic programming approach where each passenger's probability depends on previous seat selections.

Why is the probability 0.5 for n > 1?

Because the first passenger's random seat choice either blocks the last seat or leaves it untouched, making the outcome equally likely.

Can I solve this problem without recursion?

Yes, an iterative DP approach or direct mathematical observation allows computing the probability efficiently without recursion.

What are common mistakes to avoid?

Ignoring the first passenger's impact, simulating all permutations, or misapplying the state transition formula are typical pitfalls.

Does GhostInterview provide a closed-form solution?

Yes, it can recognize the constant probability simplification and return f(n) = 0.5 for n > 1 instantly.

terminal

Solution

Solution 1: Mathematics

Let $f(n)$ represent the probability that the $n$th passenger will sit in their own seat when there are $n$ passengers boarding. Consider from the simplest case:

1

2

3

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

Continue Practicing

#1025 divisor game #1467 probability of a two boxes having the same number of distinct balls #837 new 21 game