# use space - hashset
    #   - time: O(n)
    #   - space: O(1)
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = set()
        for num in nums:
            s.add(num)

        for v in range(0, len(nums) + 1):
            if v not in s:
                return v

    # XOR（异或）
    #  3 ^ 3 -> 0（相同元素会被抵消掉）
    #  3 ^ 0 -> 3（和0 XOR 会得到其本身）
    #  3 ^ 2 ^ 1 = 3 ^ 1 ^ 2（顺序不影响）
    # - time: O(n)
    # - space: O(1)
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = len(nums)
        for i in range(len(nums)):
            res = res ^ nums[i] ^ i
        return res
      
    # math - sum
    #  比如 n = 3, [0,1,2,3] 的和 减去 目标数组的和（比如 [1,2,3] 或者 [0,1,2]），就可以得到缺失的元素
    # - time: O(n)
    # - space: O(1)
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(len(nums)):
            res = res + i - nums[i]
        return res + len(nums)
      
     # Negative Marking - 解法太复杂了，就简单的办法 
    # - time: O(n)
    # - space: O(1)，把 input array 用作 memory space
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        n = len(nums)
        # Init memorised flags to be positive, i.e., we use positive to memorised a corresponding val existing
        for idx in range(n):
            if nums[idx] == 0:
                # Use u + 1 to replace 0, because
                #   1. 0 cannot record being positive or negative
                #   2. set it to be n + 1 doesn't affect the final result
                nums[idx] = n + 1

        # Memorise flags for each val
        for i in range(n):
            val = abs(nums[i])
            if val != n + 1:  # If the val is n + 1, we don't need to care
                idx = val - 1
                nums[idx] = -nums[idx]

        # Check whether a specified val exists or not by checking its corresponding memorised flag
        for idx in range(n):
            if nums[idx] > 0:
                val = idx + 1
                return val
        return 0  # If [1, n] all exist, meaning 0 doesn't exist        

    # greedy (myway and neetcode)
    # - time: O(n)
    # - space: O(1), 除了存储返回答案的空间以外，我们只需要额外的常数空间即可。
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """

        res = []
        for i, interval in enumerate(intervals):
            if newInterval[1] < interval[0]:  # no overlapping, and newInterval is on the left of the cur interval
                res.append(newInterval)
                res.extend(intervals[i:])
                return res  # 这时候不需要再 for loop 了，因为题目保证了 intervals 是排好序的
            elif 
            else:
                # has intersection, and not insert into res yet
                newInterval = [min(newInterval[0], interval[0]), max(newInterval[1], interval[1])]

        res.append(newInterval)  # edge case: intervals 中无元素
        return res

# approach 1 - myself
# - time: O(nlogn)
# - space: O(1)
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        # sort, or intervals.sort(key=lambda pair: pair[0])
        intervals.sort()  # time: O(logn)

        res = []
        newInterval = intervals[0]
        for i in range(1, len(intervals)):  # time: O(n)
            interval = intervals[i]
            if newInterval[1] < interval[0]:  # no overlapping, and newInterval is on the left side of interval
                res.append(newInterval)
                newInterval = interval
            else:
                newInterval = [min(newInterval[0], interval[0]), max(newInterval[1], interval[1])]

        res.append(newInterval)
        return res
      

# approach 2 - neetcode, quite similar
# - time: O(nlogn)
# - space: O(1)
	def merge(self, intervals: List[List[int]]) -> List[List[int]]:
		intervals.sort(key=lambda pair: pair[0])

		res = [intervals[0]]
		for i in range(1, len(intervals)):
			interval = intervals[i]

			lastEnd = res[-1][1]
			if interval[0] <= lastEnd:  # has overlap between the current interval and the previous added interval
				res[-1][1] = max(lastEnd, interval[1])  # merge "end"
			else:  # no overlap
				res.append(interval)
		return res

    # - 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     

    # - time: O(m*n)
    # - space: O(m*n) -> O(1) extra space, and O(m*n) space for the output list
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        # current valid search range: col: [minCol, maxCol], row: [minRow, maxRow]
        # this means that "while minRow <= maxRow and minCol <= maxCol"
        minRow, maxRow = 0, len(matrix) - 1
        minCol, maxCol = 0, len(matrix[0]) - 1

        res = []
        while minRow <= maxRow and minCol <= maxCol:
            # get every element in the top row
            for c in range(minCol, maxCol + 1):
                res.append(matrix[minRow][c])
            minRow += 1  # to exclude the min row

            # get every element in the right col
            for r in range(minRow, maxRow + 1):
                res.append(matrix[r][maxCol])
            maxCol -= 1

            # [[1,2,3]] or [[1], [2], [3]]
            # minCol > maxCol 说明没有任何 col 可以再被考虑了
            # minRow > maxRow 说明没有任何 row 可以再被考虑了
            # 所以如果满足任何条件，直接跳出
            if minCol > maxCol or minRow > maxRow:
                break

            # get every element in the bottom row
            for c in range(maxCol, minCol - 1, -1):
                res.append(matrix[maxRow][c])
            maxRow -= 1

            # get every element in the left col
            for r in range(maxRow, minRow - 1, -1):
                res.append(matrix[r][minCol])
            minCol += 1

        return res