# - time: O(n)
    # - space: O(n)
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = set()
        for num in nums:
            if num > 0:
                s.add(num)

        for n in range(1, len(nums) + 2):  # e.g., [1, 2]
            if n not in s:
                return n
              
    # Boolean Array 
    # 用一个 boolean array 记录下 [1, len(nums)] 的范围中每个值是否出现
    # - time: O(n)
    # - space: O(n)
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = [False] * len(nums)
        for i in range(len(nums)):
            val = nums[i]
            if 1 <= val <= len(nums):  # 在 [1, len(nums)] 的范围才去记录
                idx = val - 1
                s[idx] = True

        for val in range(1, len(nums) + 1):
            idx = val - 1
            if not s[idx]:
                return val
        return len(nums) + 1  # e.g., [1, 2], s 为 [True, True]，结果为 3    
      
    # Negative Marking
    # - time: O(n)
    # - space: O(1)，把 input array 用作 memory space
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # Reset the memorised flag to be not-positive, by setting all negative values to be 0, because
        #   all negative values don't affect the final result
        #   also set all flags to be the default value (not-positive), as we use "negative" to record a specified value existing)
        n = len(nums)
        for idx in range(n):
            if nums[idx] < 0:
                nums[idx] = 0

        # Set "negative" flag for the existence of all vals ([1, n])
        for i in range(n):
            val = abs(nums[i])
            if 1 <= val <= n:
                idx = val - 1
                # Check the memorised flag
                #  - if already negative, doesn't need to set/memorise again, e.g., [1,1,2]
                if nums[idx] > 0:
                    nums[idx] = -nums[idx]  # Write down the memorised flag for val
                elif nums[idx] == 0:
                    # Because if the flag position is 0, we couldn't be positive or negative
                    # So we set it to be negative and (n+1), since we only care about val [1, n],
                    # and thus being n+1 doesn't affect the final result
                    nums[idx] = -(n + 1)

        for idx in range(n):
            # If not flag exists, it means that the corresponding val doesn't exist
            if nums[idx] >= 0:
                val = idx + 1
                return val
        return n + 1