41. First Missing Positive
Given an unsorted integer array
nums, find the smallest missing positive integer.
Input: nums = [1,2,0]
Input: nums = [3,4,-1,1]
Input: nums = [7,8,9,11,12]
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.
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:
The time complexity is O(N) where N is the number of elements in our list.
The space complexity is O(N) where N is the number of elements in our list.