# Airplane Seat Assignment Probability
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/airplane-seat-assignment-probability)
Canonical: https://scaleengineer.com/dsa/problems/airplane-seat-assignment-probability
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Probability and Statistics](https://scaleengineer.com/dsa/patterns/probability-and-statistics)
**Companies:** [Microstrategy](https://scaleengineer.com/companies/microstrategy), [Toptal](https://scaleengineer.com/companies/toptal)
---
## Problem
`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
## Naive Dynamic Programming
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`.
**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.
**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 (`n` up to 10^5).
### Explanation
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) * 1` to the total probability.
- If they pick seat `n`, the `n`-th passenger cannot get their seat. This contributes `(1/n) * 0`.
- If they pick seat `k` (where `1 < k < n`), passengers `2` through `k-1` take their own seats. When passenger `k` arrives, their seat is taken. They must choose a random seat from the remaining ones. This scenario effectively resets the problem to a smaller version with `n-k+1` passengers, where passenger `k` is the new 'first' passenger. The probability that the last passenger gets their seat in this subproblem is `dp[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 from `i=2` to `n` and, for each `i`, re-calculating the sum from `j=2` to `i-1`.

```java
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];
}
```
### Algorithm
- Handle the base case `n = 1`, returning `1.0`.
- Create a `dp` array of size `n + 1` to store the probabilities `dp[i]` for the `i`-th person.
- Set `dp[1] = 1.0`.
- Iterate from `i = 2` to `n`:
  - Inside this loop, start another loop from `j = 2` to `i-1` to calculate the sum of previous probabilities `dp[j]`.
  - Calculate `dp[i]` using the formula: `dp[i] = (1.0 / i) * (1.0 + sum)`.
- Return `dp[n]`.

## Optimized Dynamic Programming
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)`.
**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.
**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 to `O(1)` since we only need the running sum.
### Explanation
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.

```java
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];
}
```
### Algorithm
- Handle the base case `n = 1`, returning `1.0`.
- Create a `dp` array of size `n + 1`.
- Initialize a running sum variable `sumOfPrevProbs = 0.0`.
- Iterate from `i = 2` to `n`:
  - Calculate `dp[i]` using the formula `dp[i] = (1.0 / i) * (1.0 + sumOfPrevProbs)`.
  - Update the running sum by adding the newly computed `dp[i]`: `sumOfPrevProbs += dp[i]`.
- Return `dp[n]`.

## Constant Time Mathematical Solution
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`.
**Time:** O(1) as it involves a single conditional check. · **Space:** O(1) as no extra space proportional to the input size is used.
**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.
### Explanation
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 `n` is taken by a displaced passenger, passenger `n` cannot get their seat.
For any displaced passenger making a random choice, the available seats include Seat 1 and Seat `n` (assuming neither has been taken). Since the choice is random, Seat 1 and Seat `n` have an equal probability of being chosen. Due to this symmetry, the two terminal outcomes are equally likely. Thus, the probability is `0.5`.

The case `n=1` is trivial: the first passenger takes the only seat, so the probability is 1.

```java
public double nthPersonGetsNthSeat(int n) {
    if (n == 1) {
        return 1.0;
    } else {
        return 0.5;
    }
}
```
### Algorithm
- Check if `n` is equal to 1.
- If `n == 1`, return `1.0`.
- Otherwise (if `n > 1`), return `0.5`.

# Solutions
### Java

```java
class Solution {
public
  double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 :.5; }
}

```

### CPP

```cpp
class Solution {
public:
  double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 : .5; }
};

```

### Python

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

```