Count Distinct Elements in an Array

Title: Count Distinct Elements in an Array

Counting the number of distinct, or unique, values in an array is a common warm-up problem that quickly turns into a real interview question once duplicates, large inputs, or memory limits enter the picture. In this guide, we will explore an efficient Java solution that uses a HashSet, walk through the logic line by line, and then push the problem with a step-by-step trace, concrete examples, and interview-style follow-ups.

Understanding the Problem

Given an integer array, we want to return the count of distinct values it contains. Two elements that compare equal are counted as a single distinct value no matter how many times they appear. We do not need to return the distinct values themselves, only how many there are.

For example, the array {4, 2, 7, 2, 4, 9, 7, 1} contains five distinct values: 4, 2, 7, 9, and 1. So the answer is 5 even though the array length is 8.

This problem is a good excuse to practice choosing the right data structure. A HashSet gives us constant-time membership checks on average, which is exactly what we need to decide whether a value we just read has been seen before.

Approach to Count Distinct Elements

We will scan the array once and remember every value we have already seen using a HashSet<Integer>. Because sets ignore duplicates by definition, the final size of the set is the count of distinct values.

Here are the steps:

1. Create an empty HashSet<Integer> called seen.
2. Iterate through every element value in the input array.
3. Call seen.add(value). The set silently ignores the call if the value is already present.
4. After the loop ends, read seen.size(); that is the number of distinct values.
5. Return the size as the final answer.

Java Program to Count Distinct Elements in an Array

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

import java.util.HashSet;
import java.util.Set;

public class CountDistinctElements {

    public static int countDistinct(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        for (int value : arr) {
            seen.add(value);
        }
        return seen.size();
    }

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

        System.out.println("Array length: " + arr.length);
        System.out.println("Distinct count: " + distinct);
    }
}

Explanation of the Program

• The method countDistinct takes an int[] and returns the number of distinct values it contains.
• A HashSet<Integer> named seen holds every distinct value found so far. Because HashSet is backed by a hash table, each add and lookup runs in amortized constant time.
• The enhanced for loop reads every element exactly once; the autoboxing from int to Integer happens automatically when the value is handed to seen.add.
• seen.add(value) returns true if the value was newly inserted and false if it was already present, but we do not need that return value because we only care about the final set size.
• The main method prints both the array length and the distinct count side by side so you can confirm the two numbers really are different for arrays that contain duplicates.

Step-by-Step Trace

Let us trace the algorithm on a small input that mixes new values and duplicates. Consider arr = {3, 1, 3, 5, 1, 7}; seen starts empty.

At the end of iteration i, seen holds exactly the distinct values from arr[0..i]. The duplicate visits in iterations 3 and 5 do not change the set, which is why the final seen.size() is 4 even though the array has six elements. That invariant is what makes the single pass correct.

Examples

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

Example 1: Mixed Values with Duplicates

int[] arr = {5, 3, 5, 1, 3, 8, 1};
int distinct = countDistinct(arr);

System.out.println("Distinct count: " + distinct);
// Output: Distinct count: 4

The array has seven elements but only four distinct values: 5, 3, 1, and 8. The duplicate occurrences of 5, 3, and 1 are silently absorbed by the set.

Example 2: All Elements Distinct

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

System.out.println("Distinct count: " + distinct);
// Output: Distinct count: 5

Every value is unique, so the distinct count equals the array length. This is the worst case for memory usage because the set has to grow to n entries.

Example 3: All Elements Identical

int[] arr = {7, 7, 7, 7, 7};
int distinct = countDistinct(arr);

System.out.println("Distinct count: " + distinct);
// Output: Distinct count: 1

Every value is the same, so the set never grows past a single entry regardless of the array length. This is the best case for memory and a useful sanity check that the counting logic is not confusing length with distinctness.

Common Mistakes to Avoid

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

• Returning arr.length by accident – a stray early return or a copy-paste bug that returns the array length looks correct for all-distinct inputs but silently overcounts whenever duplicates exist. Always return seen.size().
• Using an int[] boolean marker without range check – some learners replace the set with a boolean marker array indexed by value; this crashes with ArrayIndexOutOfBoundsException for negative or very large values. Use a HashSet unless the value range is small and known.
• Nested loop with == comparison – an O(n^2) double loop that counts a value as new only when no later index equals it is both slow and wrong when the same value appears three or more times; the middle copies are counted again. Use the single-pass set instead.
• Forgetting to handle a null array – calling arr.length on null throws NullPointerException. Decide up front whether you treat null as an error or as zero distinct values, then write the guard clause explicitly.
• Confusing distinct count with unique count – some learners count only values that appear exactly once (unique), not values that appear at least once (distinct). Re-read the problem statement and match HashSet behavior to the required definition.

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: Each of the n elements is inserted into the HashSet in amortized O(1), so the total running time is O(n).
2. Space complexity: In the worst case every element is distinct, so the set stores all n values, giving O(n) extra space. For an array of all duplicates the set only holds one entry.
3. Autoboxing cost: Each int gets boxed to an Integer object before being added to the set. For very hot code paths, this allocation pressure matters; a primitive-friendly set like Eclipse Collections’ IntHashSet avoids it.
4. Why Integer.MIN_VALUE matters: Any array-indexed marker approach needs to shift the index to avoid negative values; a HashSet handles the full int range without any special case.
5. Alternative with sorting: Sorting the array in O(n log n) and counting index transitions where arr[i] != arr[i - 1] gives the same answer with O(1) extra space but mutates the input and runs slower.

Interview Follow-up Questions

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

• What if the array is already sorted? – skip the set entirely and count index transitions where arr[i] != arr[i - 1], which runs in O(n) time and O(1) extra space.
• What if you need the distinct values themselves, not just the count? – return the HashSet directly, or copy it into an int[] if the caller insists on a primitive array; the work is the same, only the return type changes.
• What if the input is a stream of unknown length? – keep the same HashSet and update it as each value arrives; the final size is read when the stream ends, so there is no need to know the length up front.
• How would you count distinct elements across billions of entries that will not fit in memory? – use a probabilistic sketch such as HyperLogLog; it trades a small, bounded error for roughly constant memory regardless of the input size.
• What if you must do this without any extra data structure? – sort the array in place in O(n log n), then scan once and count the positions where consecutive elements differ; this keeps the extra space at O(1) but mutates the input.

Conclusion

In this guide, we walked through counting distinct elements in a Java array using a HashSet. The countDistinct method scans the array in a single pass, inserts every value into the set, and returns the final set size. 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 return the distinct values themselves, swap HashSet for a sorted alternative, or layer the counting on top of a stream so it handles inputs whose length you do not know in advance. Happy coding!

You can learn more about Array techniques: Arrays