A ticketing system hands out seat numbers 1, 2, 3, ... and keeps the numbers currently taken in an unsorted list (which may also contain junk: zeros, negatives, duplicates, huge values). When a new guest arrives, they get the smallest positive integer that is not in the list.
Write first_absent_positive(nums) -> int that returns that number.
first_absent_positive([3, 4, -1, 1]) # 2
first_absent_positive([1, 2, 0]) # 3
first_absent_positive([7, 8, 9, 11, 12]) # 1
first_absent_positive([2, 2, 1, 1]) # 3
Constraints:
1 <= len(nums) <= 2 * 10^5- Values are integers in
[-2^31, 2^31 - 1].
Requirements:
- O(n) time. Sorting is O(n log n), and checking
1, 2, 3, ...one at a time against the list is O(n²). - O(1) extra memory. You may rearrange or overwrite the values in
numsitself, but you must not allocate anything whose size grows withn: no set, dict, copy of the list,bytearray,sorted(...)ornums.sort()(which needs a temporary buffer). The Python tests measure your function's peak memory withtracemalloc.
Show hint
The answer is always between 1 and len(nums) + 1, so only values in that range matter. Can you use the list's own positions as the record of which of those values you've seen, for example by moving the value v into slot v - 1?