Airplane Seat Assignment Probability
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming based on a recurrence relation derived from the problem's state transitions. Let dp[i] be the probability that the i-th person gets their own seat. We can build a solution for n by solving for all i < n.
Algorithm
- Handle the base case
n = 1, returning1.0. - Create a
dparray of sizen + 1to store the probabilitiesdp[i]for thei-th person. - Set
dp[1] = 1.0. - Iterate from
i = 2ton:- Inside this loop, start another loop from
j = 2toi-1to calculate the sum of previous probabilitiesdp[j]. - Calculate
dp[i]using the formula:dp[i] = (1.0 / i) * (1.0 + sum).
- Inside this loop, start another loop from
- Return
dp[n].
Walkthrough
The probability for the n-th passenger, dp[n], can be defined recursively. The first passenger has n choices, each with probability 1/n.
- If they pick seat 1, all other passengers, including the
n-th, will get their own seats. This contributes(1/n) * 1to the total probability. - If they pick seat
n, then-th passenger cannot get their seat. This contributes(1/n) * 0. - If they pick seat
k(where1 < k < n), passengers2throughk-1take their own seats. When passengerkarrives, their seat is taken. They must choose a random seat from the remaining ones. This scenario effectively resets the problem to a smaller version withn-k+1passengers, where passengerkis the new 'first' passenger. The probability that the last passenger gets their seat in this subproblem isdp[n-k+1]. This leads to the recurrence relation:dp[i] = (1/i) * (1 + sum_{j=2}^{i-1} dp[j]). A naive DP solution computes this by iterating fromi=2tonand, for eachi, re-calculating the sum fromj=2toi-1.
public double nthPersonGetsNthSeat(int n) { if (n == 1) { return 1.0; } double[] dp = new double[n + 1]; dp[1] = 1.0; for (int i = 2; i <= n; i++) { double sumOfPrev = 0; for (int j = 2; j < i; j++) { sumOfPrev += dp[j]; } dp[i] = (1.0 / i) * (1.0 + sumOfPrev); } return dp[n];}Complexity
Time
O(n^2) due to the nested loops. The outer loop runs `n` times, and the inner loop runs up to `n` times.
Space
O(n) to store the `dp` array.
Trade-offs
Pros
It's a straightforward implementation of the derived recurrence relation.
It correctly solves the problem for small values of
n.
Cons
The
O(n^2)time complexity is inefficient and will result in a 'Time Limit Exceeded' error for the given constraints (nup to 10^5).
This approach improves upon the naive DP by optimizing the calculation of the sum. Instead of re-calculating the sum of previous probabilities in each step, we can maintain a running sum, which reduces the time complexity from O(n^2) to O(n).
Algorithm
- Handle the base case
n = 1, returning1.0. - Create a
dparray of sizen + 1. - Initialize a running sum variable
sumOfPrevProbs = 0.0. - Iterate from
i = 2ton:- Calculate
dp[i]using the formuladp[i] = (1.0 / i) * (1.0 + sumOfPrevProbs). - Update the running sum by adding the newly computed
dp[i]:sumOfPrevProbs += dp[i].
- Calculate
- Return
dp[n].
Walkthrough
The recurrence relation remains the same: dp[i] = (1/i) * (1 + sum_{j=2}^{i-1} dp[j]). We can observe that the sum required for dp[i] is sum_{j=2}^{i-1} dp[j], and for dp[i+1] it's sum_{j=2}^{i} dp[j]. The second sum is simply the first sum plus dp[i]. This allows us to avoid the inner loop by maintaining a single variable that accumulates the sum of probabilities as we compute them iteratively.
public double nthPersonGetsNthSeat(int n) { if (n == 1) { return 1.0; } double[] dp = new double[n + 1]; // Represents sum_{j=2}^{i-1} dp[j] in each iteration double sumOfPrevProbs = 0.0; for (int i = 2; i <= n; i++) { dp[i] = (1.0 / i) * (1.0 + sumOfPrevProbs); sumOfPrevProbs += dp[i]; } return dp[n];}Complexity
Time
O(n) because we iterate with a single loop from 2 to `n`, and each step takes constant time.
Space
O(n) for the `dp` array.
Trade-offs
Pros
Efficient enough to pass the given constraints.
Logically follows from optimizing the naive DP approach.
Cons
Uses
O(n)space for the DP table, which can be optimized toO(1)since we only need the running sum.
By analyzing the problem more deeply, either through simplifying the recurrence relation or through a symmetry argument, we can find a direct mathematical solution. The probability turns out to be 1.0 for n=1 and 0.5 for all n > 1.
Algorithm
- Check if
nis equal to 1. - If
n == 1, return1.0. - Otherwise (if
n > 1), return0.5.
Walkthrough
This optimal solution can be reached via two lines of reasoning:
1. Recurrence Simplification:
From the DP approach, we have n * dp[n] = 1 + sum_{j=2}^{n-1} dp[j]. For n-1, we have (n-1) * dp[n-1] = 1 + sum_{j=2}^{n-2} dp[j]. Subtracting these two equations for n > 2 yields n * dp[n] - (n-1) * dp[n-1] = dp[n-1]. This simplifies to n * dp[n] = n * dp[n-1], which means dp[n] = dp[n-1] for n > 2. Since we can calculate dp[2] = 0.5, it follows that dp[n] = 0.5 for all n >= 2.
2. Symmetry Argument:
The fate of the n-th passenger is sealed the moment any passenger sits in either Seat 1 or Seat n.
- If Seat 1 is taken by a displaced passenger, the chain of displacement ends, and all subsequent passengers, including passenger
n, get their correct seats. - If Seat
nis taken by a displaced passenger, passengerncannot get their seat. For any displaced passenger making a random choice, the available seats include Seat 1 and Seatn(assuming neither has been taken). Since the choice is random, Seat 1 and Seatnhave an equal probability of being chosen. Due to this symmetry, the two terminal outcomes are equally likely. Thus, the probability is0.5.
The case n=1 is trivial: the first passenger takes the only seat, so the probability is 1.
public double nthPersonGetsNthSeat(int n) { if (n == 1) { return 1.0; } else { return 0.5; }}Complexity
Time
O(1) as it involves a single conditional check.
Space
O(1) as no extra space proportional to the input size is used.
Trade-offs
Pros
Extremely efficient, providing a solution in constant time and space.
Very simple and concise code.
Cons
The solution relies on a non-trivial mathematical insight that might be difficult to derive under pressure.
Solutions
Solution
class Solution {public double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 :.5; }}class Solution {public: double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 : .5; }};class Solution: def nthPersonGetsNthSeat( self, n: int) -> float: return 1 if n == 1 else 0.5Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.