This problem asks for the probability that the last person boards an airplane and finds their assigned seat unoccupied, using state transitions. The first passenger chooses randomly, creating a chain of dependent seat choices for the following passengers. Using either a recursive or iterative dynamic programming approach, you track probabilities of each seat being taken and simplify to an exact closed-form probability.
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.
How GhostInterview Helps
- Automatically tracks state transitions and computes f(n) without manual recursive tracing.
- Highlights base cases and pattern recognition, reducing common mistakes in seat probability calculations.
- Provides iterative or closed-form solutions to directly answer the probability question efficiently.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Airplane Seat Assignment Probability instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Airplane Seat Assignment Probability from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Divisor Game is a game theory problem where players take turns subtracting divisors of a number n until one player loses.
Open problem page#1467 Probability of a Two Boxes Having The Same Number of Distinct BallsCompute the probability that two boxes contain the same number of distinct balls using careful combinatorial and DP methods.
Open problem page#837 New 21 GameCalculate the probability Alice reaches at most n points using state transition dynamic programming efficiently.
Open problem page