Airplane Seat Assignment Probability - Practice Coding Problems

Airplane Seat Assignment Probability - Problem

There are n passengers boarding an airplane with exactly n seats. The first passenger has lost their ticket and picks a seat randomly. After that, the rest of the passengers will:

Take their own seat if it is still available
Pick other seats randomly when they find their seat occupied

Return the probability that the nth person gets their own seat.

Input & Output

Example 1 — Single Passenger

$ Input: n = 1

› Output: 1.0

💡 Note: With only one passenger, they must sit in their own seat, so probability is 1.0

Example 2 — Two Passengers

$ Input: n = 2

› Output: 0.5

💡 Note: First passenger chooses between 2 seats randomly. 50% chance they pick their own seat (passenger 2 wins), 50% chance they pick passenger 2's seat (passenger 2 loses)

Example 3 — Multiple Passengers

$ Input: n = 3

› Output: 0.5

💡 Note: Mathematical proof shows that regardless of n > 1, the probability is always 0.5. Only the first and last seats matter in determining the outcome

Constraints

1 ≤ n ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

n passengers and n seats on airplane

Boarding Process

First passenger sits randomly, others follow rules

Output

Probability that last passenger gets correct seat

Key Takeaway

🎯 Key Insight: Only the first and last seats determine the outcome - middle passengers are irrelevant to the final probability

Asked in

G Google 15 M Microsoft 12 a Amazon 8 f Facebook 6

The key insight is recognizing that only the first and last seats matter in determining the outcome. All middle passengers either sit correctly or pass the random choice problem to the next passenger. The probability is always 0.5 for n > 1 and 1.0 for n = 1. Best approach is the mathematical solution with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive with Memoization	O(n²)	O(n)	Use recursion with caching to avoid recalculating probabilities
Simulation Approach	O(2ⁿ)	O(n)	Simulate all possible seating scenarios and calculate probability
Mathematical Insight	O(1)	O(1)	Recognize that the answer is always 0.5 for n > 1

Recursive with Memoization — Algorithm Steps

Define recursive function for probability calculation
Use memoization to cache intermediate results
Handle base cases: n=1 returns 1.0

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate State

Compute probability for current seating state

Cache Result

Store result in memo table

Reuse Cache

Look up cached results for repeated states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_MEMO 1000

typedef struct {
    int remainingSeats;
    int firstSeatTaken;
    int lastSeatTaken;
    double prob;
} MemoEntry;

MemoEntry memo[MAX_MEMO];
int memoCount = 0;

double findMemo(int remainingSeats, int firstSeatTaken, int lastSeatTaken) {
    for (int i = 0; i < memoCount; i++) {
        if (memo[i].remainingSeats == remainingSeats && 
            memo[i].firstSeatTaken == firstSeatTaken &&
            memo[i].lastSeatTaken == lastSeatTaken) {
            return memo[i].prob;
        }
    }
    return -1.0;
}

void addMemo(int remainingSeats, int firstSeatTaken, int lastSeatTaken, double prob) {
    if (memoCount < MAX_MEMO) {
        memo[memoCount].remainingSeats = remainingSeats;
        memo[memoCount].firstSeatTaken = firstSeatTaken;
        memo[memoCount].lastSeatTaken = lastSeatTaken;
        memo[memoCount].prob = prob;
        memoCount++;
    }
}

double probability(int remainingSeats, int firstSeatTaken, int lastSeatTaken) {
    if (remainingSeats == 1) {
        return firstSeatTaken ? 0.0 : 1.0;
    }
    
    double cached = findMemo(remainingSeats, firstSeatTaken, lastSeatTaken);
    if (cached >= 0.0) {
        return cached;
    }
    
    int available = remainingSeats;
    if (firstSeatTaken) available--;
    if (lastSeatTaken) available--;
    
    if (available == 0) {
        addMemo(remainingSeats, firstSeatTaken, lastSeatTaken, 0.0);
        return 0.0;
    }
    
    double prob = 0.0;
    if (!firstSeatTaken) {
        prob += (1.0 / available) * 0.0;
    }
    if (!lastSeatTaken) {
        prob += (1.0 / available) * 1.0;
    }
    
    int middleSeats = available;
    if (!firstSeatTaken) middleSeats--;
    if (!lastSeatTaken) middleSeats--;
    
    if (middleSeats > 0) {
        prob += ((double)middleSeats / available) * probability(remainingSeats - 1, firstSeatTaken, lastSeatTaken);
    }
    
    addMemo(remainingSeats, firstSeatTaken, lastSeatTaken, prob);
    return prob;
}

double solution(int n) {
    if (n == 1) return 1.0;
    memoCount = 0;
    return probability(n, 0, 0);
}

int main() {
    int n;
    scanf("%d", &n);
    double result = solution(n);
    printf("%f\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each state is calculated once and cached, with O(n) states and O(n) transitions

⚠ Quadratic Growth

Space Complexity

O(n)

Memoization cache and recursion stack both use O(n) space

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler