Solution with discussion https://discuss.leetcode.com/topic/76042/python-solution-with-detailed-explanation
First Missing Positive https://leetcode.com/problems/first-missing-positive/
Solution using extra space: O(N) time and space
- If the length of the nums array is N, then the first missing positive will be between 1 to N+1. Think Why N+1? We can have in the array 1 to N.
- Take an temp array of size N and for any number x in nums such that 1<=x<=N, mark temp[x-1]. Then simply walk the temp array and report the first unmarked index.
class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ temp, N = [None]*len(nums), len(nums) for x in nums: if 1<=x<=N: temp[x-1] = x for i in range(N): if temp[i] == None: return i+1 return N+1
Optimized solution with O(1) Space
- Simply traverse the nums array and put any number within [1, N] in their right place. For example if 2 is in that input, then put 2 at index 1.
- Now traverse this "shuffled" array again. You expect 1 at 0th index. Otherwise it is missing. Then you expect 2 at 1st index and so on.
- Above idea can be a little tricky. What about cases like  and [1,1] - i.e. 1 is in its place or there are duplicates - we need to advance pointer regardless.
class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ N, i = len(nums), 0 while i < N: while 1<=nums[i]<=N: idx_expected = nums[i]-1 if nums[i] == nums[idx_expected]: break nums[i], nums[idx_expected] = nums[idx_expected], nums[i] i = i + 1 for i in range(N): if nums[i] != i+1: return i+1 return N+1 ```.