Leetcode # 217. Contains Duplicate

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

Solution

Sorting

Time Complexity: O(n * log(n))

Space Complexity:

• O(1) with heap sort
• Worst case space complexity is O(n) and best case O(1) with sort() in Python

class Solution:
  def containsDuplicate(self, nums: List[int]) -> bool:
    nums.sort()
    for i in range(1, len(nums)):
      if nums[i] == nums[i - 1]:
        return True
    return False

Hash Table

Time Complexity: O(n)
Space Complexity: O(n)

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

Last Updated on 2023/08/16 by A1go