Count Duplicate Elements in an Array

Title: Count Duplicate Elements in an Array

Counting how many values in an array appear more than once is a classic interview warm-up that quickly exposes whether a candidate reaches for the right data structure. In this guide, you will learn an efficient Java solution that uses a HashMap to tally frequencies, walk through the logic one line at a time, and then stress the algorithm with a step-by-step trace, worked examples, and the interview-style follow-ups that typically come next.

Understanding the Problem

Given an integer array, we want to count the distinct values that occur more than once. A value that appears exactly once is not a duplicate; a value that appears two, three, or more times is a single duplicate value regardless of how many copies exist.

For example, the array {4, 2, 7, 2, 4, 9, 7, 1} has three values that repeat: 4, 2, and 7. Even though those three values together account for six positions in the array, the duplicate count is 3 because we are counting values, not occurrences.

Pin down the definition before you code. Confusing the number of duplicate values with the number of extra occurrences is the single most common bug on this problem, so make sure the interviewer and you agree on which number is being asked for.

Approach to Count Duplicate Elements

We will scan the array once and build a frequency map using a HashMap<Integer, Integer>. After the first pass, every distinct value is a key and its count is the value. We then sweep the map once and count how many keys have a frequency greater than one.

Here are the steps:

1. Create an empty HashMap<Integer, Integer> called frequency.
2. Iterate over every element value in the input array.
3. Set frequency.put(value, frequency.getOrDefault(value, 0) + 1) to bump the running tally.
4. Initialize an int counter duplicateCount to 0.
5. Iterate over frequency.values(); whenever a count is greater than 1, increment duplicateCount.
6. Return duplicateCount as the final answer.

Java Program to Count Duplicate Elements in an Array

Let us put the approach into a complete, compilable Java program:

import java.util.HashMap;
import java.util.Map;

public class CountDuplicateElements {

    public static int countDuplicates(int[] arr) {
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int value : arr) {
            frequency.put(value, frequency.getOrDefault(value, 0) + 1);
        }
        int duplicateCount = 0;
        for (int count : frequency.values()) {
            if (count > 1) {
                duplicateCount++;
            }
        }
        return duplicateCount;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 7, 2, 4, 9, 7, 1};
        int duplicates = countDuplicates(arr);

        System.out.println("Array length: " + arr.length);
        System.out.println("Duplicate values: " + duplicates);
    }
}

Explanation of the Program

• The method countDuplicates accepts an int[] and returns the number of distinct values whose frequency is greater than one.
• A HashMap<Integer, Integer> named frequency stores every value as a key and its running count as the value. The hash table gives amortized O(1) put and get.
• The enhanced for loop visits each element exactly once. The call getOrDefault(value, 0) returns zero on the first sighting and the prior count on later sightings, so the put always writes the correct updated count.
• After the first pass, every distinct value has been counted. The second loop walks only frequency.values(), which is at most n entries but is usually far fewer, and bumps duplicateCount whenever the frequency clears two.
• The main method prints both the array length and the duplicate count side by side so you can confirm the answer is a count of values, not a count of extra positions.

Step-by-Step Trace

Let us walk the algorithm through the first pass on a small, fresh input. Consider arr = {6, 2, 6, 9, 2, 4}; frequency starts empty.

At the end of iteration i, frequency.get(v) is the number of times v has appeared in arr[0..i]. After the first pass the map holds {6=2, 2=2, 9=1, 4=1}; the second loop checks each value and counts 6 and 2, giving a final duplicateCount of 2. That invariant is why a single frequency pass plus a short second sweep is enough to solve the problem.

Examples

Let us look at a few runs that stretch different parts of the algorithm.

Example 1: Several Values Appearing Twice

int[] arr = {5, 3, 5, 1, 3, 8, 1};
int duplicates = countDuplicates(arr);

System.out.println("Duplicate values: " + duplicates);
// Output: Duplicate values: 3

The array has seven elements. 5, 3, and 1 each appear twice, while 8 appears once. Three distinct values qualify as duplicates, so the answer is 3.

Example 2: All Elements Distinct

int[] arr = {10, 20, 30, 40, 50};
int duplicates = countDuplicates(arr);

System.out.println("Duplicate values: " + duplicates);
// Output: Duplicate values: 0

No value repeats, so the frequency map maps every key to 1 and no entry clears the threshold. The duplicate count is 0, which is the expected answer for a strictly unique array.

Example 3: Triplicates and a Single Pair

int[] arr = {8, 8, 8, 3, 3, 1, 5};
int duplicates = countDuplicates(arr);

System.out.println("Duplicate values: " + duplicates);
// Output: Duplicate values: 2

The value 8 appears three times and 3 appears twice, while 1 and 5 appear once each. Two distinct values are duplicates, so the answer is 2. Notice that the three copies of 8 still count as a single duplicate value; the extra copy does not add to the result.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing duplicate counting:

• Counting occurrences instead of values – returning arr.length - frequency.size() reports the number of extra positions, which is 5 for {8, 8, 8, 3, 3, 1, 5} rather than the expected 2. Count map entries whose value is greater than one.
• Using >= 1 instead of > 1 – a threshold of >= 1 treats every distinct value as a duplicate and silently returns the number of distinct values. The correct threshold is strictly greater than one.
• Incrementing inside the first loop – bumping duplicateCount every time a value is seen a second time inflates the result for triplicates and beyond; {8, 8, 8} would be counted twice instead of once. Count values in the second pass over frequency.values(), or use the explicit guard frequency.get(value) == 2 inside the first loop.
• Confusing duplicate count with distinct count – returning frequency.size() gives the number of distinct values, not the number of duplicates. Keep the two concepts separate; this problem asks for the second.
• Forgetting to handle a null array – calling arr.length on null throws NullPointerException. Decide up front whether null is an error or a zero-length input, then write the guard clause explicitly.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Empty array
• Single-element array
• All identical elements
• All distinct elements
• Array containing negative numbers
• Array containing zero alongside positive and negative values
• Integer.MIN_VALUE and Integer.MAX_VALUE present
• Null array reference

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: The first pass runs n amortized O(1) map updates and the second pass walks at most n map entries, so the total running time is O(n).
2. Space complexity: In the worst case every element is distinct, so the map stores n entries, giving O(n) extra space. For an array of all duplicates the map holds only one entry.
3. Autoboxing cost: Each int gets boxed to an Integer before being stored. For hot code paths this allocation pressure matters; a primitive map like Eclipse Collections’ IntIntHashMap avoids it.
4. Why Integer.MIN_VALUE matters: A frequency array indexed by value would need to shift negative indices or crash on them; a HashMap handles the full int range without any special case.
5. Alternative with sorting: Sorting the array in O(n log n) and counting runs where arr[i] == arr[i - 1] and arr[i] != arr[i - 2] gives the same answer with O(1) extra space, but it mutates the input and runs slower than the hash-map pass.

Interview Follow-up Questions

Once the base version works, an interviewer will usually probe deeper with questions like these:

• What if the array is already sorted? – skip the map entirely and scan once, counting a duplicate value the first time a run of equal elements reaches length two; this runs in O(n) time with O(1) extra space.
• What if you need the duplicate values themselves, not just the count? – collect every key whose value exceeds one into a List<Integer> during the second pass; the asymptotic work is unchanged.
• What if you need the total number of extra occurrences instead? – sum frequency.get(k) - 1 over every key, which is the same as arr.length - frequency.size() and answers a different, equally common variant of the problem.
• What if the input is a stream of unknown length? – keep the HashMap alive as values arrive and report duplicateCount when the stream ends; the first-pass logic is identical, only the termination condition changes.
• How would you handle billions of entries that will not fit in memory? – approximate with a count-min sketch to detect heavy hitters, or sort the input with external merge sort and count repeated runs on disk; both trade exactness or extra passes for a bounded memory footprint.

Conclusion

In this guide, we walked through counting duplicate elements in a Java array using a HashMap for frequencies. The countDuplicates method scans the array once to tally every value, then walks the frequency entries once more and returns the number of keys whose count is greater than one. The running time is O(n) and the extra space is O(n) in the worst case, which is the right trade-off for most real-world inputs.

Try adapting the code to list the duplicate values themselves, swap the map for a sorted scan, or layer the counting on top of a stream whose length is not known in advance. Happy coding!

You can learn more about Array techniques: Arrays