LC 0041 [H] First Missing Positive - ALawliet/algorithms GitHub Wiki

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        i, n = 0, len(nums)
        while i < n:
            j = nums[i] - 1
            if nums[i] > 0 and nums[i] <= n and nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
            else:
                i += 1
        
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
            
        return len(nums) + 1

holy sht this nums[nums[i]%n]+=n is brilliant. It stores information about nums[i] and still keep the information of nums[nums[i]]. Thanks for sharing this trick.

l = [1, 1, 1, 2, 2]
size = len(l)  # 5

for e in l:
    # 1 % 5 = 1
    # 2 % 5 = 2
    l[e % size] += size

print("Hashed", l)  # [1, 16, 11, 2, 2]

# Modified
unhashed = l.copy()
for i, e in enumerate(unhashed):
    unhashed[i] = e % size

print("Unhashed", unhashed)  # [1, 1, 1, 2, 2]

print("Frequency")
for i, e in enumerate(l):
    i_count = e//size
    print(f'{i}: {i_count}')

# 0: 0
# 1: 3
# 2: 2
# 3: 0
# 4: 0

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """
        :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) # edge case: 1 element e.g. [1]
        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 x in nums: #use the index as the hash to record the frequency of each number
            nums[x % n] += n
        for i in range(1,len(nums)):
            if nums[i] // n == 0:
                return i
        return n

def firstMissingPositive(self, nums: List[int]) -> int:
        """
        For nums with length n, the possible result is in the range of
        [1 : n + 1], we want to know the smallest integer in the range 
        of [1 : n] that is not in nums, if [1 : n] are all in nums,
        the result is n + 1
        
        So those numbers not in [1 : n] are not useful and we can just
        change them to be 0
        
        Then we go through nums, if nums[i] is in the range of 
        [1 : n], we use index (nums[i] - 1) to record that we have
        seen nums[i] by adding n + 1 to nums[nums[i] - 1]
        
        Finally we just need to find the first index i for which 
        nums[i] is less than n + 1 (which means we never met number
        i + 1 so we did not add n + 1 to nums[i])
        """
        n = len(nums)
        for i in range(n):
            if nums[i] < 1 or nums[i] > n:
                nums[i] = 0
                
        for i in range(n):
            if 1 <= nums[i] % (n + 1) <= n:
                ind = nums[i] % (n + 1) - 1
                nums[ind] += n + 1
          
        for i in range(n):
            if nums[i] <= n:
                return i + 1
        
        return n + 1