Find Smallest Missing Positive Integer in O(n) Time
Company: Apple
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's skill in array algorithms and in-place algorithm design, emphasizing understanding of time and space complexity and handling edge cases when identifying the smallest missing positive integer.
Constraints
- 0 <= len(nums) <= 100000
- -2147483648 <= nums[i] <= 2147483647
- The solution must run in O(n) time.
- The solution must use O(1) extra space, excluding the input array.
Examples
Input: ([1, 2, 0],)
Expected Output: 3
Explanation: The positive integers 1 and 2 are present, so the smallest missing positive integer is 3.
Input: ([3, 4, -1, 1],)
Expected Output: 2
Explanation: After ignoring non-positive values, 1 is present but 2 is missing.
Input: ([7, 8, 9, 11, 12],)
Expected Output: 1
Explanation: No value 1 appears in the array, so 1 is the smallest missing positive integer.
Input: ([],)
Expected Output: 1
Explanation: The empty array contains no positive integers, so the answer is 1.
Input: ([1, 1],)
Expected Output: 2
Explanation: Duplicate 1s should not cause an infinite swap loop. Since 1 is present and 2 is missing, the answer is 2.
Input: ([1, 2, 3, 4],)
Expected Output: 5
Explanation: All positive integers from 1 through 4 are present, so the smallest missing positive integer is 5.
Input: ([2],)
Expected Output: 1
Explanation: The only element is 2, so 1 is missing.
Hints
- Only values in the range 1 to n can affect the answer, where n is the length of the array.
- Try placing each valid number x at index x - 1 using swaps, similar to cyclic sort.