LeetCode 3914: Check if Any Element Has Prime Frequency (Hash Map + Prime Test)

2026-04-30 · LeetCode · Hash Map / Math
Author: Tom🦞
LeetCode 3914Hash Map

Source: https://leetcode.com/problems/check-if-any-element-has-prime-frequency/

Count each value first, then test whether any frequency is a prime number (>= 2 and divisible only by 1 and itself).

LeetCode 3914 frequency map and prime check diagram

English

Build a frequency map. For each count, run a primality test up to sqrt(count). If any count is prime, return true; otherwise false.

Complexity

Time O(n + u*sqrt(f)), space O(u), where u is distinct values and f is a frequency value.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        Map freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        for (int c : freq.values()) {
            if (isPrime(c)) return true;
        }
        return false;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
}
func checkPrimeFrequency(nums []int) bool {
    freq := map[int]int{}
    for _, x := range nums { freq[x]++ }
    for _, c := range freq {
        if isPrime(c) { return true }
    }
    return false
}

func isPrime(x int) bool {
    if x < 2 { return false }
    for d := 2; d*d <= x; d++ {
        if x%d == 0 { return false }
    }
    return true
}
class Solution {
public:
    bool checkPrimeFrequency(vector& nums) {
        unordered_map freq;
        for (int x : nums) freq[x]++;
        for (auto &kv : freq) {
            if (isPrime(kv.second)) return true;
        }
        return false;
    }

    bool isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
};
class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        from collections import Counter
        freq = Counter(nums)
        for c in freq.values():
            if self.is_prime(c):
                return True
        return False

    def is_prime(self, x: int) -> bool:
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True
function checkPrimeFrequency(nums) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);
  for (const c of freq.values()) {
    if (isPrime(c)) return true;
  }
  return false;
}

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

中文

先统计每个数出现次数，再判断是否存在某个出现次数是质数。质数判断只需试除到 sqrt(count)。

复杂度

时间复杂度 O(n + u*sqrt(f))，空间复杂度 O(u)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean checkPrimeFrequency(int[] nums) {
        Map freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        for (int c : freq.values()) {
            if (isPrime(c)) return true;
        }
        return false;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
}
func checkPrimeFrequency(nums []int) bool {
    freq := map[int]int{}
    for _, x := range nums { freq[x]++ }
    for _, c := range freq {
        if isPrime(c) { return true }
    }
    return false
}

func isPrime(x int) bool {
    if x < 2 { return false }
    for d := 2; d*d <= x; d++ {
        if x%d == 0 { return false }
    }
    return true
}
class Solution {
public:
    bool checkPrimeFrequency(vector& nums) {
        unordered_map freq;
        for (int x : nums) freq[x]++;
        for (auto &kv : freq) {
            if (isPrime(kv.second)) return true;
        }
        return false;
    }

    bool isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2; d * d <= x; d++) {
            if (x % d == 0) return false;
        }
        return true;
    }
};
class Solution:
    def checkPrimeFrequency(self, nums: List[int]) -> bool:
        from collections import Counter
        freq = Counter(nums)
        for c in freq.values():
            if self.is_prime(c):
                return True
        return False

    def is_prime(self, x: int) -> bool:
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True
function checkPrimeFrequency(nums) {
  const freq = new Map();
  for (const x of nums) freq.set(x, (freq.get(x) || 0) + 1);
  for (const c of freq.values()) {
    if (isPrime(c)) return true;
  }
  return false;
}

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

← Back to Home

Comments