Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Element Frequency Count

EASYProblemSolveExternal Links

Description

Given an array of positive integers that may contain duplicate values, your task is to determine how many times each distinct element appears in the array.

Return the result as a list of pairs, where each pair contains a distinct element and its frequency (count of occurrences). The pairs should preserve the order in which distinct elements first appear in the input array.

This is one of the most fundamental problems in programming — frequency counting is a building block for countless algorithms including finding majority elements, detecting duplicates, grouping anagrams, and much more.

Examples

Example 1

Input: arr = [1, 2, 2, 3, 3, 5]

Output: [[1, 1], [2, 2], [3, 2], [5, 1]]

Explanation: Element 1 appears once, element 2 appears twice, element 3 appears twice, and element 5 appears once. Each distinct element is paired with its count.

Example 2

Input: arr = [1, 5, 6, 7, 7]

Output: [[1, 1], [5, 1], [6, 1], [7, 2]]

Explanation: Elements 1, 5, and 6 each appear once. Element 7 appears twice. The output lists each distinct element alongside its occurrence count.

Example 3

Input: arr = [4, 4, 4, 4]

Output: [[4, 4]]

Explanation: There is only one distinct element (4) and it appears four times. This is an edge case where all elements are the same.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most natural approach is to pick each element one by one and count how many times it appears by scanning the entire array. To avoid counting the same element multiple times, we keep a visited array that marks which positions we have already counted.

Imagine you are a teacher taking attendance from a list of names. You start with the first name, count how many times it appears in the entire list, then cross out every copy. You repeat this for the next un-crossed name until every name is accounted for.

For each element at position i:

  1. If it is already marked as visited, skip it — we already counted it.
  2. Otherwise, scan from position i+1 to the end, counting every match and marking those positions as visited.
  3. Record the element and its total count.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 2, 3, 3, 5]:

Step 1: Initialize visited = [false, false, false, false, false, false]. Start with i=0.

Step 2: i=0, arr[0]=1. Not visited. Scan forward: compare 1 with arr[1]=2 (no match), arr[2]=2 (no match), arr[3]=3 (no match), arr[4]=3 (no match), arr[5]=5 (no match). Count = 1. Record [1, 1].

Step 3: i=1, arr[1]=2. Not visited. Scan forward: compare 2 with arr[2]=2 (MATCH! mark visited[2]=true, count++), arr[3]=3 (no match), arr[4]=3 (no match), arr[5]=5 (no match). Count = 2. Record [2, 2].

Step 4: i=2, arr[2]=2. Already visited — skip.

Step 5: i=3, arr[3]=3. Not visited. Scan forward: compare 3 with arr[4]=3 (MATCH! mark visited[4]=true, count++), arr[5]=5 (no match). Count = 2. Record [3, 2].

Step 6: i=4, arr[4]=3. Already visited — skip.

Step 7: i=5, arr[5]=5. Not visited. No elements after it. Count = 1. Record [5, 1].

Result: [[1, 1], [2, 2], [3, 2], [5, 1]]

Brute Force — Nested Loop Frequency Counting — Watch how the outer pointer fixes on each unvisited element and the inner pointer scans the rest of the array to count matches, marking duplicates as visited.

Algorithm

  1. Create a boolean visited array of size n, initialized to all false
  2. For each index i from 0 to n-1:
    • If visited[i] is true, skip to next index
    • Otherwise, set count = 1
    • For each index j from i+1 to n-1:
      • If arr[j] == arr[i], increment count and mark visited[j] = true
    • Record the pair [arr[i], count]
  3. Return the list of pairs

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> countFreq(vector<int>& arr) {
        int n = arr.size();
        vector<bool> visited(n, false);
        vector<vector<int>> result;
        
        for (int i = 0; i < n; i++) {
            // Skip if this position was already counted
            if (visited[i]) continue;
            
            int count = 1;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] == arr[i]) {
                    visited[j] = true;
                    count++;
                }
            }
            result.push_back({arr[i], count});
        }
        return result;
    }
};
class Solution:
    def countFreq(self, arr):
        n = len(arr)
        visited = [False] * n
        result = []
        
        for i in range(n):
            # Skip if this position was already counted
            if visited[i]:
                continue
            
            count = 1
            for j in range(i + 1, n):
                if arr[j] == arr[i]:
                    visited[j] = True
                    count += 1
            
            result.append([arr[i], count])
        
        return result
import java.util.*;

class Solution {
    public List<int[]> countFreq(int[] arr) {
        int n = arr.length;
        boolean[] visited = new boolean[n];
        List<int[]> result = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            // Skip if this position was already counted
            if (visited[i]) continue;
            
            int count = 1;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] == arr[i]) {
                    visited[j] = true;
                    count++;
                }
            }
            result.add(new int[]{arr[i], count});
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each element at index i, we potentially scan all remaining elements from i+1 to n-1. In the worst case (all distinct elements), this results in n + (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons, which is O(n²).

Space Complexity: O(n)

We use a visited boolean array of size n to track which positions have already been counted. The result array also uses up to O(n) space in the worst case (all distinct elements).

Why This Approach Is Not Efficient

The brute force approach uses O(n²) time because for every distinct element, it scans the entire remaining array to count occurrences. With n up to 10^5, this means up to ~5×10^9 comparisons — far too slow for typical time limits.

The fundamental problem is that we're doing repeated linear searches. Each time we encounter a new element, we scan the entire array again to find its duplicates. We have no memory of what we've already seen.

There are two paths to improvement:

  1. Sorting — If we sort the array first, all duplicates become adjacent. We can then count them in a single linear pass. Sorting costs O(n log n), but the counting pass is O(n), giving us O(n log n) overall.
  2. Hashing — If we use a hash map, we can count each element in O(1) amortized time. A single pass through the array with a hash map gives us O(n) total time.

Better Approach - Sorting

Intuition

If we sort the array first, all identical elements cluster together. Once grouped, we just walk through the sorted array and count the length of each consecutive run of equal values.

Think of organizing a messy pile of colored marbles. Instead of counting each color by searching through the whole pile, you first sort them by color. Now all red marbles are together, all blue ones are together, etc. Counting becomes trivial — just count the length of each color group.

After sorting, we use a single pointer to walk through the array. For each position, we check how far the same value extends, record the count, and jump to the next distinct value.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 2, 3, 3, 5]:

Step 1: Sort the array. Already sorted: [1, 2, 2, 3, 3, 5].

Step 2: Start at i=0, arr[0]=1. Count consecutive 1s: arr[1]=2 ≠ 1, so count=1. Record [1, 1]. Jump to i=1.

Step 3: i=1, arr[1]=2. Count consecutive 2s: arr[2]=2 (match, count=2), arr[3]=3 ≠ 2. Count=2. Record [2, 2]. Jump to i=3.

Step 4: i=3, arr[3]=3. Count consecutive 3s: arr[4]=3 (match, count=2), arr[5]=5 ≠ 3. Count=2. Record [3, 2]. Jump to i=5.

Step 5: i=5, arr[5]=5. No more elements after. Count=1. Record [5, 1].

Result: [[1, 1], [2, 2], [3, 2], [5, 1]]

Sorting Approach — Count Consecutive Runs — After sorting, identical elements are adjacent. Watch a single pointer walk through the sorted array, counting the length of each consecutive group.

Algorithm

  1. Sort the array in ascending order
  2. Initialize an index i = 0
  3. While i < n:
    • Set count = 1
    • While i + count < n AND arr[i + count] == arr[i], increment count
    • Record [arr[i], count]
    • Advance i by count (jump past the entire group)
  4. Return the result list

Code

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

class Solution {
public:
    vector<vector<int>> countFreq(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        vector<vector<int>> result;
        
        int i = 0;
        while (i < n) {
            int count = 1;
            // Count consecutive equal elements
            while (i + count < n && arr[i + count] == arr[i]) {
                count++;
            }
            result.push_back({arr[i], count});
            i += count;  // Jump past this group
        }
        return result;
    }
};
class Solution:
    def countFreq(self, arr):
        arr.sort()
        n = len(arr)
        result = []
        
        i = 0
        while i < n:
            count = 1
            # Count consecutive equal elements
            while i + count < n and arr[i + count] == arr[i]:
                count += 1
            result.append([arr[i], count])
            i += count  # Jump past this group
        
        return result
import java.util.*;

class Solution {
    public List<int[]> countFreq(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        List<int[]> result = new ArrayList<>();
        
        int i = 0;
        while (i < n) {
            int count = 1;
            // Count consecutive equal elements
            while (i + count < n && arr[i + count] == arr[i]) {
                count++;
            }
            result.add(new int[]{arr[i], count});
            i += count;  // Jump past this group
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the array takes O(n log n). After sorting, the counting pass is O(n) because each element is visited exactly once. The total is dominated by sorting: O(n log n).

Space Complexity: O(1) extra (excluding output)

Sorting can be done in-place. The only extra space is for the output array. If we don't count the output, this approach uses O(1) additional space — better than the brute force which needed a visited array.

Note: Sorting modifies the original array. If preserving the original order is required, a copy must be made first, adding O(n) space.

Why This Approach Is Not Efficient

The sorting approach improves on brute force (O(n²) → O(n log n)), but it has two limitations:

  1. It modifies the input array. Sorting rearranges elements in place. If the caller needs the original order preserved, we'd need to make a copy first (adding O(n) space).

  2. O(n log n) is not the best possible. The problem can be solved in O(n) time. Since we only need to count occurrences — not maintain sorted order — the sorting step is unnecessary overhead.

The key insight: a hash map can count element occurrences in a single pass, achieving O(n) time. Each element is inserted into the map (or its count is incremented) in O(1) amortized time. No sorting needed.

Optimal Approach - Hash Map

Intuition

A hash map is essentially a lookup table that maps keys to values. For frequency counting, we use each array element as a key and its count as the value.

Think of it like a tally counter at a voting booth. Each candidate has a name tag on the counter. As each ballot comes in, you find the candidate's tag and click the counter once. At the end, you read off each candidate's total. Finding the right tag is instant (O(1) with a hash map), so counting n ballots takes O(n) total time.

We walk through the array once:

  • For each element, look it up in the hash map
  • If it exists, increment its count by 1
  • If it doesn't exist, insert it with count 1

After the single pass, the map contains every distinct element paired with its frequency.

Step-by-Step Explanation

Let's trace through with arr = [1, 2, 2, 3, 3, 5]:

Step 1: Initialize an empty hash map.

Step 2: Process arr[0]=1. Look up 1 in map → not found. Insert {1: 1}. Map: {1: 1}.

Step 3: Process arr[1]=2. Look up 2 in map → not found. Insert {2: 1}. Map: {1: 1, 2: 1}.

Step 4: Process arr[2]=2. Look up 2 in map → found with count 1. Increment to 2. Map: {1: 1, 2: 2}.

Step 5: Process arr[3]=3. Look up 3 in map → not found. Insert {3: 1}. Map: {1: 1, 2: 2, 3: 1}.

Step 6: Process arr[4]=3. Look up 3 in map → found with count 1. Increment to 2. Map: {1: 1, 2: 2, 3: 2}.

Step 7: Process arr[5]=5. Look up 5 in map → not found. Insert {5: 1}. Map: {1: 1, 2: 2, 3: 2, 5: 1}.

Step 8: Convert map to result: [[1, 1], [2, 2], [3, 2], [5, 1]].

Hash Map Frequency Counting — Single Pass — Watch how a single scan through the array builds a frequency map. Each element either creates a new entry or increments an existing count — all in O(1) time per operation.

Algorithm

  1. Create an empty hash map (element → count)
  2. For each element num in the array:
    • If num exists in the map, increment its count by 1
    • Otherwise, insert num with count 1
  3. Convert the hash map entries into a list of [element, count] pairs
  4. Return the result

Code

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

class Solution {
public:
    vector<vector<int>> countFreq(vector<int>& arr) {
        unordered_map<int, int> freq;
        vector<vector<int>> result;
        
        // Count frequencies in a single pass
        for (int num : arr) {
            freq[num]++;
        }
        
        // Build result from map
        for (auto& [element, count] : freq) {
            result.push_back({element, count});
        }
        
        return result;
    }
};
class Solution:
    def countFreq(self, arr):
        freq = {}
        
        # Count frequencies in a single pass
        for num in arr:
            if num in freq:
                freq[num] += 1
            else:
                freq[num] = 1
        
        # Build result from dictionary
        result = [[element, count] for element, count in freq.items()]
        return result
import java.util.*;

class Solution {
    public List<int[]> countFreq(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        List<int[]> result = new ArrayList<>();
        
        // Count frequencies in a single pass
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        // Build result from map
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            result.add(new int[]{entry.getKey(), entry.getValue()});
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once. Each hash map insertion or lookup takes O(1) amortized time. Building the result from the map is O(k) where k is the number of distinct elements (k ≤ n). Total: O(n).

Space Complexity: O(n)

In the worst case (all distinct elements), the hash map stores n key-value pairs. This is O(n) extra space. However, this is the same order of space as the output itself, so it's considered optimal for this problem.

Why this is optimal: We must read every element at least once to count it — that's Ω(n) lower bound on time. Our O(n) solution matches this lower bound. No algorithm can do better than O(n) for frequency counting.