nums array · pointer i walks left to right
seen hash set · 8 buckets · bucket = n mod 8
public boolean containsDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int n : nums) { if (seen.contains(n)) { return true; } seen.add(n); } return false;}
- n
- —
- i
- —
- n mod 8
- —
- seen
- {}
- lookups
- 0
Why it works
- Brute force compares every pair: n(n−1)/2 checks, O(n²). Fine for 10 values, hopeless for 10⁵.
- A set remembers what you have seen. One pass, one lookup per value. Space grows to O(n).
- Lookup is O(1) on average: the hash sends
nstraight to one bucket. Only that bucket's short chain is checked, never the whole set. - Exit early: the first repeat answers the question. Values after it are never touched.
- One-liner:
return Arrays.stream(nums).distinct().count() < nums.length;. Same O(n), but always builds the full set, so no early exit.