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.


  • 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).


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.

Prime Course Trailer

Related Banners

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

Code :