Find Smallest Missing Positive Integer in O(n) Time
Company: Apple
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
LeetCode-style algorithm phone interview
##### Question
Implement a function that returns the smallest missing positive integer in an unsorted integer array in O(n) time and O(
1) space, then explain the complexity trade-offs.
##### Hints
Use index placement/cyclic sort to achieve constant extra space.
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.
Given an unsorted list of integers, return the smallest positive integer that does not appear in the list. Your algorithm must run in O(n) time and use O(1) extra space. You may modify the input list in place.
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.
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.