☕ DSA Java Articles

Topics › Basics › Learn Basic Hashing

Counting Frequencies of Array Elements

Easy TUF ID 252 A2Z

Java source ↗ Edit this article ↗

Problem

Given an array of N integers, report how many times each distinct value occurs. Print each value together with its count, in the order in which the values first appear in the array.

The classic version of this problem (the one with an elegant O(1) extra-space answer) adds the constraint that every element lies in [1, N]. We handle the general case with hashing and then show that special-case trick, because it reappears in several “find the missing/duplicate number” problems.

Constraints: 1 ≤ N ≤ 10^5, values fit in a 32-bit signed integer. The methods return a Map<Integer, Integer> (value to count) whose iteration order is the order of first appearance, so the tests can compare both the counts and the order.

Example 1

arr = [10, 5, 10, 15, 10, 5]
answer = 10 -> 3, 5 -> 2, 15 -> 1     // 10 appears three times, 5 twice, 15 once

Example 2

arr = [2, 3, 2, 3, 5, 1, 4]
answer = 2 -> 2, 3 -> 2, 5 -> 1, 1 -> 1, 4 -> 1   // values are in [1, 7], the special case

Example 3

arr = [1, 1, 1, 1]
answer = 1 -> 4                       // a single distinct value

Approach 1: Brute force with a visited array

Intuition. For each element, scan the rest of the array and count copies. To avoid reporting the same value again when we reach its second copy, mark every copy as visited while counting; later, skip visited positions. The order of first appearance is preserved for free because the outer loop runs left to right.

Algorithm.

  1. Create visited[0..n-1], all false, and an empty ordered map.
  2. For each i not yet visited: set count = 1; for every j > i with arr[j] == arr[i], mark visited[j] and increment count.
  3. Record arr[i] -> count.
static Map<Integer, Integer> bruteForce(int[] arr) {
    int n = arr.length;
    boolean[] visited = new boolean[n];
    Map<Integer, Integer> freq = new LinkedHashMap<>();        // insertion order = order of first appearance
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;                               // already counted as a copy of an earlier element
        int count = 1;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] == arr[i]) {
                visited[j] = true;
                count++;
            }
        }
        freq.put(arr[i], count);
    }
    return freq;
}

Complexity. Time O(n^2) in the worst case (all elements distinct: every outer iteration scans the whole remainder). Space O(n) for the visited flags, plus the output.

Approach 2: Counting array

Intuition. If the values are non-negative and not too large, let the value be an index: count[v]++ for every element, then every count is available in one read. This is array hashing. A second pass over the original array, inserting each value into the result the first time it is encountered, restores the order of first appearance.

Algorithm.

  1. Find maxValue and allocate count[0..maxValue].
  2. For each v in arr, count[v]++.
  3. For each v in arr again: if v is not yet in the result, record v -> count[v].
static Map<Integer, Integer> countingArray(int[] arr) {
    int maxValue = 0;
    for (int v : arr) maxValue = Math.max(maxValue, v);
    int[] count = new int[maxValue + 1];
    for (int v : arr) count[v]++;                               // one pass to count
    Map<Integer, Integer> freq = new LinkedHashMap<>();
    for (int v : arr) {
        if (!freq.containsKey(v)) freq.put(v, count[v]);        // report each value once, at its first appearance
    }
    return freq;
}

Complexity. Time O(n + maxValue). Space O(maxValue) for the counting array. This is the fastest option when maxValue is at most around 10^6; it fails outright for negative values and wastes memory when values are large and sparse.

Approach 3: Hash map

Intuition. A HashMap gives the same “value in, count out” interface without reserving a slot for every possible value, so it handles negative, huge and sparse keys. merge(v, 1, Integer::sum) inserts 1 for a new key and adds 1 to an existing count. Using LinkedHashMap makes the iteration order equal to insertion order, which is exactly the order of first appearance, so no second pass is needed.

Algorithm.

  1. Create an empty LinkedHashMap.
  2. For each v in arr, freq.merge(v, 1, Integer::sum).
  3. Return the map.
static Map<Integer, Integer> hashMap(int[] arr) {
    Map<Integer, Integer> freq = new LinkedHashMap<>();
    for (int v : arr) freq.merge(v, 1, Integer::sum);           // absent -> 1, present -> old + 1
    return freq;
}

Dry run on arr = [10, 5, 10, 15, 10, 5]:

v action map
10 absent, insert 1 {10: 1}
5 absent, insert 1 {10: 1, 5: 1}
10 present, 1 + 1 {10: 2, 5: 1}
15 absent, insert 1 {10: 2, 5: 1, 15: 1}
10 present, 2 + 1 {10: 3, 5: 1, 15: 1}
5 present, 1 + 1 {10: 3, 5: 2, 15: 1}

Complexity. Time O(n) on average, since each merge is O(1) on average. Space O(d) for d distinct values. This is the general-purpose answer.

Approach 4: In place, when every value is in [1, N]

Intuition. If all values lie in [1, n], the array has exactly one slot per possible value, so the array can be its own counting table. The obstacle is that each slot already holds an element we still need to read. The trick is to store two numbers in one slot: keep the original (shifted to [0, n - 1]) in the low part and add n once for every occurrence of the slot’s value. Since the original is always less than n, slot % n recovers the original and slot / n recovers the count. No extra array is needed.

Algorithm.

  1. Subtract 1 from every element so values become indices in [0, n - 1].
  2. For each i, let v = arr[i] % n (the original shifted value at i, even if arr[i] has already been increased) and do arr[v] += n.
  3. The count of the original value x is arr[x - 1] / n. Report values in first-appearance order by walking the untouched input.
static Map<Integer, Integer> inPlace(int[] input) {
    int[] arr = input.clone();                                  // keep the caller's array intact
    int n = arr.length;
    for (int i = 0; i < n; i++) arr[i]--;                       // shift values to [0, n - 1] so they are valid indices
    for (int i = 0; i < n; i++) arr[arr[i] % n] += n;           // arr[i] % n is the original value here; add n at its slot
    Map<Integer, Integer> freq = new LinkedHashMap<>();
    for (int i = 0; i < n; i++) {
        int value = input[i];
        if (!freq.containsKey(value)) freq.put(value, arr[value - 1] / n);   // slot v - 1 holds n * count(v) + junk < n
    }
    return freq;
}

Dry run on arr = [2, 3, 2, 3, 5, 1, 4], n = 7. After the shift the array is [1, 2, 1, 2, 4, 0, 3]. Processing each index: i = 0 adds 7 to slot 1; i = 1 reads 9 % 7 = 2, adds 7 to slot 2; i = 2 reads 8 % 7 = 1, adds 7 to slot 1; i = 3 reads 2, adds 7 to slot 2; i = 4 adds 7 to slot 4; i = 5 adds 7 to slot 0; i = 6 adds 7 to slot 3. Final array: [8, 16, 15, 9, 11, 0, 3]. Counts: value 2 is 16 / 7 = 2, value 3 is 15 / 7 = 2, value 5 is 11 / 7 = 1, value 1 is 8 / 7 = 1, value 4 is 9 / 7 = 1, value 6 is 0 / 7 = 0 and value 7 is 3 / 7 = 0 (they are absent).

Complexity. Time O(n). Extra space O(1) (the clone and the result map exist only so the method is side-effect free and testable; the trick itself uses no additional memory).

Edge cases and pitfalls