# First Missing Positive Leetcode Solution

## First Missing Positive Leetcode Problem :

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 O(1) auxiliary space.

## Wildcard Matching Leetcode Problem Solution :

### Constraints :

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 – 1

### Example 1:

Input: [3,4,-1,1]

Output: 2

Explanation: 1 is in the array but 2 is missing.

### Example 2:

Input: [7,8,9,11,12]

Output: 1

Explanation: The smallest positive integer 1 is missing.

### Approach:

• Since they’ve asked us to find out the smallest positive integer, then there’s no point of having the negative numbers in array.
• All the negative numbers in the array is replaced by 0.
• Check if the number one(1) is present in array or not. If not then you’ve got the answer :-))), just return 1.
• Otherwise sort the array and find out for that first element whose difference is greater than 1. If found, then store the result in a variable and break the loop.
• If the value of the variable is same even before and after the iteration, then return (last element + 1).

### Complexity:

Time complexity :

• The first loop iterates through the nums vector to set negative values to zero. This loop has a time complexity of O(n), where n is the size of the nums vector.
• The second loop counts the number of ones in the nums vector. This loop also has a time complexity of O(n).
• Sorting the nums vector using sort takes O(n * log(n)) time complexity.
• The third loop iterates through the sorted nums vector to find the first missing positive integer. This loop has a time complexity of O(n).

Space complexity:

• The code uses a few integer variables like n, ones, and ele, which have constant space complexity, O(1).
• The input vector nums is modified in place, so no additional space is used for it.

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription