Loading problem...
You are given an unsorted array of integers nums. Your task is to determine the smallest positive integer that does not appear in the array.
A positive integer is any integer strictly greater than zero (1, 2, 3, ...). Your solution must identify the first gap in the sequence of positive integers when compared against the values present in the input array.
Critical Requirement: Your algorithm must achieve O(n) time complexity and use only O(1) auxiliary space (constant extra memory beyond the input array itself). This means you cannot use additional data structures like hash sets, arrays, or maps that scale with input size. However, you may modify the input array in-place if needed.
This constraint makes the problem significantly more challenging than a straightforward hash set approach, as you must devise a clever in-place strategy to track which positive integers are present.
nums = [1,2,0]3The positive integers 1 and 2 are both present in the array. The next positive integer is 3, which is absent, making it the smallest missing positive.
nums = [3,4,-1,1]2The array contains 1, 3, and 4 as positive integers (ignoring -1 which is non-positive). The sequence of positive integers starts with 1 (present), but 2 is missing. Therefore, 2 is the smallest absent positive.
nums = [7,8,9,11,12]1None of the array elements are the smallest positive integer 1. Regardless of what larger positive integers are present, the answer is 1 since it is the first missing positive in the sequence.
Constraints