The Number of the Smallest Unoccupied Chair — Solution
The Number of the Smallest Unoccupied Chair solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
The Number of the Smallest Unoccupied Chair is a medium coding problem on arrays, hash table and heap, asked in Amazon, Google and CRED interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Heap, Ordered Set
- Asked at: Amazon, Google, CRED
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A party has infinitely many chairs numbered 0, 1, 2, …. times[i] = [arrival, leaving] gives when friend i arrives and leaves; all the arrival times are different.
On arrival a friend takes the smallest-numbered unoccupied chair. A chair freed at moment t may be taken by someone arriving at that same moment t. Return the chair number that friend targetFriend sits on.
Example 1
Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: Friend 0 takes chair 0, friend 1 takes chair 1.
Example 2
Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: Friends 1 and 2 arrive first and take chairs 0 and 1.
Example 3
Input: times = [[1,2],[2,3]], targetFriend = 1
Output: 0
Explanation: Chair 0 is freed exactly as the second friend arrives.
Constraints
n == times.length2 <= n <= 10^4times[i].length == 21 <= arrival < leaving <= 10^50 <= targetFriend <= n - 1Each arrival time is distinct.
Hints for The Number of the Smallest Unoccupied Chair
Hint 1
Process the friends in order of arrival, not in input order.
Hint 2
Before seating someone, free every chair whose occupant has already left —
leaving <= arrivalcounts as left.Hint 3
The chair taken is the smallest free number;
nchairs always suffice fornfriends.
How to solve The Number of the Smallest Unoccupied Chair
Simulate the party in arrival order. Before each arrival, release the chairs whose occupants have gone, then hand out the smallest free chair number.
Approach
- Sort the friend indices by arrival time.
- For each arrival, mark free any chair whose recorded leaving time is at most this arrival.
- Take the lowest-numbered free chair; if the arriving friend is the target, that is the answer.
- Otherwise record the chair as occupied until that friend's leaving time.
Why it works
Only n chairs are ever needed, because at most n friends are present at once — which is what lets the free chairs live in a fixed-size array. The boundary is the subtle part: a chair freed at exactly the arrival moment is available, so the release test is <= rather than <. Two heaps — free chair numbers and occupied-by-leaving-time — turn the scan into O(n log n).
Complexity
- Time —
O(n²) as written, or O(n log n) with two heaps - Space —
O(n)
Pitfalls
- Processing the friends in input order instead of arrival order.
- Using
<to release chairs loses the same-moment handover. - Chairs are reused, so the answer is not simply the friend's rank in arrival order.
Reference solution
Python
from typing import List
import heapq
def smallestChair(times: List[List[int]], targetFriend: int) -> int:
n = len(times)
order = sorted(range(n), key=lambda i: times[i][0])
free = list(range(n))
heapq.heapify(free)
busy = []
for who in order:
arrive, leave = times[who]
while busy and busy[0][0] <= arrive:
_, chair = heapq.heappop(busy)
heapq.heappush(free, chair)
chair = heapq.heappop(free)
if who == targetFriend:
return chair
heapq.heappush(busy, (leave, chair))
return -1Java
public static int smallestChair(int[][] times, int targetFriend) {
int n = times.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> times[a][0] - times[b][0]);
PriorityQueue<Integer> free = new PriorityQueue<>();
for (int i = 0; i < n; i++) free.add(i);
PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int who : order) {
int arrive = times[who][0], leave = times[who][1];
while (!busy.isEmpty() && busy.peek()[0] <= arrive) free.add(busy.poll()[1]);
int chair = free.poll();
if (who == targetFriend) return chair;
busy.add(new int[] { leave, chair });
}
return -1;
}C++
int smallestChair(vector<vector<int>>& times, int targetFriend) {
int n = (int) times.size();
vector<int> order(n);
for (int i = 0; i < n; i++) order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) { return times[a][0] < times[b][0]; });
priority_queue<int, vector<int>, greater<int>> freeChairs;
for (int i = 0; i < n; i++) freeChairs.push(i);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> busy;
for (int who : order) {
int arrive = times[who][0], leave = times[who][1];
while (!busy.empty() && busy.top().first <= arrive) {
freeChairs.push(busy.top().second);
busy.pop();
}
int chair = freeChairs.top();
freeChairs.pop();
if (who == targetFriend) return chair;
busy.push({ leave, chair });
}
return -1;
}JavaScript
var smallestChair = function(times, targetFriend) {
var n = times.length, i;
var order = [];
for (i = 0; i < n; i++) order.push(i);
order.sort(function(a, b) { return times[a][0] - times[b][0]; });
var freeAt = [], inUse = [];
for (i = 0; i < n; i++) { freeAt.push(0); inUse.push(false); }
for (var k = 0; k < order.length; k++) {
var who = order[k];
var arrive = times[who][0];
for (var c = 0; c < n; c++) {
if (inUse[c] && freeAt[c] <= arrive) inUse[c] = false;
}
var chair = 0;
while (inUse[chair]) chair++;
if (who === targetFriend) return chair;
inUse[chair] = true;
freeAt[chair] = times[who][1];
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets