Problem Description

The Airplane Seat Assignment Probability problem is a classic probability puzzle. There are n passengers boarding an airplane with exactly n seats. Each passenger has a ticket for a specific seat, and they board the plane in order. The twist is that the first passenger loses their ticket and randomly picks any seat to sit in. Every subsequent passenger:

• If their assigned seat is empty, they sit in it.
• If their seat is already taken, they randomly choose one of the remaining unoccupied seats.

Constraints:

• 1 ≤ n ≤ 10⁵
• All passengers act independently and randomly if their seat is taken.

Thought Process

At first glance, this problem seems to require simulating all possible seat assignments and counting the cases where the last passenger gets their own seat. However, this approach is not efficient for large n.

Let's think about the process:

• The first passenger can choose any seat at random.
• If the first passenger picks their own seat, every other passenger gets their own seat, and the last passenger sits in their assigned seat.
• If the first passenger picks the last passenger's seat, the last passenger will not get their own seat.
• If the first passenger picks any other seat, the problem repeats itself with one less seat and one less passenger.

Solution Approach

Let's formalize the reasoning:

1. Let P(n) be the probability that the nth passenger sits in their own seat.
2. The first passenger has n choices:
   • If they pick their own seat (probability 1/n), everyone gets their assigned seat, so the last passenger does too.
   • If they pick the last passenger's seat (probability 1/n), the last passenger cannot sit in their own seat.
   • If they pick any other seat (probability (n-2)/n), the problem reduces to the same scenario with n-1 seats and passengers.
3. This gives the recurrence:
   • P(n) = 1/n * 1 + 1/n * 0 + (n-2)/n * P(n-1)
4. For n = 1, obviously P(1) = 1.
5. For n = 2, P(2) = 1/2 * 1 + 1/2 * 0 = 0.5.
6. With some algebra or induction, you find that for n ≥ 2, P(n) = 0.5.

Conclusion: For n = 1, the answer is 1.0. For n ≥ 2, the answer is 0.5.

Thus, we can solve this in O(1) time with a simple conditional check.

Example Walkthrough

Let's walk through the case where n = 3:

• Passenger 1 randomly picks seat 1, 2, or 3.
• Case 1: Picks seat 1 (their own seat, probability 1/3).
  Passengers 2 and 3 sit in their own seats. Passenger 3 gets their own seat.
• Case 2: Picks seat 2 (probability 1/3).
  Passenger 2 finds their seat taken, so randomly picks between seats 1 and 3.
  
  • If picks seat 1, passenger 3 gets their own seat.
  • If picks seat 3, passenger 3 does not get their own seat.
  Each subcase is 1/2, so overall:
  • Passenger 3 gets their own seat: 1/3 * 1/2 = 1/6
  • Passenger 3 does not: 1/3 * 1/2 = 1/6
• Case 3: Picks seat 3 (last passenger's seat, probability 1/3).
  Passenger 3 cannot sit in their own seat.

Total probability passenger 3 gets their own seat:
1/3 (Case 1) + 1/6 (Case 2 subcase) = 0.5

Time and Space Complexity

Brute-force approach: Simulating all permutations would take O(n!) time and space, which is infeasible for large n.

Optimized approach: Using the recursive insight and closed-form solution, we simply check if n == 1 or not, so:

• Time Complexity: O(1)
• Space Complexity: O(1)

Summary

The Airplane Seat Assignment Probability problem looks complex at first, but by breaking it down and recognizing its recursive, self-similar structure, we discover that the probability the last passenger gets their own seat is always 0.5 for n ≥ 2. This allows for an elegant O(1) solution with just a simple check. This is a great example of how understanding the underlying process can lead to a dramatic simplification of what appears to be a complicated problem.

Code Implementation

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

class Solution {
public:
    double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0 : 0.5;
    }
};
      

class Solution {
    public double nthPersonGetsNthSeat(int n) {
        return n == 1 ? 1.0 : 0.5;
    }
}
      

var nthPersonGetsNthSeat = function(n) {
    return n === 1 ? 1.0 : 0.5;
};