Find duplicate elements in an array.

Hook: Interviewers love this one because it reveals whether you can replace a slow double-check with a clean one-pass solution.

Question: Find duplicate elements in an array.

Answer: The easiest reliable way in Java is to scan the array once and keep a Set of values you have already seen. If the current value is already in the set, that value is a duplicate, so you record it in a second set. This works for any integers, including negatives and zero, and it avoids the slow nested-loop approach.

Interview-Ready Answer: I would use a HashSet to track numbers I have already seen. As I iterate through the array, if add returns false, that means the value was already present, so I add it to a duplicates collection. I usually return a LinkedHashSet so each duplicate appears once and the encounter order is preserved. That gives me average O(n) time and O(n) extra space.

What it really means

A duplicate element is any value that appears more than once in the array. In interviews, the key detail is whether you need unique duplicate values like [1, 2] or all repeated occurrences like [1, 1, 2]. The standard solution below returns each duplicated value once, which is what most questions expect.

How the one-pass set solution works

1. Create a Set called seen. A Set is a collection that does not allow duplicates.
2. Create another set called duplicates. This keeps only the values that repeat.
3. Loop through the array from left to right.
4. For each number, try to add it to seen. In Java, Set.add(x) returns true if x was new, and false if it was already there.
5. If add returns false, the number has been seen before, so put it into duplicates.
6. At the end, return duplicates. If you use LinkedHashSet, the results come out in the order the duplicates were first discovered.

Memory Hook: Think of a party guest list: the first time a person arrives, they go into the lobby; the second time you see the same face, they go onto the blacklist. Seen once = lobby, seen twice = blacklist.

Why this is the best default answer

The brute-force way checks every pair of values, which is easy to imagine but slow: if the array has 10,000 items, that can mean about 50 million comparisons. The set-based solution checks each item once on average, so it is much faster and easier to explain cleanly at a whiteboard.

Comparison with other approaches

Complexity and real numbers

With a hash-based set, each lookup and insert is average O(1), so the whole scan is average O(n). In practice, if you store int values in HashSet<Integer>, Java must box them into Integer objects, which uses more memory than a raw primitive array. For one million distinct integers, the memory cost is often tens of megabytes, not just a few megabytes, because of object and hash table overhead.

Edge cases and gotchas

• Null or empty array: return an empty result or throw a clear exception, depending on the method contract.
• All values unique: the duplicate set should be empty.
• Same value repeated many times: the result should still contain that value only once if you want unique duplicates.
• Order matters: plain HashSet does not guarantee order; use LinkedHashSet if the presentation order matters.
• Already sorted input: a simple adjacent check after sorting can be fine, but it costs O(n log n) time.

Rule of thumb: if the question says duplicate elements and does not ask for counts or indices, the cleanest interview answer is usually seen set + duplicates set.

Real-World Story: Imagine a batch import service in an e-commerce platform that reads product IDs from a CSV before writing them to the catalog database. If the same product ID appears twice, the service may create duplicate records, confuse inventory counts, or trigger a unique-constraint error halfway through the import. A correct duplicate check lets the service reject the file early with a clear message like Duplicate product ID at row 183.

When this is misunderstood, the bug usually shows up as inconsistent totals: support sees one product listed twice, the log shows a database duplicate key error, and customers notice odd behavior like the same item appearing in search results multiple times. The real value of the duplicate-finding logic is not just correctness; it is making the failure obvious before bad data spreads through the system.

Follow-up & Tricky Questions:

• How would you return the duplicate counts too? Use a Map<Integer, Integer> and increment the count for each value. Then any entry with count greater than 1 is a duplicate, and you also know exactly how many times it appears.
• How do you preserve the order of duplicate discovery? Use LinkedHashSet instead of HashSet. A LinkedHashSet keeps insertion order, which is helpful when the interviewer wants results in a predictable sequence.
• Can you do this in O(1) extra space? Only if you are allowed to modify the array, for example by sorting it and then scanning neighbors. In the general unsorted case, you need extra memory for a set or map.
• What changes if the array is huge? The logic stays the same, but memory becomes important. For very large inputs, you may prefer primitive collections from third-party libraries or a sort-based approach if extra memory is the real bottleneck.
• How would you find duplicate indices, not just values? Store the first index for each value in a map, or store a list of indices per value. That way you can report exactly where the repeated items occur.
• Tricky: Does HashSet return duplicates in the same order as the array? No. HashSet does not guarantee iteration order, so if order matters, use LinkedHashSet or sort the result later.
• Tricky: If a value appears three times, do you get it three times in the duplicate list? Not with the usual unique-duplicate solution. The duplicate set contains the value once; if you need every repeated occurrence, you must return a list and add the value each time after the first.
• Tricky: What is the difference between a duplicate and a repeated occurrence? A duplicate value is the concept of a value appearing more than once, while repeated occurrences are the extra appearances beyond the first one. Interviewers sometimes use those words loosely, so clarify the expected output.

Common Mistakes:

• Using nested loops first. Correction: mention it as the brute-force baseline, then improve to a set-based one-pass solution.
• Returning the same duplicate many times. Correction: keep a second set or count map so each duplicate value is reported once unless the problem explicitly wants every repeat.
• Assuming order is guaranteed. Correction: HashSet does not preserve order; choose LinkedHashSet when order matters.
• Forgetting null and empty inputs. Correction: define the behavior clearly and handle it consistently.

Memory Hook: First time in the lobby, second time on the blacklist. That is the whole mental model for the set-based solution.

Cheat Sheet:

• Use seen set to track values already visited.
• If seen.add(x) is false, x is a duplicate.
• Use LinkedHashSet when you want stable order.
• Time is average O(n); extra space is O(n).
• Use a frequency map if you need counts too.
• Sort-and-scan is simpler on paper but slower at O(n log n).

Practice Tasks:

• Write a version that returns duplicate counts in a Map<Integer, Integer>.
• Adapt the code for String[] instead of int[].
• Return the first duplicate value only, not all duplicates.