# Leetcode First Missing Positive problem solution

Mar 22, 2023

In the Leetcode First Missing Positive problem solution Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra 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

## Solution in C Programming

``````int firstMissingPositive(int* nums, int n)
{
//replace all negative numbers in the array with 0
for (int i = 0; i < n; i++) {
if (nums[i] < 0)
nums[i] = 0;
}

//Traverse the array and use each element as the index
for (int i = 0; i < n; i++) {
int idx = abs(nums[i]) - 1; //subtract 1 bcoz the array is 0-based
//the element is OOB
if (idx < 0 || idx >= n)
continue;
//mark the slot as visited by marking it as a negative number
if (nums[idx] > 0)
nums[idx] *= -1;
//if the visited slot contains 0, we can mark it as visited by assigning it a -ve value OOB
if (nums[idx] == 0)
nums[idx] = -1 * (n + 1);

}

for (int i = 1; i <= n; i++) {
//if the number at the slot is still positive or zero, means there are
//no elements in the array that maps to that index
if (nums[i - 1] >= 0)
return i;
}

// the first missing +ve number is +1 of the max no. in the array
return n + 1;
}``````

## Solution in C++ Programming

``````class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int count=1;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(count==nums[i])count++;
}
return count;
}
};
``````

## Solution in Java Programming

``````class Solution {
public int firstMissingPositive(int[] nums) {
return withNegativeMarking(nums);
}

public int withNegativeMarking(int[] nums) {
// check if 1 present
// replace negative numbers and numbers > nums.length with 1
// mark zero index as negative
// iterate through each index
// mark the ath index as negative using number a
// iterate through again and find the only nonnegative index
// if all negative, return nums.length + 1

boolean hasOne = false;
for(int i = 0; i < nums.length; i++) {
if(nums[i] == 1) {
hasOne = true;
break;
}
}

if(!hasOne) {
return 1;
}

for(int i = 0; i < nums.length; i++) {
if(nums[i] <= 0 || nums[i] > nums.length) {
nums[i] = 1;
}
}

int max = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++) {
int abs = Math.abs(nums[i]);
max = Math.max(abs, max);
if(abs < nums.length) {
nums[abs] = Math.abs(nums[abs]) * -1;
}
if(i == 0) {
nums[0] = abs * -1;
}
}

for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) {
return i;
}
}

return max + 1;
}
}``````

## Solution in Python Programming

``````class Solution:
def firstMissingPositive(self, nums):

count = {}
MAX = nums[0]
for i in nums:
if i not in count:
count[i] = 1
else:
count[i] += 1
if i > MAX:
MAX = i

MAX = abs(MAX)
for i in range(1, MAX+2):
if i not in count:
return i``````

## Solution in C# Programming

``````public class Solution {
public int FirstMissingPositive(int[] nums)
{
if(nums.Length == 0)
{
return 1;
}

if (nums.Max() < 1)
{
return 1;
}

int smallestPositive = nums.Where(n => n > 0).Min();
if (smallestPositive > 1)
{
return 1;
}
int totalPositiveValues = nums.Count(n => n >= 1);
bool[] positiveValues = new bool[totalPositiveValues];
int differenceFromMin;
for (int i = 0; i < nums.Length; i++)
{
differenceFromMin = nums[i] - smallestPositive;
if (nums[i] > 0 && differenceFromMin < totalPositiveValues)
{
positiveValues[differenceFromMin] = true;
}
}

for (int i = 0; i < positiveValues.Length; i++)
{
if (!positiveValues[i])
{

return i + smallestPositive;
}
}

return positiveValues.Length+smallestPositive;
}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.