# Leetcode 41 Solution

https://leetcode.com/problems/first-missing-positive

## Thinking Process

Solving the problem with `O(N)` space is easy. If we are asked to use `O(1)`, the idea is basically to use the existing array to store information to infer if an element exists. One of the ways to do that is to place `i` onto the `(i - 1)`th position of the array.

Once we are done, we go through the array one more time

• If we find an element `nums[j] != j + 1`, `j + 1` is the first missing positive number.
• If we cannot find anything like that, `len(nums) + 1` is the result.

## Time & Space Complexity

Assuming `N` is the size of the array,

• Time complexity: `O(N)`
• Space complexity: `O(1)`

## Solution

``````class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
for i, num in enumerate(nums):
curr = num
while 1 <= curr <= len(nums) and nums[curr - 1] != curr:
tmp = nums[curr - 1]
nums[curr - 1] = curr
curr = tmp

for i, num in enumerate(nums):
if num != i + 1:
return i + 1

return len(nums) + 1
``````