Problem
Given an unsorted integer array, find the smallest missing positive integer. Run in O(n) time with O(1) extra space.
Example
Input: [3,4,-1,1]
Output: 2Solution
Use the array itself as a hash set. Place each value v at index v-1 if possible. Scan for first index where index+1 != value.
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
for i in range(n):
if nums[i] != i + 1: return i + 1
return n + 1function firstMissingPositive(nums) {
const n = nums.length;
for (let i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
const tmp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = tmp;
}
}
for (let i = 0; i < n; i++) if (nums[i] !== i + 1) return i + 1;
return n + 1;
}int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
}
}
for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;
return n + 1;
}public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int tmp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = tmp;
}
}
for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;
return n + 1;
}Complexity
- Time: O(n)
- Space: O(1)
Explanation
Cyclic sort places each value v at position v-1. After this, the first index where nums[i] != i+1 reveals the missing positive.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?