Domain 2MediumMEDIUM

Airplane Seat Assignment Probability

For n=1 the probability is 1, otherwise for any number of passengers greater than one, symmetry dictates a constant probability of exactly 0.5 that the last passenger gets their seat.

Domain: medium•Updated: 2026-09-10
#Mathematical Analysis#None#O(1)#Constant Space

Problem Breakdown

We are given n passengers and exactly n seats on an airplane. The boarding process follows specific rules: Passenger 1 picks a random seat, while subsequent passengers take their assigned seat if available or pick randomly otherwise. We need to determine the probability that the last passenger (Passenger n) sits in Seat n.

  • Input: An integer n (1≤n≤1051 \le n \le 10^5).
  • Output: A float representing the probability between 0.00.0 and 1.01.0.
  • Constraints: The input is always positive integers, so we do not need to handle empty inputs or negative values.

Intuition

The core of this problem lies in tracking which seats are “contested” during the random selection process. Specifically, Seat 1 (assigned to Passenger 1) and Seat n (assigned to Passenger n) act as absorbing states for the displacement chain:

  • If any displaced passenger picks Seat 1, everyone else gets their correct seat subsequently, including Passenger n. Success is guaranteed.
  • If any displaced passenger picks Seat n before it’s filled by its owner, Passenger n loses their seat immediately. Failure occurs.
  • Picking any other Seat kk (1<k<n1 < k < n) simply passes the “random choice” responsibility to another passenger without resolving the fate of Passenger n.

Since all available seats are chosen uniformly at random when a displacement happens, and intermediate choices do not bias between Seat 1 and Seat n, these two specific seats have an equal probability of being selected first among the contested set. Thus, for any n>1n > 1, the probability converges to exactly 0.50.5.

Approach

  1. Base Case Handling: If there is only one passenger (n == 1), they must take Seat 1 by default since no other seats exist. The probability of getting their own seat is 1.0.
  2. General Logic: For any n>1n > 1, the mathematical symmetry argument proves that regardless of how many passengers are displaced, the outcome depends solely on whether Seat 1 or Seat n gets picked first by a random chooser (including Passenger 1). Since they are equally likely to be chosen in this symmetric process, we return 0.5.
  3. Implementation: We implement an O(1)O(1) check: if n == 1, return 1.0; otherwise, return 0.5.

Complexity Analysis

  • Time Complexity: O(1)O(1). The solution performs a constant number of operations (a single comparison and return), independent of the magnitude of n for computation purposes.
  • Space Complexity: O(1)O(1). We utilize no auxiliary data structures, recursion stacks, or memory proportional to input size beyond basic variables.

Solution

class Solution:
    def nthPersonGetsNthSeat(self, n: int) -> float:
        """
        Calculates the probability that the last passenger gets their own seat.
        
        Args:
            n (int): Number of passengers and seats.
            
        Returns:
            float: Probability value.
        """
        # Base case: If there is only 1 passenger, they must get Seat 1.
        if n == 1:
            return 1.0
        
        # For any n > 1, the probability converges to exactly 0.5 due to 
        # symmetry between Seat 1 and Seat n being chosen first in the random chain.
        return 0.5

# Example usage for verification (not part of class submission)
if __name__ == "__main__":
    print(Solution().nthPersonGetsNthSeat(1))   # Output: 1.0
    print(Solution().nthPersonGetsNthSeat(2))   # Output: 0.5

Edge Cases Handled

  • n = 1: Explicitly handled to return 1.0, matching Example 1 where the single passenger takes their only seat with certainty. This is a critical edge case as it differs from all other inputs (>1>1).
  • Large n (10510^5): The O(1)O(1) logic handles large inputs without overflow or timeout, as no iteration occurs based on input size.
  • Constraints: Inputs are guaranteed to be ≥1\ge 1, so division by zero or invalid index errors (like accessing seat -1) do not occur in the logical flow of this constant-time solution.