42. Empty Seats Report
A small theatre has n seats numbered 1 to n. At the door, a scanner logs the seat number printed on every ticket it reads, but it sometimes reads the same ticket twice. You are given the log as seats, which has length n; every value is a seat number from 1 to n.
Return, in increasing order, every seat number that never appears in the log. If every seat appears at least once, return an empty list.
Aim for one pass over the log with no extra array or set: you may reuse the log itself as scratch space and mark seats you have seen.
Example 1
- Input:
- seats = [3,1,3,3]
- Output:
- [2,4]
- Explanation:
Seats 2 and 4 never show up in the log, so the answer is [2, 4].
Example 2
- Input:
- seats = [2,2]
- Output:
- [1]
- Explanation:
Seat 1 is missing; seat 2 appears twice. The answer is [1].
Example 3
- Input:
- seats = [1,2,3]
- Output:
- []
- Explanation:
Every seat from 1 to 3 appears, so the answer is empty.
Constraints
1 ≤ n ≤ 105
1 ≤ seats[i] ≤ n
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1) extra