nums is an unsorted array of integers. It may hold duplicates, zeros and negative numbers. Return the smallest positive integer that does not appear in it.
Aim for O(n) time and only O(1) extra space beyond the input array itself.
1 and 2 are present, but 3 is not.
Every number from 1 to 4 is there, so the first gap is just past the end.
1 itself is missing, so nothing larger matters.
Constraints
1 <= nums.length <= 10⁵-2³¹ <= nums[i] <= 2³¹ - 1In an array of length n, the answer is somewhere from 1 to n + 1, so only values between 1 and n matter. Everything else can be ignored.
3