First Missing Positive — Day 94(Python)

Today’s question is a Hard-tagged question on Leetcode. This question is quite frequently asked in technical interviews. Let us look into the problem statement.

41. First Missing Positive

Given an unsorted integer array nums, find 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


  • 0 <= nums.length <= 300
  • -231 <= nums[i] <= 231 - 1

Follow up: Could you implement an algorithm that runs in O(n) time and uses constant extra space?

This problem is a bit tricky to solve. We have an unsorted array of some numbers. We need to find the first missing positive number.

Positive numbers start from 1 and go until infinity.

One point to keep in mind, we can get repeated numbers too. So if we are thinking of sorting the number and then look for missing numbers please ensure that you take care either to remove repeated numbers or ignore them while traversing through the list.

We will be converting our given list to a set. By converting the input array to set, we are eliminating the repeated number. After eliminating the repeated numbers, we will then run a loop that starts from 1 and runs until the maximum integer value. Each time we will check if this number in the loop is present in our set. If not, that will be the missing number.

Let us look into the code snippet.

class MissingNumberFinder:
def firstMissingPositive(self, nums: List[int]) -> int:
num_set = set(nums)
for i in range(1,pow(2,31) - 1):
if i not in num_set:
return i

Complexity analysis.

Time Complexity

The time complexity is O(N) where N is the number of elements in our list.

Space Complexity

The space complexity is O(N) where N is the number of elements in our list.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store