Given an unsorted integer array nums. Return the smallest positive integer that is not…
- User
Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.
You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Example 1:
Input: nums = [1,2,0] Output: 3 Explanation: The numbers in the range [1,2] are all in the array. Example 2:
Input: nums = [3,4,-1,1] Output: 2 Explanation: 1 is in the array but 2 is missing. Example 3:
Input: nums = [7,8,9,11,12] Output: 1 Explanation: The smallest positive integer 1 is missing.
Constraints:
1 <= nums.length <= 105 -231 <= nums[i] <= 231 - 1
Assistant
To solve this problem in O(n) time and O(1) auxiliary space (ignoring the input modification), we can use an in-place cyclic sort approach.
Key Idea:
We want to place each number
numin its correct index, i.e., number1at index0, number2at index1, etc. We then scan the array to find the first index where this condition is not satisfied — that index + 1 will be our answer.
Algorithm Steps:
- Iterate through the array.
- For each number
num = nums[i], if1 <= num <= len(nums)andnums[num - 1] != num, swap it to its correct position. - After placing all numbers correctly, iterate through the array again.
- The first index
isuch thatnums[i] != i + 1gives us the result:i + 1.
Python Code:
def firstMissingPositive(nums): n = len(nums) for i in range(n): # Place nums[i] in its correct position if possible while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: correct_index = nums[i] - 1 nums[i], nums[correct_index] = nums[correct_index], nums[i] # Find the first position where the number is incorrect for i in range(n): if nums[i] != i + 1: return i + 1 return n + 1
Example Walkthrough:
Input:
[3,4,-1,1]- Initial:
[3,4,-1,1] - After sorting:
[1, -1, 3, 4] - Check positions:
- index 0 → 1 ✅
- index 1 → -1 ❌ should be 2
- So, return
2
Time & Space Complexity:
- Time: O(n) — each element is moved at most once.
- Space: O(1) — in-place swaps, no extra data structures used.
Edge Cases:
[7,8,9,11,12]→ missing1[1,2,3]→ missing4[2,1]→ missing3[1]→ missing2[]→ missing1(but per constraints, length ≥ 1)
Let me know if you'd like a version with comments or step-by-step debug output!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.