Welcome to Day 3 of the Tekraze DSA series, where we solve Contains Duplicate in Java, Python and Rust. On Day 1 we used a hash map for Two Sum. Today we use its simpler cousin, the hash set, to answer one of the most common questions in programming: have I seen this value before?
Also Read: Day 1 of the series, Two Sum in Java, Python and Rust
What is the Contains Duplicate problem?
You get an integer array nums. Return true if any value appears at least twice, and false if every element is distinct.
Contains Duplicate examples
text
Input: nums = [1, 2, 3, 1] Output: true Why: 1 appears twice Input: nums = [1, 2, 3, 4] Output: false Why: every number is different
How should you think about it in plain words?
Imagine checking guests at a party door. Each time someone arrives you look at your guest book. If the name is already written there, someone came in twice and you can stop. If not, you write the name down and let them in.
The guest book is a hash set. Looking up a name and writing a new one both take roughly constant time, so one walk through the array is enough.
What does the brute force Contains Duplicate solution look like?
The first idea is to compare every element with every element after it.
python
def contains_duplicate_brute(nums):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
Time is O(n²) because every pair gets compared. Space is O(1). It works for tiny inputs, but with 100,000 numbers that is around five billion comparisons.
A middle option is to sort first and then check neighbours, since equal values end up side by side. That takes O(n log n) time and little extra space, and it is a good answer when memory is tight.
Also Read: DSA Series Day 2: Best Time to Buy and Sell Stock in Java, Python and Rust
How do we get the optimal O(n) solution?
Walk the array once with an empty set. For each number, if it is already in the set, return true. Otherwise add it. If the loop finishes, there were no repeats.
Time is O(n) on average, because set lookups and inserts are O(1) on average. Space is O(n), since in the worst case every number goes into the set. If you want to see how these numbers are worked out, read our Big O helper post on time and space complexity.
Contains Duplicate in Java
java
import java.util.HashSet;
import java.util.Set;
public class Solution {
public static boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
if (!seen.add(n)) {
return true; // add returns false when n is already in the set
}
}
return false;
}
public static void main(String[] args) {
int[][] tests = {{1, 2, 3, 1}, {1, 2, 3, 4}, {1, 1, 1, 3, 3, 4, 3, 2, 4, 2}, {}, {-5, 5}};
boolean[] want = {true, false, true, false, false};
for (int i = 0; i < tests.length; i++) {
boolean got = containsDuplicate(tests[i]);
System.out.println("Test " + (i + 1) + ": " + got + " " + (got == want[i] ? "PASS" : "FAIL"));
}
}
}
Contains Duplicate in Python
python
def contains_duplicate(nums):
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
if __name__ == "__main__":
tests = [([1, 2, 3, 1], True), ([1, 2, 3, 4], False),
([1, 1, 1, 3, 3, 4, 3, 2, 4, 2], True), ([], False), ([-5, 5], False)]
for i, (nums, want) in enumerate(tests, 1):
got = contains_duplicate(nums)
print(f"Test {i}: {got} {'PASS' if got == want else 'FAIL'}")
Contains Duplicate in Rust
rust
use std::collections::HashSet;
fn contains_duplicate(nums: &[i32]) -> bool {
let mut seen = HashSet::with_capacity(nums.len());
// insert returns false when the value was already there
nums.iter().any(|&n| !seen.insert(n))
}
fn main() {
let tests: [(&[i32], bool); 5] = [
(&[1, 2, 3, 1], true),
(&[1, 2, 3, 4], false),
(&[1, 1, 1, 3, 3, 4, 3, 2, 4, 2], true),
(&[], false),
(&[-5, 5], false),
];
for (i, (nums, want)) in tests.iter().enumerate() {
let got = contains_duplicate(nums);
println!("Test {}: {} {}", i + 1, got, if got == *want { "PASS" } else { "FAIL" });
}
}
In Java and Rust the insert call already tells you whether the value was new, so you get the check and the insert in one step. I ran all three programs against the same five tests: a repeat, all distinct, many repeats, an empty array and negative numbers. Every one passed.
What are the tips and tricks for an easy Contains Duplicate solution?
- Spot the pattern. Words like duplicate, unique, seen before or first repeat almost always point to a hash set.
- Return early. Stop the moment you find a repeat. There is no reason to scan the rest of the array.
- Use the insert result.
HashSet.addin Java andinsertin Rust returnfalsefor an existing value, which saves a separate lookup. - Know the one liner. In Python
len(set(nums)) != len(nums)works, but it always builds the whole set, so mention that the loop can exit early. - Offer the trade off. A hash set gives O(n) time with O(n) space. Sorting gives O(n log n) time with less memory. Saying both shows real understanding.
- Check edge cases. An empty array, a single element, negative numbers and very large values should all just work with a set.
What are the common Contains Duplicate mistakes people make?
- Using a list instead of a set for
seen, which makes every lookup O(n) and the whole solution O(n²) again. - Sorting the input in place when the caller still needs the original order.
- Forgetting that sorting changes the complexity to O(n log n), not O(n).
- Counting every value with a map when you only need to know whether one repeats.
Where is the Contains Duplicate pattern used in the real world?
Duplicate checks are everywhere. Signup forms check whether an email is already registered. Payment systems reject a transaction ID they have already processed. Web crawlers keep a set of visited URLs so they don’t fetch the same page twice. Data pipelines use the same idea to drop repeated rows before loading them into a database.
Conclusion
Contains Duplicate is a warm-up, but it teaches the habit you will reuse all series: when you need to know whether you have seen something, reach for a hash set. Try solving it again without looking, then attempt the variant where duplicates only count if they are within k positions of each other. After that, read Day 2, Best Time to Buy and Sell Stock, to see how one pass with a running minimum replaces a slow nested loop.
Frequently asked questions about Contains Duplicate
Why is a hash set faster than comparing every pair?
A hash set checks whether a value exists in O(1) time on average, so one pass of O(n) replaces the O(n²) pair comparisons.
Can I solve Contains Duplicate without extra space?
Yes. Sort the array and compare neighbours. It uses little extra memory but takes O(n log n) time.
Is len(set(nums)) != len(nums) a good answer in Python?
It is correct and short, but it always builds the full set. The loop version can stop early at the first repeat, which is worth mentioning in an interview.
What is the difference between a hash set and a hash map here?
A set stores only keys, which is all you need to know if a value was seen. A map also stores a value, like the index we needed in Two Sum.
Is Contains Duplicate asked in interviews?
Yes, it is a very common warm-up question and leads into variants that add distance and value limits.
