3591. Check if Any Element Has Prime Frequency

Difficulty: Easy

Topics: Array, Hashing, Prime Numbers

Companies: Google, Amazon, Adobe

Problem Statement

Given an integer array nums, return true if the frequency of any element in the array is a prime number, otherwise return false.

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

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Example 1

Input: nums = [1,2,3,4,5,4]
Output: true
Explanation: 4 appears twice, and 2 is a prime number.

Example 2

Input: nums = [1,2,3,4,5]
Output: false
Explanation: All elements appear once, and 1 is not prime.

Example 3

Input: nums = [2,2,2,4,4]
Output: true
Explanation: 2 appears three times (prime), 4 appears twice (prime).

Problem Link: View on LeetCode ↗

Approach 1: Frequency Map with Prime Check

This approach counts element frequencies using a hash map, then checks if any frequency is prime.

Algorithm Steps

Create a frequency map to count occurrences of each element
For each frequency value:
- Check if it's a prime number
- Return true if any frequency is prime
Return false if no prime frequencies found

Frequency Map with Prime Check

class Solution {
public:
    bool isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    bool checkPrimeFrequency(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;
        
        for (auto& [num, count] : freq) {
            if (isPrime(count)) return true;
        }
        return false;
    }
};

class Solution {
    private boolean isPrime(int n) {
        if (n <= 1) return false;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    public boolean checkPrimeFrequency(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        for (int count : freq.values()) {
            if (isPrime(count)) return true;
        }
        return false;
    }
}

class Solution:
    def isPrime(self, n: int) -> bool:
        if n <= 1:
            return False
        for i in range(2, int(n**0.5) + 1):
            if n % i == 0:
                return False
        return True
    
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
            
        for count in freq.values():
            if self.isPrime(count):
                return True
        return False

Complexity: O(n + f√m) time, O(u) space
• n: array size
• u: unique elements
• m: max frequency
• f: number of unique frequencies

Approach 2: Frequency Array with Prime Precomputation

Optimized approach that uses a fixed-size frequency array and precomputed primes for the range 1-100.

Algorithm Steps

Precompute prime numbers up to maximum possible frequency (100)
Create frequency array (size 101 for values 0-100)
Count frequencies of each number
Check frequencies against precomputed primes

Frequency Array with Prime Precomputation

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        // Precompute primes up to 100 (max frequency)
        vector<bool> isPrime(101, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= 100; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= 100; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Count frequencies (values 0-100)
        vector<int> freq(101, 0);
        for (int num : nums) {
            freq[num]++;
        }
        
        // Check frequencies
        for (int count : freq) {
            if (count > 0 && isPrime[count]) {
                return true;
            }
        }
        return false;
    }
};

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        // Precompute primes up to 100
        boolean[] isPrime = new boolean[101];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= 100; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= 100; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Count frequencies
        int[] freq = new int[101];
        for (int num : nums) {
            if (num >= 0 && num <= 100) {
                freq[num]++;
            }
        }
        
        // Check frequencies
        for (int count : freq) {
            if (count > 0 && isPrime[count]) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        # Precompute primes up to 100
        is_prime = [True] * 101
        is_prime[0] = is_prime[1] = False
        for i in range(2, 101):
            if is_prime[i]:
                for j in range(i*i, 101, i):
                    is_prime[j] = False
        
        # Count frequencies
        freq = [0] * 101
        for num in nums:
            if 0 <= num <= 100:
                freq[num] += 1
        
        # Check frequencies
        for count in freq:
            if count > 0 and is_prime[count]:
                return True
        return False

Optimization: O(n) time with O(1) prime checks using Sieve of Eratosthenes

Approach 3: Set of Prime Frequencies

Uses predefined set of prime frequencies for constant-time lookups.

Algorithm Steps

Define a set of prime numbers in the possible frequency range (1-100)
Count frequencies using a hash map
Check if any frequency exists in the prime set

Set of Prime Frequencies

class Solution {
public:
    bool checkPrimeFrequency(vector<int>& nums) {
        // Predefined prime frequencies (2-97)
        unordered_set<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 
                                    41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
        
        unordered_map<int, int> freq;
        for (int num : nums) freq[num]++;
        
        for (auto& [num, count] : freq) {
            if (primes.find(count) != primes.end()) {
                return true;
            }
        }
        return false;
    }
};

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        // Predefined prime frequencies
        Set<Integer> primes = new HashSet<>(
            Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
                         47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
        );
        
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        
        for (int count : freq.values()) {
            if (primes.contains(count)) {
                return true;
            }
        }
        return false;
    }
}

class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        # Predefined prime frequencies
        primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
                  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
        
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
            
        for count in freq.values():
            if count in primes:
                return True
        return False

Efficiency: O(n) time with O(1) prime checks - fastest for small inputs

Approach Comparison

Approach	Time	Space	Best For
Frequency Map	O(n + f√m)	O(u)	General cases
Precomputation	O(n + log log 100)	O(100)	Large inputs
Prime Set	O(n)	O(25)	Small inputs

Recommendation: Precomputation approach (Approach 2) is most efficient for constraints

Edge Cases

1. Single element array

Input: [5] → Output: false (frequency=1, not prime)

2. All elements same

Input: [2,2,2] → Output: true (frequency=3, prime)

3. Frequency=1

Input: [1,2,3] → Output: false

4. Frequency=2

Input: [4,4,5,5] → Output: true

5. Large prime frequency

Input: Array with 97 duplicates → Output: true

Important: Remember 1 is not prime, 2 is the smallest prime

Frequently Asked Questions

Why is 1 not considered prime?

By definition, prime numbers must have exactly two distinct divisors. 1 has only one divisor (itself), so it's not prime.

How do we handle negative numbers?

Constraints specify nums[i] ≥ 0, so negatives aren't possible. For general solutions, use absolute values.

What's the largest possible frequency?

Since n ≤ 100, max frequency is 100 (if all elements are identical).

Can frequency be zero?

No, we only count frequencies of elements that appear in the array.

Why use Sieve of Eratosthenes?

It efficiently precomputes primes up to a limit (100 in this case) with O(n log log n) time complexity.

Is frequency case-sensitive?

The problem deals with integers, not characters, so case sensitivity doesn't apply.

How to optimize for memory?

Use Approach 3 (Prime Set) which only stores 25 prime numbers.

What if the array has duplicate values?

Duplicates increase frequency counts - exactly what we need to check for prime frequencies.

Can we use bit manipulation for primes?

Yes, but for n=100, boolean array is simpler and more readable.

Why not check primes during frequency count?

We need to complete counting to get accurate frequencies before checking.

How to handle very large arrays (n>100)?

Approach 2 scales well as sieve computation remains O(1) for fixed max frequency.

What's the time complexity of sieve method?

O(n log log n) for range n, but here n=100 → O(1) in practice.

Final Recommendation: The precomputation approach (Approach 2) provides the best balance of efficiency and readability for this problem's constraints.