Introduction
Finding duplicate numbers in an array is one of the most frequently asked questions in Java coding interviews, precisely because it offers such a clear, teachable progression from a naive O(n²) brute-force solution to an optimal O(n) approach using a HashSet — exactly the kind of algorithmic optimization story interviewers love to walk through with candidates.
This guide covers the brute-force nested-loop approach, a sorting-based method, the optimal HashSet approach, a HashMap-based variant that also counts how many times each duplicate appears, and a modern Streams-based alternative — giving you a complete toolkit for this classic problem along with a clear understanding of each approach's time and space trade-offs.
Understanding the Problem: Detecting vs Counting Duplicates
There are two related but distinct versions of this problem worth distinguishing upfront:
- Simply identifying which values are duplicated (regardless of how many times).
- Counting exactly how many times each duplicate value appears.
Both are covered in this guide, since real interview questions and practical use cases ask for either version depending on context.
Method 1: Brute Force Using Nested Loops
The most straightforward approach compares every element against every other element.
public class DuplicatesBruteForce {
public static void main(String[] args) {
int[] arr = {4, 3, 6, 2, 8, 3, 6, 9};
System.out.println("Duplicate numbers:");
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) {
System.out.print(arr[i] + " ");
break;
}
}
}
}
}How this works
The outer loop picks each element, and the inner loop checks every element that comes after it (starting from i + 1, avoiding redundant comparisons and self-comparison) for a match. The break statement prevents printing the same duplicate value multiple times if it appears more than twice.
Output:
Duplicate numbers:
3 6The problem: this approach runs in O(n²) time, since every element is compared against nearly every other element — for an array of 10,000 elements, that's roughly 100 million comparisons, clearly impractical at scale.
Method 2: Using Sorting
Sorting the array first brings duplicate values next to each other, allowing a single linear pass to detect them.
import java.util.Arrays;
public class DuplicatesSorting {
public static void main(String[] args) {
int[] arr = {4, 3, 6, 2, 8, 3, 6, 9};
Arrays.sort(arr);
System.out.println("Duplicate numbers:");
for (int i = 1; i < arr.length; i++) {
if (arr[i] == arr[i - 1]) {
System.out.print(arr[i] + " ");
}
}
}
}How this works
After sorting, the array becomes:
{2, 3, 3, 4, 6, 6, 8, 9}Any duplicate values become adjacent to each other. The loop simply checks whether each element equals the one immediately before it, printing it if so.
Output:
Duplicate numbers:
3 6Time complexity: Arrays.sort() runs in O(n log n), and the subsequent linear scan is O(n) — giving an overall O(n log n) time complexity, a meaningful improvement over brute force's O(n²), though this approach does modify the original array's order (a consideration if the original ordering needs to be preserved).
Method 3: Using a HashSet (Optimal Approach)
The most efficient standard approach uses a HashSet to track values already seen, achieving O(n) time complexity.
import java.util.HashSet;
public class DuplicatesHashSet {
public static void main(String[] args) {
int[] arr = {4, 3, 6, 2, 8, 3, 6, 9};
HashSet<Integer> seen = new HashSet<>();
HashSet<Integer> duplicates = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) {
duplicates.add(num);
}
}
System.out.println("Duplicate numbers: " + duplicates);
}
}How this works
seen.add(num) attempts to add each number to the seen set, returning false if that value was already present (since HashSet doesn't allow duplicates).
When add() returns false, we know we've encountered a repeat, so it's added to a separate duplicates set (itself a HashSet, automatically avoiding printing the same duplicate value more than once even if it repeats three or more times).
Output:
Duplicate numbers: [3, 6]Why this is optimal
HashSet operations (add(), contains()) run in O(1) average time, making the entire algorithm O(n) overall — a single pass through the array, with constant-time work per element.
This is generally the expected, ideal answer in technical interviews for this exact problem.
