41.first-missing-positive

bucket sort, runtime 62.53 %

Solution 1: bucket sort

First for loop to sort the array, and the second for loop to find the missing value.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if len(nums) == 0: return 1
        # bucket sort
        # [3,4,-1,1]
        for i in range(len(nums)): 
            while nums[i] > 0 and nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
                temp = nums[nums[i] - 1] #  temp = -1
                nums[nums[i] - 1] = nums[i]   # nums[2] = 3
                nums[i] = temp # nums[0] = -1 
        # [1, -1, 3, 4]
for i, val in enumerate(nums):
            if i + 1 != val:
                return i + 1
        # if the case is [1, 2, 3, 4]
        # return len(nums) + 1
        return len(nums) + 1
#   ✔ 165/165 cases passed (40 ms)
#   ✔ Your runtime beats 62.53 % of python3 submissions
#   ✔ Your memory usage beats 5.26 % of python3 submissions (13.2 MB)