Contains Duplicate (LeetCode #217)

Introduction:
I'm diving into a very common interview question: "Contains Duplicate" (LeetCode #217). This problem is fantastic for understanding how to efficiently check for the presence of elements, and it beautifully illustrates the power of a specific data structure: the HashSet
.
Understanding the Problem:
The problem is straightforward: Given an integer array nums
, we need to determine if any value appears more than once in the array. If even one duplicate is found, we should return true
. If all elements are unique, we return false
.
Let's look at some examples:
Input:
nums = [1, 2, 3, 1]
- Expected Output:
true
(because '1' appears twice)
- Expected Output:
Input:
nums = [1, 2, 3, 4]
- Expected Output:
false
(all elements are unique)
- Expected Output:
Input:
nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
- Expected Output:
true
(many duplicates here!)
- Expected Output:
My Thought Process & Approach:
When approaching "Contains Duplicate," my immediate thought goes to checking each number against every other number. This would involve nested loops, leading to a less efficient solution (O(N^2) time complexity). While it works, interviewers often look for more optimized approaches.
This is where the idea of quickly checking if I've already seen a number comes in. If I encounter a number and realize I've seen it before, then it's a duplicate! To do this efficiently, I need a data structure that allows for very fast lookups and additions.
This points directly to using a HashSet
in Java. A HashSet
stores unique elements and provides average O(1) time complexity for add()
and contains()
operations.
Here's the refined logic:
Initialize a
HashSet
: Create an emptyHashSet
to store all the numbers we encounter.Iterate through the array: Go through each number (
n
) in the input arraynums
one by one.Check for Duplicates: For each
n
:First, ask the
HashSet
: "Have I seen this numbern
before (hs.contains(n)
)?"If the answer is yes, it means
n
is a duplicate, so we immediately returntrue
. We don't need to check any further!
Add to Set: If the answer was no (we haven't seen
n
before), then addn
to theHashSet
(hs.add(n)
) so we remember it for future checks.No Duplicates Found: If the loop finishes without ever returning
true
, it means we went through the entire array and never found a duplicate. In this case, we returnfalse
.
Java Code Implementation:
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> hs = new HashSet<>();
for(int n : nums){
if(hs.contains(n)){
return true;
}
hs.add(n);
}
return false;
}
}
Time and Space Complexity Analysis:
Time Complexity: O(N) (Average Case)
We iterate through the input array
nums
exactly once.Inside the loop,
hs.contains(n)
andhs.add(n)
operations on aHashSet
take average O(1) time. In the worst case (no duplicates, or duplicate at the very end), the loop runsN
times, making the overall time complexity linear, O(N).In the best case (e.g.,
[1, 1, 2, 3]
), it returnstrue
almost immediately.This is the optimal time complexity because, to guarantee no duplicates, you must examine every element at least once.
Space Complexity: O(N) (Worst Case)
In the worst case (e.g., all elements in
nums
are unique), theHashSet
will end up storing allN
unique elements.Therefore, the space required by the
HashSet
grows linearly with the size of the input array, resulting in O(N) space complexity. This is optimal for approaches using auxiliary space to track seen elements.
Subscribe to my newsletter
Read articles from Kaushal Maurya directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
