Contains Duplicate

Last updated on Jul 9, 2020 Leetcode

Question
Solution
- First try
- Improve
Summary

Question

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution

First try

My intuition is to use hash table (dictionary) to solve this question. Similar to Two Sum, we can build hash table while go through all the elements. Let’s try.

def containsDuplicate(nums):
  if nums == []:
    return False
  num_table = {}
  
  for i in nums:
    if i in num_table:
      return True
    else:
      num_table[i] = 1
  return False

nums = [1,1,3,4,5]

containsDuplicate(nums)

## True

Success
Details 
Runtime: 252 ms, faster than 5.77% of Python online submissions for Contains Duplicate.
Memory Usage: 18.7 MB, less than 13.80% of Python online submissions for Contains Duplicate.

Improve

After looking at the discussion section. I found many people use set function which is faster than a dictionary.

Python | set() method
Set, a term in mathematics for a sequence consisting of distinct language is also extended in its language by Python and can easily be made using set().
set() method is used to convert any of the iterable to sequence of iterable elements with dintinct elements, commonly called Set. source

The code is similar

def containsDuplicate2(nums):
  seen = set()
  for num in nums:
    if num not in seen:
      seen.add(num)
    else:
      return True
  return False
  
nums = [1,1,3,4,5]

containsDuplicate(nums)

## True

Success
Details 
Runtime: 140 ms, faster than 21.75% of Python online submissions for Contains Duplicate.
Memory Usage: 18 MB, less than 76.68% of Python online submissions for Contains Duplicate.

Summary

Dictionary is searching key.
set function is faster than a dictionary.

Leetcode