Count Occurrences of Each Element in an Array

Title: Count Occurrences of Each Element in an Array

Counting how many times each distinct value appears in an array is a bread-and-butter problem that opens the door to frequency maps, histograms, and mode-style questions. In this guide, we will explore a clean Java solution that uses a HashMap, walk through the logic line by line, trace it on a small input, and finish with concrete examples, common pitfalls, and interview-style follow-up questions.

Understanding the Problem

Given an integer array, we want to produce the count of occurrences for every distinct value it contains. The result is typically returned as a map from value to count, where each distinct value appears as a key exactly once and the associated value is how many times that key appeared in the input.

For example, the array {4, 2, 7, 2, 4, 9, 7, 1, 4} has 4 appearing 3 times, 2 and 7 appearing 2 times each, and 9 and 1 appearing once each. The expected result is the map {4=3, 2=2, 7=2, 9=1, 1=1}.

This problem is a good excuse to practice the frequency map pattern. A HashMap<Integer, Integer> gives us amortized constant-time lookups and updates, which is exactly what we need to bump a counter for every element we read.

Approach to Count Occurrences of Each Element

We will scan the array once and keep a running tally of how many times each value has appeared using a HashMap<Integer, Integer>. Java 8 added Map.merge, which makes the increment logic a single clean line.

Here are the steps:

1. Create an empty HashMap<Integer, Integer> called counts.
2. Iterate through every element value in the input array.
3. Call counts.merge(value, 1, Integer::sum). If value is not yet a key, this inserts it with count 1; otherwise it adds 1 to the existing count.
4. After the loop ends, counts maps every distinct value to its total occurrence count.
5. Return counts, or iterate over its entries to print each value and its frequency.

Java Program to Count Occurrences of Each Element in an Array

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

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

public class CountOccurrences {

    public static Map<Integer, Integer> countOccurrences(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int value : arr) {
            counts.merge(value, 1, Integer::sum);
        }
        return counts;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 7, 2, 4, 9, 7, 1, 4};
        Map<Integer, Integer> counts = countOccurrences(arr);

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int value = entry.getKey();
            int count = entry.getValue();
            System.out.println("Element " + value + " occurs " + count + " time(s)");
        }
    }
}

Explanation of the Program

• The method countOccurrences takes an int[] and returns a Map<Integer, Integer> whose entries describe how often each distinct value appears.
• A HashMap<Integer, Integer> named counts stores the frequencies. The HashMap is backed by a hash table, so each merge call 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 counts.merge.
• counts.merge(value, 1, Integer::sum) is the heart of the algorithm. If the key is absent, it writes the value 1; if the key is present, it replaces the current count with currentCount + 1. One line replaces the familiar get-then-put idiom and avoids the subtle null check it needs.
• The main method iterates over the map’s entrySet and prints each value next to its count, so you can see the frequency breakdown at a glance.

Step-by-Step Trace

Let us trace the algorithm on a small input that mixes new values and repeats. Consider arr = {6, 2, 6, 1, 2, 8}; counts starts empty.

At the end of iteration i, counts holds the frequency of each distinct value seen in arr[0..i]. Notice how iterations 3 and 5 do not add new keys; they only bump the counter for an existing key. 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};
Map<Integer, Integer> counts = countOccurrences(arr);

System.out.println(counts);
// Output: {1=2, 3=2, 5=2, 8=1}

The array has seven elements and four distinct values. Each of 1, 3, and 5 appears twice, while 8 appears once. The map therefore totals 2 + 2 + 2 + 1 = 7, which matches the array length and is a cheap sanity check.

Example 2: All Elements Distinct

int[] arr = {10, 20, 30, 40, 50};
Map<Integer, Integer> counts = countOccurrences(arr);

System.out.println(counts);
// Output: {50=1, 20=1, 40=1, 10=1, 30=1}

Every value is unique, so every key in the map has a count of 1. This is the worst case for memory because the map has to grow to n entries. Note that HashMap does not preserve insertion order, so the printed order can differ from the array order; use LinkedHashMap if you need stable ordering.

Example 3: All Elements Identical

int[] arr = {7, 7, 7, 7};
Map<Integer, Integer> counts = countOccurrences(arr);

System.out.println(counts);
// Output: {7=4}

Every value is the same, so the map has a single entry whose count equals the array length. This is the best case for memory and a useful sanity check that the counting logic is not accidentally confusing length with distinctness.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing a frequency count:

• get-then-put without a null check – calling counts.put(value, counts.get(value) + 1) throws NullPointerException the first time a new key is seen because get returns null and auto-unboxing fails. Use merge or getOrDefault(value, 0) + 1.
• Using an int[] frequency array without a range check – some learners replace the map with a counter array indexed by value; this crashes with ArrayIndexOutOfBoundsException for negative or very large values. Use a HashMap unless the value range is small and known.
• Nested loop with == comparison – an O(n^2) double loop that counts occurrences of each element from scratch overcounts every value by its own multiplicity. Prefer the single-pass map.
• Relying on HashMap iteration order – printing the map and expecting insertion order fails because HashMap ordering is unspecified. Switch to LinkedHashMap to preserve first-seen order, or sort the entries explicitly.
• Forgetting to handle a null array – calling arr.length on null throws NullPointerException. Decide up front whether null means an error or an empty map, 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: Each of the n elements triggers one merge call in amortized O(1), so the total running time is O(n).
2. Space complexity: Let k be the number of distinct values. The map holds k entries, so the extra space is O(k), which is O(n) in the worst case and O(1) when every element is identical.
3. Autoboxing cost: Each int gets boxed to an Integer before entering the map, and each count is a boxed Integer too. For very hot code paths, a primitive-friendly map such as Eclipse Collections’ IntIntHashMap avoids both allocations.
4. Why Integer.MIN_VALUE matters: Any array-indexed frequency approach needs to shift the index to avoid negative values; 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 of equal consecutive elements gives the same answer with O(1) extra space but mutates the input and runs slower than the map approach.
6. Alternative with streams: Arrays.stream(arr).boxed().collect(Collectors.groupingBy(x -> x, Collectors.counting())) produces a Map<Integer, Long> in one expression, trading a little readability for extra allocation.

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 map and count runs of equal consecutive elements in a single pass, which runs in O(n) time and O(1) extra space.
• What if you need the counts in order of first appearance? – swap HashMap for LinkedHashMap; the API is identical, but iteration order follows insertion order.
• What if you only need the element with the maximum frequency (the mode)? – build the same map, then walk its entries once and keep the entry with the largest value; total time stays O(n).
• What if the input is a stream of unknown length? – keep the same HashMap and update it as each value arrives; the final counts are read when the stream ends, so there is no need to know the length up front.
• How would you count frequencies across billions of entries that will not fit in memory? – shard the input by hash of the key across many workers, let each worker build a partial map in parallel, then merge the partial maps by summing counts per key.

Conclusion

In this guide, we walked through counting the occurrences of each element in a Java array using a HashMap. The countOccurrences method scans the array in a single pass, calls merge for every element, and returns a map from value to count. The running time is O(n) and the extra space is O(k) where k is the number of distinct values.

Try adapting the code to return the counts in insertion order with LinkedHashMap, to pick out the mode in a single additional pass, or to 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