Find Duplicates in Array Java | Fresher Interview
Fast recall
Quick revision
Core answer
add it - if add returns false (already present) you found a duplicate. This is O(n) time and O(n) space, beating the O(n^2) brute-force double loop. If the array is sorted (or you sort it), adjacent equal elements reveal duplicates in O(n) with O(1) extra space.Whether you reach for a HashSet to trade space for time instead of the O(n^2) nested loop
Defaulting to nested loops (O(n^2)) or forgetting HashSet.add returns false on a duplicate
State the space-time tradeoff and offer the sort-based O(1)-space alternative
Interview-ready guide
Interview answer
The naive way is a double loop that compares every element with every other element, which is O of n squared.
I'd mention it but immediately offer something better. The standard approach uses a HashSet as a record of what I've already seen. I scan the array once, and for each element I try to add it to the set.
The nice part is that HashSet's add method returns a boolean: true if the value was new, and false if it was already in the set. So the moment add returns false, I know I've hit a duplicate. That gives me O of n time and O of n space, because in the worst case the set holds every element.
This is a clear space-for-time trade-off: the set uses extra memory to remove the nested scan. If memory is tight, there's an alternative: sort the array first, which makes any duplicates land next to each other, and then a single pass comparing each element with the previous one finds them using only constant extra space.
The catch is that sorting is O of n log n and it reorders the data, so I wouldn't use it if the original order matters. One detail to watch is a value that appears three or more times: it'll trigger the duplicate signal more than once, so if I only want to report each duplicate a single time, I dedupe the output.
So my default is the HashSet for O of n, and I keep the sort-based approach in my back pocket for when space is the constraint.
Find Duplicates in Array Java | Fresher Interview
Direct Answer
Use a HashSet: scan the array, and for each element try to add it - if add returns false (already present) you found a duplicate. This is O(n) time and O(n) space, beating the O(n^2) brute-force double loop. If the array is sorted (or you sort it), adjacent equal elements reveal duplicates in O(n) with O(1) extra space.
Deep Dive & Architecture
A HashSet answers the useful question for each number: “Have I seen this value before?” Its add method returns false when the value is already present, so a second occurrence is detected during the same scan.
Worked example: [3, 1, 3, 3]
Add 3, then add 1. The next 3 cannot be added, so it is a duplicate. The final 3 also cannot be added. If the output should contain each duplicate only once, place duplicates in a second set; the result is simply {3}. If the requirement is to report every repeated occurrence, add directly to a list instead.
This distinction belongs in the problem contract. “Find duplicates” can mean return unique duplicate values, count each value, or return duplicate indexes. A set solves membership, while a HashMap<Integer, Integer> is better when counts or positions are required.
The set approach takes O(n) average time and O(n) extra space. Sorting first can reduce extra storage when the input may be changed, but sorting costs O(n log n) and changes the original order. A nested scan avoids extra memory but costs O(n²).
Code Example
List<Integer> findDuplicates(int[] nums) {
Set<Integer> seen = new HashSet<>();
List<Integer> dups = new ArrayList<>();
for (int x : nums) {
if (!seen.add(x)) dups.add(x); // add() false => already seen
}
return dups;
}
// nums = {3, 1, 3, 4, 1}
// add 3 -> true; add 1 -> true; add 3 -> false (dup!);
// add 4 -> true; add 1 -> false (dup!)
// dups = [3, 1]
Common Mistakes & Pitfalls
- Nested loops by default: O(n^2) is fine to mention but you should offer the O(n) HashSet version.
- Forgetting add()'s return:
HashSet.addreturns a boolean; using it avoids a separatecontainscall. - Reporting duplicates multiple times: a value appearing 3x triggers two 'false' returns - dedupe if you need each only once.
- Sorting when order matters: the O(1)-space sort approach reorders the input; don't use it if original order is needed.
Check your understanding
Answer these without looking back at the article.
- What is the time complexity of common array operations in Java?
- How do you reverse a string in Java without using built-in reverse methods?
- How do you check if two strings are anagrams of each other?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.