YouTube Video

[A1] - Brute Force

Time: O(n^2)

Space: O(1)

class Solution(object):
    def containsDuplicate(self, nums):
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]==nums[j]:
                    return True
        return False

Comment: Getting TLE in python.

[A2] - Sorting

Time: O(nlog(n))

Space: O(1)

class Solution(object):
    def containsDuplicate(self, nums):
        nums.sort()
        for i in range(0,len(nums)-1):
            if nums[i]==nums[i+1]:
                return True
        return False

Comment: We can do better by sacrificing some memory.

[A3] - Hash table

Time: O(n)

Space: O(n)

class Solution(object):
    def containsDuplicate(self, nums):
        hashmap = set()
        for n in nums:
            if n in hashmap:
                return True
            hashmap.add(n)
        return False

Comment:set() in python is implemented using hash table.