Check if Any Element Has Prime Frequency - Solution & Explanation

Problem Overview: You are given an integer array and need to determine whether any value appears a prime number of times. The task reduces to counting element frequencies and checking if at least one frequency is a prime number.

The key observation: the array values themselves do not matter. Only the frequency of each unique element matters. Once you compute those counts, the problem becomes a simple prime number check.

Approach 1: Frequency Map + Prime Check (O(n + k√f) time, O(k) space)

Use a hash map to count how many times each element appears. Iterate through the array once and update a frequency table. After building the map, iterate through the frequency values and check whether any count is prime.

A number x is prime if it has no divisors between 2 and √x. For each frequency, run this check. The moment you find a prime count, return true. If none of the counts are prime, return false. Counting takes O(n) time, and each prime check costs O(√f) where f is the frequency value. Space complexity is O(k) where k is the number of unique elements.

This approach relies on standard frequency counting using a hash table and a basic primality test from number theory. It works well because the number of unique elements is usually much smaller than n.

Approach 2: Frequency Counting + Sieve Precomputation (O(n + m log log m) time, O(m) space)

If you expect many prime checks, you can precompute prime numbers using the Sieve of Eratosthenes. First count element frequencies using a map or array. Track the maximum frequency m. Then run a sieve up to m to mark all prime numbers.

After building the sieve, simply check whether any frequency value corresponds to a prime index in the sieve array. This converts repeated primality checks into constant-time lookups. The sieve step costs O(m log log m) time and O(m) space, where m is the maximum frequency.

This version can be useful when the dataset is large or when prime checks are frequent. The approach combines array traversal with efficient counting and prime preprocessing.

Recommended for interviews: The hash map counting with a direct prime check is the expected solution. It demonstrates clean use of frequency counting and a standard primality test while keeping the implementation short. A brute-force counting approach shows basic understanding, but the hash map + prime check method highlights stronger problem decomposition and is typically what interviewers want.