'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
from collections import *


class Solution:
    # cyclic sort. T: O(N), S: O(1)
    def findDisappearedNumbers2(self, nums: List[int]) -> List[int]:
        i = 0
        while i < len(nums):
            idx = nums[i] - 1
            if nums[i] != nums[idx]:
                nums[i], nums[idx] = nums[idx], nums[i]
            else:
                i += 1
        res = []
        for i in range(len(nums)):
            if nums[i] != i+1:
                res.append(i+1)
        return res


    # T: O(N), S: O(1)
    def findDisappearedNumbers1(self, nums: List[int]) -> List[int]:
        # Iterate over each of the elements in the original array
        for i in range(len(nums)):
            
            # Treat the value as the new index
            new_index = abs(nums[i]) - 1
            
            # Check the magnitude of value at this new index
            # If the magnitude is positive, make it negative 
            # thus indicating that the number nums[i] has 
            # appeared or has been visited.
            if nums[new_index] > 0:
                nums[new_index] *= -1
        
        result = []    
        # Iterate over the numbers from 1 to N and add all those
        # that have positive magnitude in the array 
        for i in range(1, len(nums) + 1):
            if nums[i - 1] > 0:
                result.append(i)
        return result        
        
    
    # naive
    # O(N) for S and T
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        if not nums: return []
        tmp = list(range(1, len(nums)+1))
        # dict_ = set(nums) # or just use set
        dict_ = Counter(nums)
        res = []
        for val in tmp:
            if val not in dict_:
                res.append(val)
        return res
                
            