🤖
Data Structures and Algorithms
  • CS Theory And Problems
  • Big O
    • Big O Notation
  • Algorithms
    • Binary Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Dynamic Programming
    • Kadane's Algorithm
    • Kahn's Algorithm
    • Quickselect
    • Recursion
    • Sorting Algorithms
    • Sliding Window
  • Data Structures
    • Binary Heap
    • Graph
    • Linked List
    • Trees
  • Problems
    • LeetCode
      • 1. Two Sum
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 11. Container With Most Water
      • 15. 3 Sum
      • 19. Remove Nth Node From End of List
      • 20. Valid Parentheses
      • 33. Search in Rotated Sorted Array
      • 49. Group Anagrams
      • 53. Maximum Subarray
      • 55. Jump Game
      • 56. Merge Intervals
      • 76. Minimum Window Substring
      • 98. Validate Binary Search Tree
      • 105. Construct Binary Tree from Preorder and Inorder Traversal
      • 121. Best Time to Buy and Sell Stock
      • 133. Clone Graph
      • 141. Linked List Cycle
      • 152. Maximum Product Subarray
      • 153. Find Minimum in Rotated Sorted Array
      • 200. Number of Islands
      • 206. Reverse Linked List
      • 207. Course Schedule
      • 217. Contains Duplicate
      • 226. Invert Binary Tree
      • 238. Product of Array Except Self
      • 242. Valid Anagram
      • 297. Serialize and Deserialize Binary Tree
      • 347. Top K Frequent Elements
      • 417. Pacific Atlantic Water Flow
      • 424. Longest Repeating Character Replacement
      • 435. Non-overlapping Intervals
      • 647. Palindromic Substrings
Powered by GitBook
On this page
  • Description
  • Solutions
  • Solution 1
  • Solution 2
  • Solution 3
  1. Problems
  2. LeetCode

217. Contains Duplicate

Previous207. Course ScheduleNext226. Invert Binary Tree

Last updated 3 years ago

Description

See

Solutions

There are numerous solutions to this problem. Here are a few.

Solution 1

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return len(set(nums)) != len(nums)

Space O(N), Time O(N) - from creating the set

Solution 2

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        cache = defaultdict(int)
        for i in nums:
            if i in cache:
                return True
            else:
                cache[i] = i
        return False

Space O(N), Time O(N)

Solution 3

This would be the slowest solution as it has the overhead of sorting the list.

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

Space O(N), Time O(N log N) - Time complexity for sort. See:

https://leetcode.com/problems/contains-duplicate/
https://wiki.python.org/moin/TimeComplexity