You get a list of integers nums in no particular order. It may hold negative numbers, zeros, repeats, and numbers much larger than its length. Find the smallest positive integer (1, 2, 3, ...) that nums does not contain, and return it.

The limits are the hard part. Your solution must take O(n) time and O(1) extra space, where n is len(nums): a few variables, but no set, dict, sorted copy or second list. You may change nums in place, by moving its items or overwriting them. The tests time your code but cannot measure its memory, so the space rule is yours to keep, as it is in the interview.