→ "Appears at least twice": have I seen this value before?
→ n up to 10⁵ rules out comparing all pairs
→ Values up to 10⁹ rule out a simple counting array
These clues point to Hash Map Lookup (Complement): As you scan, store what you've seen; for each new element, ask in O(1) whether its partner was already seen.
Stuck? Take one hint at a time
Solution.java · starter
import java.util.*;
class Solution {
public boolean containsDuplicate(int[] nums) {
// remember what you've seen
return false;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
For each index i, compare nums[i] with every later element. If any are equal, return true.
Approach 1
class Solution {
public boolean containsDuplicate(int[] nums) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] == nums[j]) return true;
return false;
}
}
Verdict: About 5 × 10⁹ comparisons for n = 10⁵: far too slow. Useful only to confirm you understand the problem.
2
Better: sort, then check neighbours
Time O(n log n) Space O(1) extra (O(log n) for the sort's internal stack)
After sorting, equal values sit next to each other, so one pass comparing each element with the next finds any duplicate.
Approach 2
import java.util.Arrays;
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++)
if (nums[i] == nums[i - 1]) return true;
return false;
}
}
Verdict: Fast enough for 10⁵, and uses almost no extra memory. A good answer if memory is tight; it does reorder the input.
3
Optimal: hash set of seen values
Time O(n) Space O(n)
Walk the array once and keep a HashSet of values seen so far. Before adding each value, check whether it's already in the set. HashSet.add returns false if the value was already present, which does both in one call.
import java.util.HashSet;
import java.util.Set;
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int x : nums) {
if (!seen.add(x)) return true; // add() is false when x was already there
}
return false;
}
}
Verdict: One pass with O(1) average lookups. The standard answer; mention the sorting version if asked to save memory.
Before you submit
Edge cases and common mistakes
Test these inputs
Single element → false
Duplicate at the very end
Negative numbers and zero
All elements equal
Mistakes people make
Using a boolean[] indexed by value: values go up to 10⁹ and can be negative.
Calling seen.contains(x) and then seen.add(x): correct, but add's return value already tells you.
In the sorted version, starting the loop at 0 and reading nums[i - 1] out of bounds.
Interview
Follow-up questions
What if duplicates only count when they're at most k positions apart?