Welcome to day one of my LeetCode adventure! Today’s problem is called “Contains Duplicate” and it asks a simple question: does any number appear at least twice in a given array?
If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!
Let’s dive in!
Understanding the Problem
We’re given an integer array nums. We need to determine if any number appears more than once in the array. If a duplicate exists, the function should return True, otherwise False.
Brute Force Approach
The first solution that might come to mind is to iterate through the array twice. During the first loop, we can compare each element with every other element. If we find a match, it means there’s a duplicate and we can return True.
Here’s the Python code for this approach:
def containsDuplicate(self, nums: List[int]) -> bool:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
Time Complexity: This approach has a time complexity of O(n²). This is because we have two nested loops, each iterating through the entire array. As the size of the array (n) increases, the number of comparisons grows quadratically.
Space Complexity: The space complexity of this approach is O(1) because it only uses a constant amount of extra space for variables like i and j.
Thinking More Efficiently
The brute force approach works, but it’s not very efficient for larger datasets. Can we do better?
Using a Hash Table (More Efficient)
A more efficient solution utilizes a hash table (also called a dictionary in Python). Hash tables allow us to store key-value pairs and perform lookups in constant time (on average).
Here’s how we can solve this problem using a hash table:
def containsDuplicate(self, nums: List[int]) -> bool:
# Create a hash table to store seen numbers
seen = {}
for num in nums:
# If the number already exists in the hash table, we found a duplicate
if num in seen:
return True
# Otherwise, add the number to the hash table
seen[num] = True
# If the loop completes without finding a duplicate, return False
return False
Explanation:
- We initialize a dictionary seen to store the numbers we’ve encountered so far.
- We iterate through the nums array.
- For each number (num), we check if it exists as a key in the seen dictionary.
- If it exists, it means we’ve seen this number before, so we return True.
- If it doesn’t exist, we add the number as a key and True as the value to the seen dictionary. (Note: You can use anything as the value, doesn’t have to True)
- Lastly, if the loop completes without finding a duplicate, it means all the elements are unique and we return False.
Time Complexity: This approach has a time complexity of O(n) because we iterate through the array only once. The lookups in the hash table are on average constant time (O(1)).
Space Complexity: The space complexity is O(n) because we use a hash table to store potentially all the unique elements from the array.
Challenge for you guys!
We’ve explored the brute force and hash table approaches to solve this problem. There’s another efficient approach that leverages Python’s built-in set data structures. Sets are collections that only store unique elements, and attempting to add a duplicate element is ignored. This property can be useful for solving this problem.
I encourage you to try implementing this approach yourself!
Experimenting with different solutions is a great way to solidify your understanding and explore alternative techniques.
Conclusion
Today, we tackled the “Contains Duplicate” problem on LeetCode. We explored two approaches: a brute force method with a time complexity of O(n²) and a more efficient solution using a hash table with a time complexity of O(n) and space complexity of O(n).
As we progress through our LeetCode journey, we’ll encounter more problems that can be solved with different levels of efficiency. It’s important to consider both the time and space complexity when choosing an approach.
Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.
