Skip to main content
Talentd

The Number of the Smallest Unoccupied Chair - Solution & Explanation

MediumArrayHash TableHeap (Priority Queue)16 min readAsked at: Amazon, Microsoft, Spinny +2
Practice this problem

Problem Statement

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

  • For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

 

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

 

Constraints:

  • n == times.length
  • 2 <= n <= 104
  • times[i].length == 2
  • 1 <= arrivali < leavingi <= 105
  • 0 <= targetFriend <= n - 1
  • Each arrivali time is distinct.

Approach Overview

Problem Overview: Friends arrive and leave at different times, and each one takes the smallest numbered unoccupied chair when they arrive. When a friend leaves, their chair becomes available again. Given the arrival/leave schedule and a target friend index, you need to determine which chair that friend sits on.

Approach 1: Min-Heap Simulation (O(n log n) time, O(n) space)

This approach models the process exactly as it happens using two heap (priority queue) structures. First, sort all friends by arrival time so events happen in chronological order. Maintain one min-heap for currently occupied chairs keyed by leaving time, and another min-heap that stores available chair numbers. When a friend arrives, repeatedly pop from the occupied heap if their leave time is less than or equal to the current arrival time, pushing those chair numbers back into the free heap. The arriving friend takes the smallest available chair from the free heap. If the arriving friend is the target friend, return that chair number immediately.

The key insight: you never need to simulate all chairs explicitly. The free heap always provides the smallest available chair in O(log n), while the occupied heap quickly releases chairs when friends leave. This solution fits naturally with array processing and event simulation.

Approach 2: Event Scheduling with Ordered Sets (O(n log n) time, O(n) space)

This approach treats arrivals and departures as ordered events and uses a balanced set structure to manage available chairs. Sort friends by arrival time. Maintain a set containing all currently free chair numbers and a structure mapping leave times to the chair occupied by that friend. As you iterate through arrivals, release chairs for all friends whose leave time has passed and reinsert those chair numbers into the set. The arriving friend always picks the smallest element from the set.

The ordered set guarantees that retrieving the smallest free chair takes O(log n). Tracking departures ensures chairs are recycled efficiently. This method often appears in C++ or Java implementations where ordered sets or tree structures are convenient. The scheduling idea closely resembles problems involving hash table lookups combined with sorted events.

Recommended for interviews: The min-heap simulation is the expected solution. It demonstrates understanding of event ordering, priority queues, and resource allocation problems. Explaining the simulation clearly shows strong problem modeling skills, while the heap operations keep the runtime optimal at O(n log n).

Approach 1: Min-Heap Approach

The problem can be efficiently solved by using a min-heap (priority queue) to keep track of the smallest available chair. When a friend arrives, we assign them the smallest chair, and when they leave, their chair is added back to the pool of available chairs. This ensures that friends always get the smallest possible available chair.

We start by sorting all events by time. As we process each event, we use the heap to efficiently manage the available chairs.

This Python function uses two main structures: a list of events that are sorted by time, and a min-heap to keep track of the smallest available chairs. We iterate through each event, either assigning an available chair to an arriving friend or freeing up a chair when a friend leaves. This method works because the heap operations are logarithmic, keeping the solution efficient.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n log n), where n is the number of friends (and thus events). This is due to sorting the events and using heap operations.
Space Complexity: O(n) for storing event data and the heap.

Try this approach in the editor →

Approach 2: Event Scheduling with Sets

This approach involves handling chair availability using a sorted list (or equivalent structure) to manage the sequence of chairs efficiently. We simulate arrival and departure events by updating the list and assigning chairs accordingly. While slightly less efficient than a heap in handling dynamic minimum queries, it offers an alternative perspective by focusing on set management operations.

This C++ solution uses a sorted set (implemented typically with Red-Black Trees in the STL set) to track available chairs and assigns them to arriving friends. When a friend arrives, we select the smallest available chair, either from the set or by incrementing. When a friend leaves, we return the chair to the set.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n log n) primarily due to sorting events and set operations.
Space Complexity: O(n) for storing chair assignments and event data.

Try this approach in the editor →

Approach 3: Priority Queue (Min-Heap)

First, we create a tuple for each friend consisting of their arrival time, leaving time, and index, then sort these tuples by arrival time.

We use a min-heap idle to store the currently available chair numbers. Initially, we add 0, 1, ldots, n-1 to idle. We also use a min-heap busy to store tuples (leaving, chair), where leaving represents the leaving time and chair represents the chair number.

We iterate through each friend's arrival time, leaving time, and index. For each friend, we first remove all friends from busy whose leaving time is less than or equal to the current friend's arrival time, and add their chair numbers back to idle. Then we pop a chair number from idle, assign it to the current friend, and add (leaving, chair) to busy. If the current friend's index is equal to targetFriend, we return the assigned chair number.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of friends.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Min-Heap Approach

Time Complexity: O(n log n), where n is the number of friends (and thus events). This is due to sorting the events and using heap operations.
Space Complexity: O(n) for storing event data and the heap.

Event Scheduling with Sets

Time Complexity: O(n log n) primarily due to sorting events and set operations.
Space Complexity: O(n) for storing chair assignments and event data.

Priority Queue (Min-Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap SimulationO(n log n)O(n)General case; ideal when modeling arrivals and departures with priority queues
Event Scheduling with Ordered SetsO(n log n)O(n)Useful when language libraries provide efficient ordered sets or trees

Video Solution

The Number of the Smallest Unoccupied Chair - Leetcode 1942 - Python • NeetCodeIO • 12,920 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is The Number of the Smallest Unoccupied Chair easy or hard?
The problem is classified as Medium difficulty. The logic is straightforward once you recognize it as an event simulation problem, but managing two priority queues and correctly releasing chairs based on leave times requires careful implementation.
The Number of the Smallest Unoccupied Chair Python/Java solution
Python solutions typically use the heapq module to manage available chairs and active departures. Java implementations often rely on PriorityQueue with custom pairs storing leave time and chair number. Both follow the same event simulation strategy with O(n log n) complexity.
How to solve The Number of the Smallest Unoccupied Chair in O(n)?
An exact O(n) solution is generally not feasible because arrivals must be processed in sorted order and chair assignments require ordered retrieval. Sorting alone costs O(n log n). The practical optimal approach therefore uses heaps or ordered sets and runs in O(n log n) time.
What is the best approach for The Number of the Smallest Unoccupied Chair?
The most common solution uses a min-heap simulation. Friends are processed in order of arrival time, a heap tracks currently occupied chairs by leave time, and another heap stores available chair numbers. Each arrival releases chairs whose owners have left, then assigns the smallest available chair. This approach runs in O(n log n) time and O(n) space.
Is The Number of the Smallest Unoccupied Chair asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving event simulation and priority queues. Variants of the problem appear in interviews at companies like Google, Amazon, and Meta when testing heap usage, scheduling logic, and resource allocation algorithms.
What data structure is used in The Number of the Smallest Unoccupied Chair?
The core data structure is a min-heap (priority queue). One heap tracks the smallest available chair number, while another heap tracks occupied chairs ordered by leaving time. Some implementations also use ordered sets or maps to manage chair availability.
What is the time complexity of The Number of the Smallest Unoccupied Chair?
The optimal solution runs in O(n log n) time. Sorting friends by arrival takes O(n log n), and each heap operation for assigning or freeing a chair costs O(log n). Since each friend is inserted and removed from the heaps at most once, the total complexity remains O(n log n) with O(n) space.

Ready to solve this problem?

Practice The Number of the Smallest Unoccupied Chair with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays