First Missing Positive
Problem Description
Question
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]
0
1
1
2
2
0
Output:3
3
Explanation: The numbers in the range [1,2] are all in the array.
Example 2:
Input:nums=[3,4,-1,1]
0
3
1
4
2
-1
3
1
Output:2
2
Explanation: 1 is in the array but 2 is missing.
Example 3:
Input:nums=[7,8,9,11,12]
0
7
1
8
2
9
3
11
4
12
Output:1
1
Explanation: The smallest positive integer 1 is missing.
Constraints:
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 - 1
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
- We need to find the first missing positive integer from an unsorted array.
- Our basic approach involves checking starting from 1, then 2, and so on, whether each number is present in the array.
- We continue this process until we find a number that is not present, which will be our answer.
Steps:
- Start with the integer 1.
- For each integer, check if it exists in the array by iterating through the entire array.
- If the integer is found, increment to check the next integer.
- If an integer is not found, it is the first missing positive number.
Code:
Complexity Analysis
- Time Complexity: O(n^2) - We iterate through the array for each number starting from 1.
- Space Complexity: No additional space used.
2. HashSet Approach
Intuition:
- Rather than checking every number by iterating through the array, we can store all numbers in a HashSet for O(1) look-up time.
- Iterate through numbers starting from 1 and check if they are in the HashSet.
Steps:
- Insert all numbers into a HashSet.
- Start checking integers from 1 onwards.
- If any integer is not found in the HashSet, that's the first missing positive number.
Code:
Complexity Analysis
- Time Complexity: O(n) - Linear time to populate the set and checking numbers
- Space Complexity: O(n) - Space used for storing array elements in the HashSet.
3. Cyclic Sort Approach
Intuition:
- Place each number at its correct index (i.e., number 1 at index 0, number 2 at index 1, etc.). Numbers out of this range can be ignored.
- Finally, the first place where the number is not equal to the index + 1 is the missing number.
Steps:
- Iterate through the array and swap numbers to their correct positions if they are within the valid range (1 to n).
- After sorting, iterate again to find the first index where the number is not equal to
index + 1. - Return
index + 1as the result.
Code:
Complexity Analysis
- Time Complexity: O(n) - Each number is visited at most twice.
- Space Complexity: O(1) - In-place sorting without additional space.