3591. Check if Any Element Has Prime Frequency Solution

Q: Is Check if Any Element Has Prime Frequency easy or hard?

This problem is typically classified as Easy because it combines two straightforward steps: frequency counting and a simple prime number check. The challenge lies mainly in recognizing that only the counts matter, not the element values.

Q: Check if Any Element Has Prime Frequency Python/Java solution

In Python, use collections.Counter or a dictionary to count elements, then run a helper function that checks divisibility up to √n. In Java, use HashMap to store counts and implement a small isPrime method. The same logic translates directly to C++, Go, and TypeScript.

The problem

You are given an integer array nums.

Return true if the frequency of any element of the array is prime, otherwise, return false.

The frequency of an element x is the number of times it occurs in the array.

A prime number is a natural number greater than 1 with only two factors, 1 and itself.

Example 1:

Input: nums = [1,2,3,4,5,4]

Output: true

Explanation:

4 has a frequency of two, which is a prime number.

Example 2:

Input: nums = [1,2,3,4,5]

Output: false

Explanation:

All elements have a frequency of one.

Example 3:

Input: nums = [2,2,2,4,4]

Output: true

Explanation:

Both 2 and 4 have a prime frequency.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

Approach overview

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.

Solution

We use a hash table cnt to count the frequency of each element. Then, we iterate through the values in cnt and check if any of them is a prime number. If there is a prime, return true; otherwise, return false.

The time complexity is O(n times \sqrt{M}), and the space complexity is O(n), where n is the length of the array nums and M is the maximum

Python

class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            return all(x % i for i in range(2, int(sqrt(x)) + 1))

        cnt = Counter(nums)
        return any(is_prime(x) for x in cnt.values())

Java

import java.util.*;

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }

        for (int x : cnt.values()) {
            if (isPrime(x)) {
                return true;
            }
        }
        return false;
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

C++

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) {
            ++cnt[x];
        }

        for (auto& [_, x] : cnt) {
            if (isPrime(x)) {
                return true;
            }
        }
        return false;
    }

private:
    bool isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i <= x / i; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
};

TypeScript

function checkPrimeFrequency(nums: number[]): boolean {
    const cnt: Record<number, number> = {};
    for (const x of nums) {
        cnt[x] = (cnt[x] || 0) + 1;
    }
    for (const x of Object.values(cnt)) {
        if (isPrime(x)) {
            return true;
        }
    }
    return false;
}

function isPrime(x: number): boolean {
    if (x < 2) {
        return false;
    }
    for (let i = 2; i * i <= x; i++) {
        if (x % i === 0) {
            return false;
        }
    }
    return true;
}

func checkPrimeFrequency(nums []int) bool {
	cnt := make(map[int]int)
	for _, x := range nums {
		cnt[x]++
	}
	for _, x := range cnt {
		if isPrime(x) {
			return true
		}
	}
	return false
}

func isPrime(x int) bool {
	if x < 2 {
		return false
	}
	for i := 2; i*i <= x; i++ {
		if x%i == 0 {
			return false
		}
	}
	return true
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Frequency Map + Prime Check	O(n + k√f)	O(k)	General case; simplest and most common interview solution
Frequency Counting + Sieve of Eratosthenes	O(n + m log log m)	O(m)	When many prime checks are required or maximum frequency is known

Frequently asked questions

Is Check if Any Element Has Prime Frequency easy or hard?

This problem is typically classified as Easy because it combines two straightforward steps: frequency counting and a simple prime number check. The challenge lies mainly in recognizing that only the counts matter, not the element values.

Check if Any Element Has Prime Frequency Python/Java solution

In Python, use collections.Counter or a dictionary to count elements, then run a helper function that checks divisibility up to √n. In Java, use HashMap<Integer, Integer> to store counts and implement a small isPrime method. The same logic translates directly to C++, Go, and TypeScript.

How to solve Check if Any Element Has Prime Frequency in O(n)?

Traverse the array once to build a frequency map using a hash table. After counting, iterate over the frequency values and check whether any count is prime using a divisor check up to √count. The counting step dominates the runtime, making the algorithm effectively linear for typical inputs.

What is the best approach for Check if Any Element Has Prime Frequency?

The most efficient approach is counting element frequencies with a hash map and then checking whether any frequency is prime. Counting takes O(n) time, and each primality check costs O(√f) where f is the frequency. Space complexity is O(k) for k distinct elements. This is the standard solution expected in interviews.

Is Check if Any Element Has Prime Frequency asked at Google/Amazon/Meta?

Problems involving frequency counting and prime checks commonly appear in coding interviews at companies like Amazon and Google. They test familiarity with hash tables, basic number theory, and the ability to separate counting logic from validation logic.

What data structure is used in Check if Any Element Has Prime Frequency?

A hash table (hash map) is the primary data structure used to count occurrences of each element in the array. After building the map, simple arithmetic checks determine whether any frequency value is prime.

What is the time complexity of Check if Any Element Has Prime Frequency?

Building the frequency map requires O(n) time where n is the array length. Each frequency is then tested for primality using a square root check, which takes O(√f). Overall complexity is O(n + k√f), where k is the number of unique elements.

Check if Any Element Has Prime Frequency solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Check if Any Element Has Prime Frequency solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems