Count Unique Frequencies — Problem Statement & Solution Guide

HashingEasyFrequency Map

TimeO(n)

SpaceO(k)

Problem Description

You are given an array of integers named nums. Your objective is to compute the total number of distinct occurrence counts (frequencies) present across all unique elements in the input array.

The frequency of an element is defined as the number of times it appears in nums. If multiple distinct elements share the same frequency, that frequency value is only counted once towards the final answer. Return an integer representing the total number of unique frequency values.

DSA Pattern Breakdown

"Count Unique Frequencies"

easy

WHY DOES IT MATTER?

Counting unique frequencies is a classic example of frequency analysis, a pattern that appears in duplicate detection, load‑balancing, and data compression. Mastering this pattern teaches you to separate "counting" from "uniqueness" using two complementary hash structures.

OPTIMIZATION CHALLENGE

The breakthrough is realizing that you never need to sort the frequencies; a hash set can deduplicate them on the fly, turning a potential O(n log n) sorting step into O(1) average‑case insertion.

REAL-WORLD CONNECTION

In a distributed logging system, each server emits log entries; you may want to know how many distinct request rates (hits per second) exist across servers. The per‑server hit count is analogous to element frequency, and the set of distinct rates mirrors the unique frequency count.

During an interview, build the element frequency map first, then immediately insert each count into a set—no second pass is required if you update the set after each increment.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The problem reduces to counting how many distinct frequencies appear among the elements of the input array. A naive solution would iterate over every possible pair of elements to compute frequencies, leading to O(n^2) time, which quickly becomes infeasible for large n (e.g., n>10^5). The optimal paradigm leverages hashing: first, a hash map (or dictionary) records the occurrence count of each unique value in O(n) time; second, a second hash set collects the distinct counts, also in O(n) time. This two‑pass hashing approach collapses the problem to linear time while using only linear extra space. The key insight is that we never need the ordering of elements—only the multiplicity—so a frequency map suffices, and the uniqueness of frequencies can be captured by a set, avoiding any sorting or nested loops.

Interview Questions on This Problem

Q1How would you modify the solution if you also needed to return the list of frequencies that appear more than once?

First build the frequency map as usual, then iterate over its values and use another hash map to count how many elements share each frequency. Finally, collect frequencies whose count > 1 into a list. This remains O(n) time and O(n) space.

Q2Can you solve the problem in O(n) time without using extra space proportional to the range of input values?

Yes. Use a hash map for element→count (O(k) where k is number of distinct elements) and a hash set for distinct counts. Both structures grow only with the number of distinct elements, not with the numeric range of the values.

Q3What would be the impact on time and space complexity if the input array is streamed and you cannot store it entirely?

You can maintain the element→count map incrementally as the stream arrives, still O(n) time overall. Space remains O(k) for distinct elements seen so far. If k can be huge, you might need approximate counting (e.g., Count‑Min Sketch), trading exactness for sub‑linear space.

Examples

Example 1

Input

nums = [4, 4, 4, 7, 7, 9]

Output

Explanation: The unique elements in the array have the following frequencies: element 4 appears 3 times, element 7 appears 2 times, and element 9 appears 1 time. The set of distinct frequency counts is {1, 2, 3}, which contains 3 unique values.

Example 2

Input

nums = [10, 10, 20, 20, 30, 30]

Output

Explanation: Each unique element (10, 20, and 30) appears exactly 2 times in the array. The set of distinct frequencies is {2}, which contains 1 unique value.

Example 3

Input

nums = [-5, -5, -5, -5, 0, 0, 12]

Output

Explanation: The frequency breakdown is: -5 appears 4 times, 0 appears 2 times, and 12 appears 1 time. The set of unique frequency counts is {1, 2, 4}, giving a count of 3.

Example 4

Input

nums = [100]

Output

Explanation: The single element 100 has a frequency of 1. The set of distinct frequencies is {1}, so the count is 1.

Constraints

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Optimal Approach & Strategy

Use a hash map to count each element in O(n) then a hash set to collect distinct counts, also O(n).

Brute Force Approach

Count frequencies by scanning the array for each distinct element, leading to O(n^2) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function countUniqueFrequencies(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    // Step 1: Count the frequency of each element
    const freqMap = new Map();
    for (const num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    
    // Step 2: Collect unique frequencies
    const uniqueFreqs = new Set();
    for (const freq of freqMap.values()) {
        uniqueFreqs.add(freq);
    }
    
    // Step 3: Return the count of unique frequencies
    return uniqueFreqs.size;
}

// Standard I/O boilerplate for testing
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
});

rl.on('close', () => {
    if (lines.length >= 2) {
        const n = parseInt(lines[0]);
        const nums = lines[1].split(' ').map(Number);
        console.log(countUniqueFrequencies(nums));
    }
});

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int countUniqueFrequencies(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    
    // Step 1: Count the frequency of each element
    unordered_map<int, int> freqMap;
    for (int num : nums) {
        freqMap[num]++;
    }
    
    // Step 2: Collect unique frequencies
    unordered_set<int> uniqueFreqs;
    for (const auto& pair : freqMap) {
        uniqueFreqs.insert(pair.second);
    }
    
    // Step 3: Return the count of unique frequencies
    return uniqueFreqs.size();
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    cout << countUniqueFrequencies(nums) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static int countUniqueFrequencies(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // Step 1: Count the frequency of each element
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        
        // Step 2: Collect unique frequencies
        Set<Integer> uniqueFreqs = new HashSet<>(freqMap.values());
        
        // Step 3: Return the count of unique frequencies
        return uniqueFreqs.size();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        if (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = scanner.nextInt();
            }
            
            System.out.println(countUniqueFrequencies(nums));
        }
        
        scanner.close();
    }
}

def count_unique_frequencies(nums):
    if not nums:
        return 0
    
    # Step 1: Count the frequency of each element
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    # Step 2: Collect unique frequencies
    unique_freqs = set(freq_map.values())
    
    # Step 3: Return the count of unique frequencies
    return len(unique_freqs)

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()
    
    if data:
        n = int(data[0])
        nums = list(map(int, data[1:n+1]))
        print(count_unique_frequencies(nums))

function countUniqueFrequencies(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    // Step 1: Count the frequency of each element
    const freqMap = new Map();
    for (const num of nums) {
        freqMap.set(num, (freqMap.get(num) || 0) + 1);
    }
    
    // Step 2: Collect unique frequencies
    const uniqueFreqs = new Set();
    for (const freq of freqMap.values()) {
        uniqueFreqs.add(freq);
    }
    
    // Step 3: Return the count of unique frequencies
    return uniqueFreqs.size;
}

// Standard I/O boilerplate for testing
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
});

rl.on('close', () => {
    if (lines.length >= 2) {
        const n = parseInt(lines[0]);
        const nums = lines[1].split(' ').map(Number);
        console.log(countUniqueFrequencies(nums));
    }
});

Asked in Top Tech Interviews

Accenture

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Count Unique Frequencies Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Count Unique Frequencies — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor