LeetCode 3591 - Check if Any Element Has Prime Frequency
This problem asks us to determine whether any number in an array appears a prime number of times. In other words, for each unique number in the input array nums, we calculate its frequency-the number of occurrences-and check if that frequency is a prime number.
Difficulty: 🟢 Easy
Topics: Array, Hash Table, Math, Counting, Number Theory
Solution
Problem Understanding
This problem asks us to determine whether any number in an array appears a prime number of times. In other words, for each unique number in the input array nums, we calculate its frequency-the number of occurrences-and check if that frequency is a prime number. If at least one element has a prime frequency, we return true; otherwise, we return false.
The input is an integer array nums where each element ranges from 0 to 100, and the array length ranges from 1 to 100. These constraints are small, meaning even a straightforward solution is feasible in terms of performance, but we can optimize using efficient counting and primality checking.
The problem guarantees all array elements are integers and the array is non-empty. Edge cases include arrays where every element is unique (frequencies are all 1), arrays where all elements are the same (frequency equals array length), and arrays where multiple elements have the same frequency. A naive solution could mistakenly fail to check the prime condition efficiently or might miscount element frequencies.
Approaches
A brute-force approach would first iterate over each element and count how many times it occurs in the array. Then, for each frequency, we would check if it is prime by testing divisibility with numbers up to the frequency itself. This approach works correctly but involves redundant counting for repeated elements, giving an unnecessary quadratic complexity.
The optimal approach uses a hash map (dictionary in Python or map in Go) to count the frequencies of each element in a single pass. Then, we check each unique frequency for primality. Since the array length is at most 100, we only need to check numbers from 2 to 100 for primality. This is efficient, avoids redundant counting, and leverages the mathematical property that a number is prime if it has no divisors other than 1 and itself.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Count frequency of each element repeatedly and check prime each time |
| Optimal | O(n * √m) | O(n) | Use a hash map to count frequencies and check each unique frequency for primality; m ≤ 100 |
Here n is the length of the array, and m is the maximum frequency, which cannot exceed n.
Algorithm Walkthrough
- Initialize an empty hash map to count the frequency of each element in the array. The keys of the map will be the elements of the array, and the values will be their respective counts.
- Iterate through the input array, updating the hash map by incrementing the count for each element. This ensures we count each element exactly once.
- Define a helper function to determine if a number is prime. This function should return false for numbers less than 2. For numbers 2 or greater, iterate from 2 up to the square root of the number and check if any number divides it evenly. If so, it is not prime; otherwise, it is prime.
- Iterate over the frequencies stored in the hash map. For each frequency, use the helper function to check if it is prime.
- If any frequency is prime, return true immediately. If no prime frequencies are found after checking all elements, return false.
This algorithm works because it separates concerns: counting elements efficiently using a hash map ensures correctness, and the prime-checking function guarantees mathematical correctness. The combination ensures that any prime frequency will be detected, and the algorithm avoids redundant checks.
We are given an integer array nums and must determine whether there exists at least one distinct value in the array whose frequency of occurrence is a prime number.
Formally, if we define a frequency function $f(x)$ as the number of indices $i$ such that $nums[i] = x$, the task is to check whether there exists an element $x$ for which $f(x)$ is a prime number. If such an element exists, the output is true; otherwise, the output is false.
The input constraints are small: the array length is at most 100, and each element lies in the range $[0, 100]$. This immediately implies that both the number of distinct elements and the maximum frequency are bounded by 100.
The key edge cases include arrays where all elements are distinct (all frequencies equal to 1, which is not prime), arrays with a single element, and arrays where multiple elements share the same frequency. Since 1 is explicitly not prime, any frequency equal to 1 must be rejected.
Approaches
Brute Force Approach
The most direct approach is to compute the frequency of each distinct element and then, for each element, check whether its frequency is prime using a naive primality test. This can be done by iterating from 2 up to $\sqrt{f(x)}$ for each frequency.
This approach is correct because it directly follows the definition: compute frequencies and test primality independently. However, it is redundant because primality checks may be repeated for the same frequency values multiple times if implemented carelessly.
Optimal Approach
The optimal approach observes that frequencies are bounded by 100, so primality can be precomputed for all integers in this range using a simple sieve or direct marking. Then we compute the frequency map once and check each frequency against the precomputed prime table.
This eliminates repeated primality checks and reduces the problem to a linear scan over frequency values.
Complexity Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | $O(n \sqrt{n})$ | $O(n)$ | Count frequencies and test primality per element |
| Optimal | $O(n + M \log \log M)$ | $O(M)$ | Precompute primes up to $M = 100$, then scan frequencies |
Algorithm Walkthrough
We proceed with the optimal method.
- Construct a frequency map over
numsusing a hash table keyed by element value. This is necessary to obtain $f(x)$ for every distinct element in constant expected time per insertion. - Determine the maximum possible frequency bound, which is at most
len(nums). Since $|nums| \le 100$, we only need primality information up to 100. - Precompute a boolean array
is_primeof size 101 whereis_prime[i]indicates whether $i$ is prime. This is done using a sieve-like marking process. This step ensures that primality queries are constant time. - Iterate over all frequency values in the frequency map.
- For each frequency $f$, check whether
is_prime[f]is true. If any such frequency is prime, returntrueimmediately. - If the iteration completes without finding a prime frequency, return
false.
Why it works
The correctness follows from the fact that every element frequency is explicitly checked against a complete and correct classification of primality over the entire possible domain. Since frequencies are exactly represented in the hash map and primality is precomputed without omission or approximation, the decision procedure is both exhaustive and sound.
Python Solution
from typing import List
import math
class Solution:
def checkPrimeFrequency(self, nums: List[int]) -> bool:
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
def is_prime(n: int) -> bool:
if n < 2:
return False
for i in range(2, int(math.isqrt(n)) + 1):
if n % i == 0:
return False
return True
for count in freq.values():
if is_prime(count):
return True
return False
In the Python implementation, we first count the frequency of each element using a dictionary. The is_prime helper efficiently checks primality up to the square root of the frequency, reducing unnecessary computations. Finally, we iterate through the frequencies and return true if any are prime.
for x in nums:
freq[x] = freq.get(x, 0) + 1
n = len(nums)
is_prime = [False] * (n + 1)
if n >= 2:
is_prime[2] = True
for i in range(3, n + 1):
is_prime[i] = True
p = 2
while p * p <= n:
if is_prime[p]:
for j in range(p * p, n + 1, p):
is_prime[j] = False
p += 1
for f in freq.values():
if f <= n and is_prime[f]:
return True
return False
The implementation first builds a hash map `freq` to compute frequencies. It then constructs a sieve-based primality table `is_prime` up to `n`. Finally, it scans all frequency values and returns early upon encountering a prime frequency.
## Go Solution
```go
import "math"
func checkPrimeFrequency(nums []int) bool {
freq := make(map[int]int)
for _, num := range nums {
freq[num]++
}
isPrime := func(n int) bool {
if n < 2 {
return false
}
limit := int(math.Sqrt(float64(n)))
for i := 2; i <= limit; i++ {
if n%i == 0 {
return false
}
}
return true
}
for _, count := range freq {
if isPrime(count) {
return true
}
}
func checkPrimeFrequency(nums []int) bool {
freq := make(map[int]int)
n := len(nums)
for _, x := range nums {
freq[x]++
}
isPrime := make([]bool, n+1)
if n >= 2 {
isPrime[2] = true
}
for i := 3; i <= n; i++ {
isPrime[i] = true
}
for p := 2; p*p <= n; p++ {
if isPrime[p] {
for j := p * p; j <= n; j += p {
isPrime[j] = false
}
}
}
for _, f := range freq {
if f <= n && isPrime[f] {
return true
}
}
return false
}
In Go, we use a map to count element frequencies. The isPrime closure checks if a number is prime, iterating up to the integer square root. Go requires explicit conversion for math.Sqrt to work with integers. Otherwise, the logic is identical to Python.
Worked Examples
Example 1: nums = [1,2,3,4,5,4]
| Step | freq dictionary | Prime check | Result |
|---|---|---|---|
| 1 | {} | - | - |
| 2 | {1:1, 2:1, 3:1, 4:2, 5:1} | 1 (false), 2 (true) | return true |
Example 2: nums = [1,2,3,4,5]
| Step | freq dictionary | Prime check | Result |
|---|---|---|---|
| 1 | {} | - | - |
| 2 | {1:1,2:1,3:1,4:1,5:1} | all 1 (false) | return false |
Example 3: nums = [2,2,2,4,4]
| Step | freq dictionary | Prime check | Result |
|---|---|---|---|
| 1 | {} | - | - |
| 2 | {2:3,4:2} | 3 (prime), 2 (prime) | return true |
| In Go, we explicitly allocate a boolean slice for primality. Unlike Python, map access and iteration are similarly straightforward. There are no concerns about integer overflow given the small constraint range. The sieve logic is identical, with slice indexing replacing list operations. |
Worked Examples
Example 1: nums = [1,2,3,4,5,4]
Frequency construction:
| Value | Frequency |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 1 |
Prime table (relevant): 2 is prime.
We scan frequencies:
- 1 is not prime
- 2 is prime → early return
true
Example 2: nums = [1,2,3,4,5]
| Value | Frequency |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 1 |
All frequencies are 1. Since 1 is not prime, no match is found. The algorithm returns false.
Example 3: nums = [2,2,2,4,4]
| Value | Frequency |
|---|---|
| 2 | 3 |
| 4 | 2 |
Prime checks:
- 3 is prime → condition satisfied
- 2 is prime → also valid
The algorithm returns true.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n * √n) | Counting frequencies takes O(n), checking primality for each frequency takes up to O(√n) |
| Space | O(n) | Hash map stores frequencies for up to n unique elements |
Because the array length is small (≤100), the algorithm is efficient in practice. | Time | $O(n + M \log \log M)$ | Frequency counting takes $O(n)$, sieve runs up to $M \le 100$, final scan is $O(M)$ | | Space | $O(M)$ | Frequency map and primality table bounded by input size |
The complexity is effectively linear in practice due to the constant upper bound of 100.
Test Cases
# Provided examples
assert Solution().checkPrimeFrequency([1,2,3,4,5,4]) == True # 4 appears twice
assert Solution().checkPrimeFrequency([1,2,3,4,5]) == False # all frequencies are 1
assert Solution().checkPrimeFrequency([2,2,2,4,4]) == True # 2 appears 3 times, 4 appears 2 times
# Edge cases
assert Solution().checkPrimeFrequency([1]) == False # single element, frequency 1
assert Solution().checkPrimeFrequency([1,1]) == True # frequency 2 is prime
assert Solution().checkPrimeFrequency([1,1,1]) == True # frequency 3 is prime
assert Solution().checkPrimeFrequency([1,2,2,3,3,3,4,4,4,4]) == True # multiple prime frequencies
assert Solution().checkPrimeFrequency([i for i in range(100)]) == False # all frequencies 1
assert Solution().checkPrimeFrequency([1,2,3,4,5,4]) == True # basic prime frequency exists
assert Solution().checkPrimeFrequency([1,2,3,4,5]) == False # all frequencies are 1
assert Solution().checkPrimeFrequency([2,2,2,4,4]) == True # multiple prime frequencies
assert Solution().checkPrimeFrequency([7]) == False # single element frequency = 1
assert Solution().checkPrimeFrequency([1,1]) == True # frequency 2 is prime
assert Solution().checkPrimeFrequency([0,0,0,0]) == False # frequency 4 is not prime
assert Solution().checkPrimeFrequency([5,5,5,5,5,5,5]) == False # frequency 7 is prime should be True
assert Solution().checkPrimeFrequency([5,5,5,5,5,5,5]) == True # corrected prime case
| Test | Why |
|---|---|
| [1,2,3,4,5,4] | Tests a single prime frequency |
| [1,2,3,4,5] | Tests all frequencies non-prime |
| [2,2,2,4,4] | Multiple elements with prime frequencies |
| [1] | Single element edge case |
| [1,1] | Frequency of 2, smallest prime |
| [1,1,1] | Frequency of 3, next prime |
| [1..100] | Large array with frequency 1, non-prime |
Edge Cases
One important edge case is an array of length 1. Since the only element has a frequency of 1, which is not prime, the correct output is false. A naive implementation might incorrectly consider 1 as prime.
Another edge case is when all elements are unique, as in [0,1,2,...]. Each frequency is 1, and again, the result must be false. The hash map ensures we count accurately without missing any elements.
A third edge case involves multiple elements sharing the same prime frequency, such as [2,2,3,3,3,5,5]. The algorithm correctly detects any prime frequency among them because it checks all unique frequencies stored in the map. This avoids false negatives even when multiple frequencies exist.
| mixed frequencies | verifies detection of a prime frequency |
| all unique | ensures rejection of frequency 1 |
| repeated values | checks multiple candidates |
| single element | boundary case for minimal input |
| double element | smallest prime frequency case |
Edge Cases
One important edge case is when all elements are distinct. In this situation every frequency equals 1, which is not prime by definition. The algorithm correctly handles this because it explicitly checks primality via a precomputed table where is_prime[1] is false.
Another edge case is when the array has only one element. The frequency is 1, and since the sieve initialization only marks primes starting from 2, the algorithm correctly returns false without special casing.
A third edge case is when multiple elements share the same frequency, potentially prime or composite. The algorithm does not assume uniqueness of frequencies and checks all values in the frequency map independently, ensuring correctness regardless of duplication patterns.