442. Find All Duplicates in an Array

Approach 1: Brute force array lookup

For each number in the array we can lookup the seen part of the array to see if the number exists in them, and if so add them to the answer array

def findDuplicates(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    ans = []
    for i in range(len(nums)):
        if nums[i] in nums[:i]:
            ans.append(nums[i])
    return ans

As expected this solution exceeds the time limit at test case 23/28 because of the time complexity since the "in" keyword is O(n) average case

Time Complexity: O(n²)

Space Complexity: O(n) [worst case]

Approach 2: Set/Hash Lookup

For each number in the array we add the values to a set (which hashes them and stores them in a lookup table with an average O(1) runtime for "in" ) and if the values are in the set then we add them to the answer array

def findDuplicates(self, nums): 
    """
    :type nums: List[int]
    :rtype: List[int]
    """   
    ans = []    
    seen = set()
    for i in range(len(nums)):        
        if nums[i] in seen:
            ans.append(nums[i])
        else:
            seen.add(nums[i])
    return ans

This solution doesn't behave the best way since the set lookup isn't the fastest and we haven't use the fact that all the numbers are within the range of 0 to n

Time Complexity: O(n) [Average case, worst case: O(n^2)]

Space Complexity: O(n) [worst case]

Approach 3: List Lookup

For each number in the array we add the values to a list and if the values are already seen in the list then we add them to the answer array

def findDuplicates(self, nums): 
    """
    :type nums: List[int]
    :rtype: List[int]
    """   
    ans = []    
    seen = [0]*(len(nums)+1)
    for i in nums:        
        if seen[i]==1:
            ans.append(i)
        else:
            seen[i]=1
    return ans

This solution has the most optimal runtime and is at 100% of the performance chart.

Time Complexity: O(n)

Space Complexity: O(n) [worst case]