[Leetcode][python3] 442. Find All Duplicates in an Array

problem: https://leetcode.com/problems/find-all-duplicates-in-an-array/

 

code:

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        hashmap = dict()
        result = []
        for num in nums: # n times
            if num in hashmap : #O(1)
                result.append(num)
            else:
                hashmap[num]=True
        return result

        
# time complexity
# O(n)

# space complextiy
# O(n)

 

code:

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        isExist = [False]*(10**5)
        result = []
        for num in nums: # n times
            if isExist[num] : #O(1)
                result.append(num)
            else:
                isExist[num]=True
        return result

# time complexity
# O(n)

# space complextiy
# O(1) 
# O(10**5) # costant space

 

other's code -> genius :

nums list would be hash map itself

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        result = []
        for num in nums:
            if nums[abs(num)-1] <0 :
                result.append(abs(num))
            else :
                nums[abs(num)-1] *= -1
        return result