Python O(1) space, O(n) time solution with explanation


  • 15
    A
     def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
         Basic idea:
        1. for any array whose length is l, the first missing positive must be in range [1,...,l+1], 
            so we only have to care about those elements in this range and remove the rest.
        2. we can use the array index as the hash to restore the frequency of each number within 
             the range [1,...,l+1] 
        """
        nums.append(0)
        n = len(nums)
        for i in range(len(nums)): #delete those useless elements
            if nums[i]<0 or nums[i]>=n:
                nums[i]=0
        for i in range(len(nums)): #use the index as the hash to record the frequency of each number
            nums[nums[i]%n]+=n
        for i in range(1,len(nums)):
            if nums[i]/n==0:
                return i
        return n

  • 0

    I dont really understand why you can determine which one is missed by:

    if nums[i]/n==0:
        return i
    

  • 1
    A

    after removing all the numbers greater than or equal to n, all the numbers remaining are smaller than n. If any number i appears, we add n to nums[i] which makes nums[i]>=n. Therefore, if nums[i]<n, it means i never appears in the array and we should return i.


  • 0

    It is super neat! Thank you!


  • 0
    X

    spectacular idea


  • 0
    M

    @JayWong Simpler would be to just check nums[i] == 0.
    The division is unnecessary.


  • 0
    W

    Great idea. Since Java doesn't have append, I just use a variable instead. A little bit dumb though.

    class Solution {
        public int firstMissingPositive(int[] nums) {
            if (nums == null || nums.length == 0) {
                return 1;
            }
            int len = nums.length + 1;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < 0 || nums[i] >= len) {
                    nums[i] = 0;
                }
            }
            int s = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] % len == nums.length) {
                    s += len;
                } else {
                    nums[nums[i] % len] += len;    
                }
                
            }
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < len) {
                    return i;
                }
            }
            if (s < len) {
                return len - 1;
            }
            return len;
        }
    }
    

  • 0

    @mmmasale

    Thats not true, there are cases when nums[i] < n but not necessarily 0


Log in to reply
 

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