Airplane Seat Assignment Probability - Video Solutions
Leetcode 1227. Airplane Seat Assignment Probability
Airplane Seat Assignment Probability - Video Solution
Watch 10 video solutions for Airplane Seat Assignment Probability, a medium level problem involving Math, Dynamic Programming, Brainteaser. This walkthrough by Math Geeks has 2,759 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of the passengers will:
- Take their own seat if it is still available, and
- Pick other seats randomly when they find their seat occupied
Return the probability that the nth person gets his own seat.
Example 1:
Input: n = 1 Output: 1.00000 Explanation: The first person can only get the first seat.
Example 2:
Input: n = 2 Output: 0.50000 Explanation: 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
Approach Overview
Problem Overview: An airplane has n passengers and n seats. The first passenger loses their ticket and picks a random seat. Every other passenger takes their assigned seat if available, otherwise chooses a random remaining seat. The task is to compute the probability that the last passenger ends up in their own seat.
Approach 1: Dynamic Programming / Recurrence Modeling (Time: O(n), Space: O(n))
The process can be modeled using a recurrence. Let dp[i] represent the probability that the last passenger gets their own seat when there are i passengers remaining. When the first passenger chooses a seat, three outcomes matter: they take their own seat (probability 1/i), they take the last passenger's seat (probability 1/i), or they take some other passenger's seat (probability (i-2)/i). If another passenger's seat is taken, the situation reduces to the same problem with i-1 passengers. This gives the recurrence dp[i] = 1/i + (i-2)/i * dp[i-1]. Iterate from the base case to n to compute the probability. This approach demonstrates how probabilistic processes can be modeled with dynamic programming and recurrence relations.
Approach 2: Mathematical Analysis (Time: O(1), Space: O(1))
The recurrence simplifies dramatically with mathematical reasoning. The only seats that ultimately matter are the first passenger's seat and the last passenger's seat. Every time someone is forced to pick randomly, the process effectively restarts with the same structure. The chain continues until someone chooses either seat 1 or seat n. Both are equally likely, which leads to a constant result: if n == 1, the probability is 1; for any n >= 2, the probability is exactly 0.5. This insight turns the problem into a simple formula derived from mathematical reasoning and probability analysis.
Recommended for interviews: Interviewers typically expect the mathematical insight after you reason through the recurrence. Showing the dynamic programming formulation demonstrates clear understanding of the process, while deriving the constant 0.5 result proves strong analytical thinking. In practice, the optimal implementation returns 1 when n == 1 and 0.5 otherwise.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming / Recurrence | O(n) | O(n) | When deriving the probability step‑by‑step or demonstrating reasoning in interviews |
| Mathematical Analysis | O(1) | O(1) | Optimal solution once the probabilistic pattern is recognized |