Solution Explanation for Airplane Seat Assignment Probability

This problem asks for the probability that the nth passenger gets their own seat, given that the first passenger picks a seat randomly, and subsequent passengers take their own seat if available, otherwise picking a random available seat.

Approach: Mathematical Reasoning

Instead of simulating the process, a mathematical approach is significantly more efficient. Let's analyze the probabilities:

• Base Cases:

  • If n = 1, the probability is 1.0 (only one seat, one passenger).
  • If n = 2, the probability is 0.5. If passenger 1 takes seat 1, passenger 2 gets seat 2. If passenger 1 takes seat 2, passenger 2 gets seat 1.

• Recursive Reasoning (Incorrect but Illustrative): A naive attempt might involve recursion. Consider the seat the first passenger chooses:

  • Case 1: Passenger 1 chooses seat 1 (probability 1/n). Everyone else gets their assigned seat.
  • Case 2: Passenger 1 chooses seat n (probability 1/n). Passenger n doesn't get their seat.
  • Case 3: Passenger 1 chooses seat i (2 ≤ i ≤ n-1, probability (n-2)/n). This is where it gets tricky. We can't easily reduce this to a simpler subproblem with a direct recursive formula because the probability of the nth passenger getting their seat is dependent on the choices of passengers 2 through (i-1). A straightforward recursive approach would have high complexity.

• The Key Insight: The key is recognizing a pattern. For n≥2, the probability the nth passenger gets their seat is always 0.5. This isn't immediately obvious, but it holds true.

Algorithm

The algorithm is extremely simple based on the insight above:

1. If n is 1, return 1.0.
2. Otherwise, return 0.5.

Time and Space Complexity

• Time Complexity: O(1) - The solution is constant time; it involves a single conditional check.
• Space Complexity: O(1) - The solution uses constant extra space.

Code Implementation

The code implementations across various languages are nearly identical, reflecting the simplicity of the algorithm:

Python:

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

Java:

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

C++:

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

Go:

func nthPersonGetsNthSeat(n int) float64 {
	if n == 1 {
		return 1
	}
	return 0.5
}

TypeScript:

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

Rust:

impl Solution {
    pub fn nth_person_gets_nth_seat(n: i32) -> f64 {
        match n {
            1 => 1.0,
            _ => 0.5,
        }
    }
}

All these implementations achieve the same O(1) time and space complexity. The elegance of this solution lies in its mathematical insight, making it far superior to any simulation-based approach in terms of efficiency.