Frequency of Each Array Element: 3 Approaches

Counting how often each element appears in an array is a foundational problem, with three approaches ranging from the O(n²) nested loop to the O(n) hash map. Each trades different amounts of time against space, and placement interviewers at Tier-2 and Tier-3 college drives routinely ask which you’d choose and why.

The Problem and a Worked Example

Given an integer array, return a mapping from each element to its count in that array.

• Input: [1, 2, 1, 3, 2, 1]
• Expected output: element 1 appears 3 times, element 2 appears 2 times, element 3 appears 1 time.

Manual trace using the hash map approach (element by element):

• Process 1: frequency dict is {1: 1}
• Process 2: frequency dict is {1: 1, 2: 1}
• Process 1 again: frequency dict is {1: 2, 2: 1}
• Process 3: frequency dict is {1: 2, 2: 1, 3: 1}
• Process 2 again: frequency dict is {1: 2, 2: 2, 3: 1}
• Process 1 again: frequency dict is {1: 3, 2: 2, 3: 1}

Final result: {1: 3, 2: 2, 3: 1}. All three approaches produce this same output; only the path to get there differs.

Approach 1: Nested Loop

The nested loop approach uses two passes. The outer loop picks an element. The inner loop scans the rest of the array counting matches. A visited boolean array prevents double-counting elements already processed.

Time complexity: O(n²). Space complexity: O(n) for the visited array.

Python

def frequency_nested(arr):
    n = len(arr)
    visited = [False] * n
    result = {}
    for i in range(n):
        if visited[i]:
            continue
        count = 1
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                count += 1
                visited[j] = True
        result[arr[i]] = count
    return result

# Example
arr = [1, 2, 1, 3, 2, 1]
print(frequency_nested(arr))
# {1: 3, 2: 2, 3: 1}

C++

#include <iostream>
#include <vector>
using namespace std;

void frequencyNested(const vector<int>& arr) {
    int n = arr.size();
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        int count = 1;
        for (int j = i + 1; j < n; j++) {
            if (arr[i] == arr[j]) {
                count++;
                visited[j] = true;
            }
        }
        cout << arr[i] << " -> " << count << "\n";
    }
}

int main() {
    vector<int> arr = {1, 2, 1, 3, 2, 1};
    frequencyNested(arr);
    return 0;
}
// Output:
// 1 -> 3
// 2 -> 2
// 3 -> 1

This approach works correctly but becomes slow on large inputs:

• At n = 10,000 elements, the nested loop performs up to 100,000,000 comparisons.

Approach 2: Sort Then Linear Sweep

Sorting brings identical elements together. One pass over the sorted array then counts adjacent groups. The inner loop is eliminated.

Time complexity: O(n log n) dominated by the sort. Space complexity: O(n) for the sorted copy (or O(log n) if sorting in place with a language’s built-in introsort).

Python

def frequency_sorted(arr):
    if not arr:
        return {}
    sorted_arr = sorted(arr)
    result = {}
    count = 1
    for i in range(1, len(sorted_arr)):
        if sorted_arr[i] == sorted_arr[i - 1]:
            count += 1
        else:
            result[sorted_arr[i - 1]] = count
            count = 1
    result[sorted_arr[-1]] = count
    return result

# Example
arr = [1, 2, 1, 3, 2, 1]
print(frequency_sorted(arr))
# {1: 3, 2: 2, 3: 1}

Trace on sorted [1, 1, 1, 2, 2, 3]:

• i=1: 1 == 1, count becomes 2
• i=2: 1 == 1, count becomes 3
• i=3: 2 != 1, store 1 -> 3, reset count to 1
• i=4: 2 == 2, count becomes 2
• i=5: 3 != 2, store 2 -> 2, reset count to 1
• After loop: store 3 -> 1

Result matches: {1: 3, 2: 2, 3: 1} ✓

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

void frequencySorted(vector<int> arr) {
    if (arr.empty()) return;
    sort(arr.begin(), arr.end());
    int count = 1;
    for (int i = 1; i < (int)arr.size(); i++) {
        if (arr[i] == arr[i - 1]) {
            count++;
        } else {
            cout << arr[i - 1] << " -> " << count << "\n";
            count = 1;
        }
    }
    cout << arr.back() << " -> " << count << "\n";
}

int main() {
    vector<int> arr = {1, 2, 1, 3, 2, 1};
    frequencySorted(arr);
    return 0;
}
// Output:
// 1 -> 3
// 2 -> 2
// 3 -> 1

The sorted approach is a good fit when the interviewer restricts extra hash space, or when the output needs to be in sorted key order already.

Approach 3: Hash Map

One pass through the array. For each element, increment its count in a dictionary. No sorting, no inner loop.

Time complexity: O(n). Space complexity: O(k) where k is the number of distinct elements (worst case O(n) when all elements are unique).

Python

The manual dict version makes the mechanism explicit:

def frequency_hashmap(arr):
    freq = {}
    for element in arr:
        freq[element] = freq.get(element, 0) + 1
    return freq

# Example
arr = [1, 2, 1, 3, 2, 1]
print(frequency_hashmap(arr))
# {1: 3, 2: 2, 3: 1}

Python’s standard library also provides Counter from collections, which wraps this pattern in a single call:

from collections import Counter

arr = [1, 2, 1, 3, 2, 1]
print(dict(Counter(arr)))
# {1: 3, 2: 2, 3: 1}

Counter handles the iteration and incrementing internally; the result is a dict subclass keyed by element with integer counts.

C++

C++ provides unordered_map (see cppreference), which offers O(1) amortized insertions and lookups. Unlike symmetric pairs in an array where you need to match key-value pairs, here you only accumulate a running count per key:

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

void frequencyHashMap(const vector<int>& arr) {
    unordered_map<int, int> freq;
    for (int x : arr) {
        freq[x]++;
    }
    for (const auto& entry : freq) {
        cout << entry.first << " -> " << entry.second << "\n";
    }
}

int main() {
    vector<int> arr = {1, 2, 1, 3, 2, 1};
    frequencyHashMap(arr);
    return 0;
}
// Output (order may vary):
// 1 -> 3
// 2 -> 2
// 3 -> 1

Note: unordered_map does not guarantee key order during iteration. If sorted output is required, iterate over a std::map<int, int> instead.

The hash map is the standard answer in placement interviews. If an interviewer asks “can you do better than O(n log n)?”, the hash map is the answer.

Edge Cases

Test these three scenarios before submitting:

• Empty array: [] — expected output is an empty dict. All three approaches return early or produce no results.
• All identical elements: [5, 5, 5, 5] — expected output: element 5 appears 4 times. The nested loop counts 4 on the first pass and marks the rest visited. The sorted sweep processes one group. The hash map increments the same key 4 times.
• All unique elements: [1, 2, 3, 4] — expected output: each element appears 1 time. The nested loop finds no matches after the anchor element. The sorted sweep emits a count of 1 at each element transition. The hash map inserts 4 distinct keys each with value 1.

For a walkthrough of how these edge case patterns apply to other array problems, the equilibrium index of an array uses similar boundary condition thinking.

Which Approach to Use

Approach	Time	Space	Use when
Nested loop	O(n²)	O(n)	Array is tiny (under 50 elements); no dictionary allowed by constraints
Sorted sweep	O(n log n)	O(n)	Output must be in sorted key order; extra hash space is restricted
Hash map	O(n)	O(n)	Default choice — any interview, any production code

The space cost of the hash map is the same order as the sorted copy, so there is no space advantage to the sorted approach in practice. The only trade-off worth noting is that unordered_map has O(n) worst-case time per operation under adversarial hash collisions, while std::map guarantees O(log n). This rarely matters in placement tests but can come up in system design rounds.

For a fuller treatment of O(n) space costs across different array algorithms, see the article on space complexity of algorithms.

The hash map compresses the frequency problem to a single pass because dictionary lookups run in O(1) amortized time. That same pattern (a dictionary keyed on tokens rather than integers) appears in most natural language preprocessing: token frequency, vocabulary dictionaries, n-gram counts. TinkerLLM (₹499) has Python notebooks where you can trace that path from integer array frequency counting to tokenizer vocabulary construction, without setting up a separate ML environment.