The first missing positive number should >= 1 and <=len(nums).
minvalue = 1 maxvalue = len(nums)
Using O(n) time and O(n) space, one could build an extra array containing booleans.
- Scan through the array to mark each number as exist or missing.
- Find the first missing positive number.
Based on this idea, then we need to improve the code so that it uses O(1) extra space.
A straight thinking is to use the array itself and modify the value in-place.
- If the nums[i] is in place (e. g. nums == 1), go to next;
- If the value is not in place, swap it so that it is in place;
- if the value is out of boundary (too small, too large) or duplicated, discard the value, and the first missing positive number should now between 1 and maxvalue -1
def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ i, end = 0, len(nums) while i < end: j = nums[i]-1 # nums[i] should go to jth index if i == j: # nums[i] is in place i += 1 # in case: # the value is smaller than 1; # the value is larger than largest possible # the value is duplicated elif nums[i] < 1 or nums[i] > end or nums[i] == nums[j]: end -= 1 # the largest possible -1 nums[i] = nums[end] # discard the value and get new one from the end else: # swap the value, so nums[j] is in place nums[i], nums[j] = nums[j], nums[i] return i+1 # return the missing value, not the index