Element Occurrence Counter — Problem Statement & Solution Guide

MathEasyFrequency Count

TimeO(n)

SpaceO(k)

Problem Description

You are given an integer array nums. Determine which distinct values appear more than 47 times in the array and return them as a list. The order of the returned values does not matter, but each qualifying value must appear exactly once in the output. If no element satisfies the frequency condition, return an empty list.

Input: an array of integers nums.

Output: a list containing every integer that occurs strictly more than 47 times in nums.

Your algorithm should run in linear time relative to the size of nums and use only O(k) additional memory, where k is the number of distinct values in the array.

DSA Pattern Breakdown

"Element Occurrence Counter"

easy

WHY DOES IT MATTER?

Frequency counting is a foundational pattern for detecting anomalies, generating statistics, and implementing cache eviction policies; mastering it equips engineers to handle large‑scale data streams efficiently.

OPTIMIZATION CHALLENGE

The key insight is recognizing that you only need a single pass with constant‑time updates; storing full pairwise comparisons is unnecessary, and a compact hash table suffices to track counts for all distinct values.

REAL-WORLD CONNECTION

Think of a distributed logging system where each server reports error codes; the central aggregator must quickly identify error codes that exceed a fixed alert threshold (e.g., 47 occurrences) to trigger alarms, mirroring the exact logic of this problem.

During an interview, first state the O(n) hash‑map plan, then discuss edge cases (empty array, negative numbers) and optionally mention the sorted‑array O(1) space alternative to show depth of understanding.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The core of this problem is frequency counting, a classic use‑case for hash‑based maps. By scanning the array once and incrementing a counter for each encountered value, we can determine in linear time which elements exceed the fixed threshold of 47 occurrences. A naive double‑loop that compares each element with every other would run in O(n²) time and quickly become infeasible for large inputs (n can be up to 10⁵ or more in typical interview constraints). The optimal paradigm leverages constant‑time average look‑ups of a hash table (or dictionary) to maintain a compact frequency table, allowing us to isolate qualifying values in a single pass while keeping auxiliary space proportional only to the number of distinct elements.

Because the threshold is a constant (47) and not a dynamic fraction of n, we cannot apply majority‑vote algorithms like Boyer‑Moore; instead, we must retain exact counts for all distinct numbers. This subtlety forces the solution to balance time efficiency with modest extra space, a pattern that recurs in many real‑world analytics pipelines where fixed‑frequency alerts are required.

Interview Questions on This Problem

Q1How would you modify the solution if the threshold were not a constant but a percentage of the array length (e.g., elements appearing more than 10% of the time)?

Compute the threshold as Math.floor(0.10 * n) after reading the array length, then apply the same hash‑map counting logic; the only change is that the threshold is derived at runtime, but the algorithmic complexity remains O(n) time and O(k) space.

Q2Can you solve the problem using O(1) extra space if the input array is sorted in place?

Yes. A single pass with two pointers can count consecutive identical values; when a count exceeds 47, add the value to the result list. This eliminates the hash map, achieving O(1) auxiliary space but requires the array to be sorted beforehand, which adds O(n log n) time if sorting is needed.

Q3Why might a hash map implementation cause performance degradation in a language with poor hash function quality, and how would you mitigate it?

Poor hash functions can lead to many collisions, degrading average O(1) operations to O(n) in the worst case. Mitigation strategies include using a language‑provided robust map (e.g., Java's HashMap), reserving capacity upfront to avoid rehashing, or switching to a balanced BST (TreeMap) which guarantees O(log n) operations regardless of hash quality.

Examples

Example 1

Input

[5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,2,3,7,9]

Output

[5]

Explanation: The array length is 56. The value 5 appears 50 times, which is greater than 47. All other numbers appear fewer than 48 times. Hence the result contains only 5.

Example 2

Input

[7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3]

Output

[ -3, 7 ]

Explanation: The array contains 100 elements. The value 7 occurs 60 times and -3 occurs 48 times; both exceed the threshold of 47. No other value meets the condition, so the output list includes 7 and -3 (order is irrelevant).

Example 3

Input

[1,2,3,4,5,6,7,8,9,10]

Output

[]

Explanation: Each number appears exactly once, which is far below the required 48 occurrences. Therefore the result is an empty list.

Constraints

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
The frequency threshold is fixed at 47 (i.e., strictly more than 47 occurrences).
The algorithm should run in O(n) time and use O(k) auxiliary space, where k is the number of distinct values.

Optimal Approach & Strategy

The optimal solution uses a hash map to tally frequencies in one pass, then extracts keys with counts greater than 47. This runs in O(n) time and uses O(k) extra space, where k is the number of distinct numbers.

Brute Force Approach

A naive solution would compare each element with every other element to count occurrences, resulting in O(n²) time. It also risks adding the same qualifying element multiple times to the output.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function elementOccurrenceCounter(arr) {
    const countMap = new Map();
    for (let num of arr) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    const result = [];
    for (let [num, count] of countMap) {
        if (count > 47) {
            result.push(num);
        }
    }
    return result;
}

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

std::vector<int> elementOccurrenceCounter(std::vector<int>& arr) {
    std::unordered_map<int, int> countMap;
    for (int num : arr) {
        if(countMap.find(num) != countMap.end()){
            countMap[num]++;
        } else {
            countMap[num] = 1;
        }
    }
    std::vector<int> result;
    for (auto& pair : countMap) {
        if (pair.second > 47) {
            result.push_back(pair.first);
        }
    }
    return result;
}

int main() {
    std::vector<int> arr = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    std::vector<int> result = elementOccurrenceCounter(arr);
    std::cout << "[";
    for(int i = 0; i < result.size(); i++) {
        std::cout << result[i];
        if(i != result.size() - 1) {
            std::cout << ", ";
        }
    }
    std::cout << "]";
    return 0;
}

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

public class Solution {
    public int[] elementOccurrenceCounter(int[] arr) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int num : arr) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            if (entry.getValue() > 47) {
                result.add(entry.getKey>();
            }
        }
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        int[] res = solution.elementOccurrenceCounter(arr);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }
    }
}

def element_occurrence_counter(arr):
    count_map = {}
    for num in arr:
        count_map[num] = count_map.get(num, 0) + 1
    result = [num for num, count in count_map.items() if count > 47]
    return result

function elementOccurrenceCounter(arr) {
    const countMap = new Map();
    for (let num of arr) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    const result = [];
    for (let [num, count] of countMap) {
        if (count > 47) {
            result.push(num);
        }
    }
    return result;
}

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.

Element Occurrence Counter Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Constraints

More Math

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Element Occurrence Counter — 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

Solve in Interative Editor