645. Set Mismatch

"""
tc O(N) sc O(N)
"""
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        seen = set()
        res = []
        for x in nums:
            if x in seen:
                res.append(x)
            else:
                seen.add(x)
        for i in range(1,n+1):
            if i not in seen:
                res.append(i)
        return res 

class Solution:
    def findErrorNums(self, A: List[int]) -> List[int]:
        """ note the arr is not necessarily sorted 
        main idea: use element value as idx to mark visited element so we can find duplicates;  then iterate index i from 0 -> n-1, get missing number which is not reversed 
        1. find duplicate number 
        2. find missing number 
        tc O(N)  sc O(1)
        """
        n = len(A)
        res = []
        # for each number, set A[x-1] to negtive 
        for i,x in enumerate(A):
            idx = abs(x)-1
            if A[idx] > 0: A[idx] *= -1 
            else: res.append(idx+1)
        
        # at this point, only missing number A[missingnumber -1] > 0 
        for i in range(n):
            if A[i]<0:  A[i] *= -1 # reverse back (optional)
            else: 
                res.append(i+1)
                return res