Description

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3


Example 2:

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


Example 3:

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


Note:

Your algorithm should run in O(n) time and uses constant extra space.

Solutions

1. Hash Table?

# Time: O(n)
# Space: O(1)
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
i, n = 0, len(nums)
while i < n:
if nums[i] != i + 1 and nums[i] > 0 and nums[i] <= n and nums[i] != nums[nums[i]-1]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
else:
i += 1

for i in range(n):
if nums[i] != i + 1:
return i+1
return n + 1

# 165/165 cases passed (32 ms)
# Your runtime beats 79.23 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)


2. Max

# Time: O(n)
# Space: O(1)
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 1

large = max(nums)

if large < 0:
return 1

for i in range(1, large + 1):
if i not in nums:
return i
return large + 1
# 165/165 cases passed (36 ms)
# Your runtime beats 48.81 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)