Leetcode 41 Solution
This article provides solution to leetcode question 41 (first-missing-positive)
Access this page by simply typing in "lcs 41" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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 + 1is the first missing positive number.
- If we cannot find anything like that,
len(nums) + 1is the result.
Time & Space Complexity
N is the size of the array,
- Time complexity:
- Space complexity:
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