# Solution For First Missing Positive

Problem Statement:
Given an unsorted integer array nums, return the smallest missing positive integer.

Example 1:
Input: nums = [1,2,0] Output: 3

Example 2:
Input: nums = [3,4,-1,1] Output: 2

Example 3:
Input: nums = [7,8,9,11,12] Output: 1

Approach:
The approach is to use the given array as a hash table to mark the presence of the elements from 1 to n. In the array, we ignore all the negative numbers, as they cannot be part of the answer, and any number greater than n can be replaced with n, as we are only interested in the first missing positive integer. We traverse the array, and for every number in the array, we mark its presence in the hash table, placed at nums[nums[i] – 1]. Finally, we traverse the hash table, and the first index i, that does not contain i+1, is the answer.

Algorithm:
1. Traverse the given array, and place all the positive numbers, less than or equal to the length of the array, in their correct position. For any number greater than the length of the array, replace it with n+1, as we are only interested in the first missing positive integer.
2. Now, traverse the array and mark the presence of the elements in the hash table, placed at nums[nums[i] – 1].
3. Finally, traverse the hash table, and the first index i, that does not contain i+1, is the answer.
4. If no element is missing, return n+1.

Dry Run:
Let’s dry run the first example [1,2,0], for better understanding of the algorithm.

1. We traverse the array, and place all the positive numbers, less than or equal to the length of the array, in their correct position. The array becomes [1,2,0].
2. Now, we traverse the array and mark the presence of the elements in the hash table, placed at nums[nums[i] – 1]. The hash table becomes [1,1,0].
3. Finally, we traverse the hash table, and the first index i, that does not contain i+1, is the answer. Here, the answer is 3.

Solution:

class Solution {
public:
int firstMissingPositive(vector& nums) {
int n = nums.size();
//Step 1
for(int i=0;i0 && nums[i]<=n){
int pos = nums[i]-1;
if(nums[pos]!=nums[i]){
swap(nums[pos],nums[i]);
i–;
}
}
}
//Step 2
for(int i=0;i<n;i++){
if(nums[i]!=i+1){
return i+1;
}
}
//Step 3
return n+1;
}
};

## Step by Step Implementation For First Missing Positive

```class Solution {
public int firstMissingPositive(int[] nums) {
// check for the corner cases of an empty or single element array
if (nums == null || nums.length == 0) {
return 1;
} else if (nums.length == 1) {
// if the single element array contains the number 1, then return 2
return (nums == 1) ? 2 : 1;
}

// sort the array in ascending order
Arrays.sort(nums);

// check if the first element is positive and greater than 1
if (nums <= 0 || nums > 1) {
return 1;
}

// iterate through the array
for (int i = 0; i < nums.length - 1; i++) {
// check if the current number is positive
if (nums[i] > 0) {
// check if the difference between the current number and the next number is greater than 1
if (nums[i+1] - nums[i] > 1) {
// return the first number that is missing
return nums[i] + 1;
}
}
}

// return the next positive number after the last element in the array
return nums[nums.length-1] + 1;
}
}```
```class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:

# Base case:
if not nums:
return 1

# Sort the list in ascending order
nums.sort()

# Edge case: If the first element is greater than 1,
# that means the list is not starting from 1
if nums > 1:
return 1

# Iterate through the list
for i in range(len(nums)):

# If the current element is not equal to the previous element + 1
# then that element is the first missing positive number
if nums[i] != nums[i-1] + 1:
return nums[i-1] + 1

# If we reach here, it means the list is starting from 1
# and is consecutive up till the last element
# Therefore, the first missing positive number is the last element + 1
return nums[-1] + 1```
```var firstMissingPositive = function(nums) {

// sort the array in ascending order
nums.sort((a, b) => a - b);

// if the first element is greater than 1, then 1 is the first missing positive
if (nums > 1) {
return 1;
}

// iterate through the array
for (let i = 0; i < nums.length; i++) {
// if the current element is positive
if (nums[i] > 0) {
// and the next element is greater than the current element + 1
// then the current element + 1 is the first missing positive
if (nums[i+1] > nums[i] + 1) {
return nums[i] + 1;
}
}
}

// if we reach here, that means the array consists of consecutive positive integers starting from 1
// therefore, the next integer after the last element in the array is the first missing positive
return nums[nums.length-1] + 1;

};```
```class Solution {
public:
int firstMissingPositive(vector& nums) {

// Base case
if (nums.size() == 0)
return 1;

// To mark the presence of elements
// we use the sign of the elements
// as the index.
// For example, if 'n' is present
// at index 5, then we represent it
// by making the value at index -5
// as negative.
for (int i = 0; i < nums.size(); i++) {
int x = abs(nums[i]);

// If the index 'x-1' is positive,
// then make it negative to indicate
// that 'x' is present in the array.
// But if the index 'x-1' is negative,
// then 'x' is already present.
if (x > 0 && x <= nums.size())
nums[x - 1] = -1 * abs(nums[x - 1]);
}

// If 1 is not present, then return 1
if (nums > 0)
return 1;

// Find the first index value which
// is positive
for (int i = 1; i < nums.size(); i++)
if (nums[i] > 0)
return i + 1;

// If all values are negative,
// then the smallest positive
// value is size+1
return nums.size() + 1;
}
};```
```public class Solution {
public int FirstMissingPositive(int[] nums) {
// Initialize an empty list
List list = new List();

// Loop through the input array
for(int i = 0; i < nums.Length; i++) {
// If the current element is positive, add it to the list
if(nums[i] > 0) {
}
}

// Sort the list in ascending order
list.Sort();

// Loop through the sorted list
for(int i = 0; i < list.Count; i++) {
// If the current element is not equal to its index + 1,
// then that is the first missing positive integer
if(list[i] != i + 1) {
return i + 1;
}
}

// If we reach here, that means the list is complete
// without any missing integers, so return the next integer
return list.Count + 1;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]