#217 Contains Duplicate
frequently reported atNetflixAirbnbBloombergMicrosoftAmazonGoogle
the problem
In plain words
Does the array hold some number more than once? Answer true if so, and false when every number is different.
in nums = [1,2,3,1]
out true
in nums = [1,2,3,4]
out false
in nums = [1,1,1,3,3,4,3,2,4,2]
out true
- 1 ≤ n ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)
"Have I seen this before?" is exactly what a HashSet answers in O(1), and add already tells you.
solutions
From brute force to optimal
Two loops looking for an equal pair.
- For each i, for each j > i, return true if nums[i] == nums[j].
All pairs. Too slow for n = 10⁵ (≈5·10⁹ comparisons).
No extra storage.
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; }}After sorting, equal values sit next to each other.
- Copy and sort.
- Return true if any copy[i] == copy[i−1].
The sort dominates.
The copy (sorting in place would be O(log n) but mutates the input).
class Solution { public boolean containsDuplicate(int[] nums) { int[] copy = nums.clone(); // don't surprise the caller by reordering their array Arrays.sort(copy); for (int i = 1; i < copy.length; i++) { if (copy[i] == copy[i - 1]) return true; // equal values are now neighbours } return false; }}Add each number. If add returns false, it was already there.
- For each x: if !seen.add(x) return true.
- Return false at the end.
n O(1)-average set operations, with an early exit on the first repeat.
Up to n distinct values stored.
class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> seen = new HashSet<>(); for (int x : nums) { if (!seen.add(x)) return true; // add() returns false when x is already there } return false; }}Dry run
in the room
How to say it in the interview
talk track
- Offer the trade-off out loud: "O(n) time with O(n) memory using a set, or O(n log n) time and only the sort's own memory if I may sort in place."
- Mention
set.addreturning a boolean. It saves a separatecontainscall.
traps
- Calling
containsand thenadd: two lookups whereaddalone answers the question. - Sorting
numsin place without asking — the caller may still need the original order. - Comparing every pair: about 5·10⁹ checks for n = 10⁵, far too slow.
what they ask next
Follow-ups
Contains Duplicate II (LC 219): equal values at most k apart?
Keep a sliding window of the last k values in a HashSet, or map value → last index.
Contains Duplicate III (LC 220): values within t and indices within k?
Bucket by value / (t + 1) in a map, or use a TreeSet window with ceiling.
before you submit
Edge cases to test
- One element → false.
- The repeat is the very first and very last element.
- Negative duplicates ([-1,5,-1]) → true.
practise next
Similar problems
- #1Two SumEasyin Hashing
- #220Contains Duplicate IIIHardin BST
- #705Design HashSetEasyin Java OOP