Leetcode 217: Contains Duplicate

I tackled Leetcode problem 217, which asks to determine if a list contains any duplicates.

Problem statement:

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.

Example 1:
Input: nums=[1,2,3,1]
Output: true

Example 2:
Input: nums=[1,2,3,4]
Output: false

Example 3:
Input: nums=[1,1,1,3,3,4,3,2,4,2]
Output: true

Approach Taken:

Here, I used a set to keep track of unique elements encountered as I iterate through the list:

Why set?

A set in Python is implemented as a hash table, which allows for average O(1) time complexity for both insert and lookup operations. This means that checking if an element is already in the set and adding a new element to the set are both very fast, even for large datasets.

Also, sets do not allow duplicate elements which makes it easier to keep track of elements that have already been seen. There’s no need to write additional logic to handle duplicates since the set takes care of it automatically.

Code Approach:

1. Initialization: We initialize an empty set called ‘unique’. This set will store all unique elements we encounter in the list ‘nums’.
2. Iteration: We iterate over each element ‘i’ in ‘nums’.
3. Duplicate Check: For each element, we check if it already exists in the ‘unique’ set using the ‘if i in unique’ statement. This check is very fast due to the O(1) average time complexity for lookups in a set.
4. Duplicate Found: If the element is found in the set, it means we have encountered a duplicate, and we immediately return ‘True’.
5. Adding Element: If the element is not found in the set, we add it to the set using ‘unique.add(i)’. Adding an element to a set also has an O(1) average time complexity.
6. Completion: If the loop completes without finding any duplicates, we return ‘False’.

Time Complexity: The for loop iterates through ’n’ elements, with each membership check and insertion operation in the set taking O(1) time on average. Therefore, the overall time complexity is O(n).

Space Complexity: In the worst case, all ’n’ elements in the list ‘nums’ are unique, and the set ‘unique’ will store all ’n’ elements. So the space required to store ’n’ elements in a set is O(n).

Solution for Leetcode 217

References: Neetcode