0217. Contains duplicate

Problem category:: Array, Hash table Neetcode Category:: Arrays and Hashing

https://leetcode.com/problems/contains-duplicate/

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Optimal

Dictionary (hash table)

Use a hash table based data structure, such as Dictionary, as we can check in average $O(1)$ time whether an entry already exists (we do this up to n times over the entries)

• $O(n)$ time (average), $O(n)$ space

Python dictionary implementation

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        dictionary = {} # Dict uses hash table
        # Use the numbers as keys, let their values be 1 when added
            # This allows us to use 1/0 as bool checks
        for number in nums:
            if dictionary.get(number, 0): # 2nd arg is return value if key not found
            # True (1) when number is already a key
                return True
            else: # Number not yet a key
                dictionary[number] = 1 # Set
        # Finished iteration
        return False

Python set implementation

class Solution(object):
    def containsDuplicate(self, nums):
        hset = set()
        for idx in nums:
            if idx in hset:
                return True
            else:
                hset.add(idx)

Others

Brute force (linear search)

For every item, check every item ahead if it’s equal to it (2x nested for loops)

• $O(n^2)$ time, $O(1)$ space
  • Will time out

Python code

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        i = 0
        while i < len(nums):
            curr = nums[i]
            j = i + 1
            while j < len(nums):
                if nums[j] == curr:
                    return True
                else:
                    j += 1
            i += 1
        return False

Sorting

Use a $O(nlog(n))$ sort (in place) first, then linear scan - check if prior element is identical

• $O(nlog(n))$ time, $O(1)$ space

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        list.sort(nums)
        i = 1
        while i < len(nums):
            if nums[i-1] == nums[i]:
                return True
            i += 1
        return False

---

• task Add detail in Hash table and Dictionary and Set that a Python dict and set both use a Hashmap