DSA-002 · FOCUSED PRACTICE
Contains Duplicate
Foundation · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 19534 deterministic checks. Learner drafts are not executed.
Understand the problem
Determine whether any value appears at least twice in the array. Return true as soon as a duplicate is established, otherwise return false.
- nums is a non-null int[] of 0–100,000 elements, each any signed int. Null is outside the contract.
- Return a boolean. Empty and singleton arrays return false. Equality is exact int equality; the positions need not be adjacent.
- Preserve input and its order. A duplicate value can occur more than twice; only existence is requested.
Examples
Input:
[1,2,3,1]
Output:trueThe first and last positions hold the same value.
Input:
[1,2,3,4]
Output:falseEvery value is distinct.
Input:
[-2147483648,2147483647,-2147483648]
Output:trueExtreme signed values are ordinary set keys; no subtraction is needed.
Before you start
- Java Set<Integer> and equality
- Expected hashing bounds versus sorting costs
Recognize the structure
The next element asks whether the same value has occurred in the processed prefix. Only presence matters, so a set is sufficient. Two Sum needs an earlier index and Subarray Sum needs multiplicity; retaining those extra fields is unnecessary for this boolean contract.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 88/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which fact about the past does the next value need?
Hint 2
Store distinct values already processed.
Hint 3
An insertion that does not add a new value proves a duplicate.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Sort a copy and inspect neighbors
Clone the input, sort the clone, then compare adjacent values. For [3,1,2,1], the sorted copy is [1,1,2,3] and the first comparison establishes a duplicate. Sorting places equal values next to one another, but costs O(n log n) time and O(n) copy space to preserve the caller’s data. Pairwise comparison is another valid, slower O(n²) baseline.
Improve the baseline
Retain seen values
Use HashSet<Integer> to represent precisely the values already processed. Order is not needed for the question.
Combine lookup and update
Set.add returns false when an equal value is already present. That unsuccessful insertion is the evidence for a duplicate; a successful insertion extends the prefix state.
Stop once existence is established
An additional value cannot invalidate a duplicate already found. Returning early is correct for existence, though a task asking for all duplicates would need to continue.
Why it is correct
Initialization
The empty set describes the empty processed prefix, which has no repeated pair.
Preservation
Before inserting the next value, the set contains exactly earlier values. Failed insertion therefore identifies two different positions holding equal values. Successful insertion means this position introduces no duplicate and makes the set accurate for the next prefix.
Termination
The finite scan either returns a justified true or processes every position. If all insertions succeeded, no position matched an earlier one, so false is correct.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public final class Solution {
public static boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int value : nums) if (!seen.add(value)) return true;
return false;
}
public static boolean baseline(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
for (int i = 1; i < sorted.length; i++) if (sorted[i] == sorted[i - 1]) return true;
return false;
}
}
Read the meaningful blocks
Use boxed keys
Java generics require Set<Integer>, not Set<int>. Equality is value equality for these keys.
Interpret add correctly
The reference tests !seen.add(value); true from add means a new value, not a duplicate.
Return false after the scan
A nonmatching pair alone proves nothing about later values; only the completed scan can establish absence.
Complexity
Expected O(n) time and O(u) extra set entries, where u is the number of distinct values before termination. Hash membership has expected rather than unconditional worst-case constant cost.
The output is one boolean. The sorting baseline takes O(n log n) time and O(n) space for its copy. Neither method changes input.
Exact-state walkthroughs
Reveal normal and boundary traces
A nonadjacent repeat
Input: [1,2,3,1] · Result: true
Step 1 of 6: Begin with an empty processed prefix.
The set contains exactly the earlier values.
- 0: 1
- 1: 2
- 2: 3
- 3: 1
| Variable | Value |
|---|---|
| seen | [] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.HashSet; 3 import java.util.Set; 4 public final class Solution { 5 public static boolean containsDuplicate(int[] nums) { 6 Set<Integer> seen = new HashSet<>(); 7 for (int value : nums) if (!seen.add(value)) return true; 8 return false; 9 } 10 public static boolean baseline(int[] nums) { 11 int[] sorted = nums.clone(); 12 Arrays.sort(sorted); 13 for (int i = 1; i < sorted.length; i++) if (sorted[i] == sorted[i - 1]) return true; 14 return false; 15 } 16 } 17
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an empty processed prefix.
The set contains exactly the earlier values.
- seen
[]
- Insert the next value and inspect whether it was new.
The set now describes the extended prefix.
- index
0- value
1- duplicate
false- seen
[1]
- Insert the next value and inspect whether it was new.
The set now describes the extended prefix.
- index
1- value
2- duplicate
false- seen
[1,2]
- Insert the next value and inspect whether it was new.
The set now describes the extended prefix.
- index
2- value
3- duplicate
false- seen
[1,2,3]
- Insert the next value and inspect whether it was new.
This value already had an earlier occurrence.
- index
3- value
1- duplicate
true- seen
[1,2,3]
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
true
No pair of positions
Input: [] · Result: false
Step 1 of 2: Begin with an empty processed prefix.
The set contains exactly the earlier values.
Empty at this step.
| Variable | Value |
|---|---|
| seen | [] |
See the affected Java block
1 import java.util.Arrays; 2 import java.util.HashSet; 3 import java.util.Set; 4 public final class Solution { 5 public static boolean containsDuplicate(int[] nums) { 6 Set<Integer> seen = new HashSet<>(); 7 for (int value : nums) if (!seen.add(value)) return true; 8 return false; 9 } 10 public static boolean baseline(int[] nums) { 11 int[] sorted = nums.clone(); 12 Arrays.sort(sorted); 13 for (int i = 1; i < sorted.length; i++) if (sorted[i] == sorted[i - 1]) return true; 14 return false; 15 } 16 } 17
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Begin with an empty processed prefix.
The set contains exactly the earlier values.
- seen
[]
- Return the contract result.
The completed state satisfies the declared output and mutation contract.
- result
false
Test the contract
Input:
[]
Output:falseNo pair of positions.
Input:
[7]
Output:falseOne occurrence.
Input:
[0,0]
Output:trueRepeated zero.
Input:
[2,2,2]
Output:trueEarly success is enough.
Common mistakes and counterexamples
Only compare neighboring input positions
Counterexample: [1,2,1] has a nonadjacent duplicate.
Use a set or first sort a copy.
Reverse the meaning of add
Counterexample: [5] must return false even though add(5) returns true.
A failed insertion indicates repetition.
Return false after the first new value
Counterexample: [1,2,1] still has a later repetition.
Return false only after all positions have been considered.
Follow-ups
Return every duplicated value once.
Continue scanning, keep seen and duplicated sets, and define output order. Emitting every repeated occurrence would be a different contract.
Detect duplicates only within distance k.
Maintain a sliding set of at most k earlier values, removing the value that leaves the window. Specify the update order and k=0 behavior.
The stream is larger than memory.
Exact arbitrary-value membership may require external storage or sorting. A Bloom filter can suggest repetition but has false positives and cannot replace this exact boolean contract without changed guarantees.