Python solution with detailed explanation


  • 0
    G

    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 [1] 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
    ```.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.