Friedrich Ewald My Personal Website

Leetcode: Contains duplicate

Given an array of nums, return True if there is a duplicated number and False otherwise. The simple most solution I could find was to use a set and then see for every number if it is already contained in the set. A map would have worked as well. The time complexity for this is O(n), assuming that the access to the hash set is O(1), it takes only one iteration over the whole list.

from typing import List, Optional

class Solution:
  def containsDuplicate(self, nums: List[int]) -> bool:
    s = set()
    for n in nums:
      if n in s:
        return True
    return False

if __name__ == '__main__':
  s = Solution().containsDuplicate
  print(s([1,2,3,1]), True)
  print(s([1,2,3,4]), False)
  print(s([1,1,1,3,3,4,3,2,4,2]), True)
Runtime: 439 ms, faster than 99.61% of Python3 online submissions for Contains Duplicate. Memory Usage: 26 MB, less than 71.55% of Python3 online submissions for Contains Duplicate.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.