Maximum Frequency Score of a Subarray
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array nums and a positive integer k.
The frequency score of an array is the sum of the distinct values in the array raised to the power of their frequencies , taking the sum
modulo 109 + 7.
- For example, the frequency score of the array
[5,4,5,7,4,4]is(43 + 52 + 71) modulo (109 + 7) = 96.
Return _themaximum frequency score of a subarray of size _k
innums. You should maximize the value under the modulo and not the actual value.
A subarray is a contiguous part of an array.
Examples
Example 1:
Input: nums = [1,1,1,2,1,2], k = 3
Output: 5
Explanation: The subarray [2,1,2] has a frequency score equal to 5. It can be shown that it is the maximum frequency score we can have.
Example 2:
Input: nums = [1,1,1,1,1,1], k = 4
Output: 1
Explanation: All the subarrays of length 4 have a frequency score equal to 1.
Constraints:
1 <= k <= nums.length <= 10^51 <= nums[i] <= 10^6
Solution
Method 1 – Sliding Window with Hash Map
Intuition
We want to efficiently compute the frequency score for every subarray of size k. By using a sliding window and a hash map to track frequencies, we can update the score incrementally as the window moves.
Approach
- Use a hash map to count the frequency of each number in the current window.
- For each new element added to the window, update its frequency and the running score.
- For each element removed from the window, update its frequency and the running score.
- For each window of size
k, compute the frequency score as the sum ofval^freqfor all distinct values, modulo10^9 + 7. - Track and return the maximum frequency score found.
Code
C++
class Solution {
public:
int maxFrequencyScore(vector<int>& nums, int k) {
const int MOD = 1e9+7;
unordered_map<int, int> freq;
int n = nums.size();
long long score = 0, ans = 0;
for (int i = 0; i < n; ++i) {
freq[nums[i]]++;
if (i >= k) {
freq[nums[i-k]]--;
if (freq[nums[i-k]] == 0) freq.erase(nums[i-k]);
}
if (i >= k-1) {
long long cur = 0;
for (auto& [v, f] : freq) {
long long t = 1;
for (int j = 0; j < f; ++j) t = t * v % MOD;
cur = (cur + t) % MOD;
}
ans = max(ans, cur);
}
}
return ans;
}
};
Go
func maxFrequencyScore(nums []int, k int) int {
mod := int(1e9+7)
freq := map[int]int{}
ans := 0
for i, v := range nums {
freq[v]++
if i >= k {
freq[nums[i-k]]--
if freq[nums[i-k]] == 0 {
delete(freq, nums[i-k])
}
}
if i >= k-1 {
cur := 0
for val, f := range freq {
t := 1
for j := 0; j < f; j++ {
t = t * val % mod
}
cur = (cur + t) % mod
}
if cur > ans {
ans = cur
}
}
}
return ans
}
Java
class Solution {
public int maxFrequencyScore(int[] nums, int k) {
int mod = 1000000007, n = nums.length, ans = 0;
Map<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < n; i++) {
freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
if (i >= k) {
freq.put(nums[i-k], freq.get(nums[i-k]) - 1);
if (freq.get(nums[i-k]) == 0) freq.remove(nums[i-k]);
}
if (i >= k-1) {
int cur = 0;
for (var e : freq.entrySet()) {
long t = 1;
for (int j = 0; j < e.getValue(); j++) t = t * e.getKey() % mod;
cur = (int)((cur + t) % mod);
}
ans = Math.max(ans, cur);
}
}
return ans;
}
}
Kotlin
class Solution {
fun maxFrequencyScore(nums: IntArray, k: Int): Int {
val mod = 1_000_000_007
val freq = mutableMapOf<Int, Int>()
var ans = 0
for (i in nums.indices) {
freq[nums[i]] = freq.getOrDefault(nums[i], 0) + 1
if (i >= k) {
freq[nums[i-k]] = freq.getOrDefault(nums[i-k], 0) - 1
if (freq[nums[i-k]] == 0) freq.remove(nums[i-k])
}
if (i >= k-1) {
var cur = 0L
for ((v, f) in freq) {
var t = 1L
repeat(f) { t = t * v % mod }
cur = (cur + t) % mod
}
ans = maxOf(ans, cur.toInt())
}
}
return ans
}
}
Python
class Solution:
def maxFrequencyScore(self, nums: list[int], k: int) -> int:
from collections import defaultdict
mod = 10**9+7
freq = defaultdict(int)
ans = 0
for i, v in enumerate(nums):
freq[v] += 1
if i >= k:
freq[nums[i-k]] -= 1
if freq[nums[i-k]] == 0:
del freq[nums[i-k]]
if i >= k-1:
cur = 0
for val, f in freq.items():
t = pow(val, f, mod)
cur = (cur + t) % mod
ans = max(ans, cur)
return ans
Rust
impl Solution {
pub fn max_frequency_score(nums: Vec<i32>, k: i32) -> i32 {
use std::collections::HashMap;
let modn = 1_000_000_007;
let mut freq = HashMap::new();
let mut ans = 0;
for (i, &v) in nums.iter().enumerate() {
*freq.entry(v).or_insert(0) += 1;
if i as i32 >= k {
let e = freq.get_mut(&nums[i - k as usize]).unwrap();
*e -= 1;
if *e == 0 { freq.remove(&nums[i - k as usize]); }
}
if i as i32 >= k - 1 {
let mut cur = 0;
for (&val, &f) in &freq {
let mut t = 1i64;
for _ in 0..f {
t = t * val as i64 % modn;
}
cur = (cur + t) % modn;
}
ans = ans.max(cur as i32);
}
}
ans
}
}
TypeScript
class Solution {
maxFrequencyScore(nums: number[], k: number): number {
const mod = 1e9+7;
const freq = new Map<number, number>();
let ans = 0;
for (let i = 0; i < nums.length; i++) {
freq.set(nums[i], (freq.get(nums[i]) ?? 0) + 1);
if (i >= k) {
freq.set(nums[i-k], freq.get(nums[i-k])! - 1);
if (freq.get(nums[i-k]) === 0) freq.delete(nums[i-k]);
}
if (i >= k-1) {
let cur = 0;
for (const [val, f] of freq.entries()) {
let t = 1;
for (let j = 0; j < f; j++) t = t * val % mod;
cur = (cur + t) % mod;
}
ans = Math.max(ans, cur);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * m), wherenis the length ofnumsandmis the number of distinct values in a window (worst case up tok). - 🧺 Space complexity:
O(m), for the frequency map.