Maximum Frequency Score of a Subarray solution and explanation
The 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 the maximum frequency score of a subarray of size k in nums. You should maximize the value under the modulo and not the actual value.
A subarray is a contiguous part of an array.
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 <= 1051 <= nums[i] <= 106
Approach overview
Problem Overview: You are given an integer array nums and an integer k. For every subarray of size k, compute a frequency score where each distinct value contributes value^frequency. The task is to return the maximum score among all such subarrays while handling large values using modular arithmetic.
Approach 1: Recompute Frequency for Every Window (Brute Force) (Time: O(n * k log k), Space: O(k))
The straightforward method evaluates each subarray of length k independently. For every window, build a frequency map using a hash table. After computing frequencies, iterate through the map and calculate the score by summing value^freq using fast exponentiation. This requires rebuilding the map for each window and recomputing powers repeatedly. The approach is simple and easy to reason about, but it becomes slow for large arrays since each window costs O(k) operations plus exponentiation.
Approach 2: Hash Table + Sliding Window + Fast Power (Time: O(n log k), Space: O(k))
The optimized approach avoids recomputing everything for each subarray. Instead, maintain a sliding window of size k using the classic two-pointer pattern from sliding window problems. A frequency map tracks how many times each value appears in the current window. The key insight is to maintain the score incrementally: when a number x appears with frequency f, its contribution is x^f. When you add another x, update the score by subtracting x^f and adding x^(f+1). When removing an element as the window slides, reverse the update by replacing x^f with x^(f-1).
Exponentiation uses fast modular power since values can grow quickly. Each update only touches the entering and leaving elements, so the window moves in linear time across the array. The hash map stores at most k elements, keeping memory bounded. This technique combines ideas from array traversal, hash-based counting, and modular math.
Recommended for interviews: Interviewers expect the sliding window optimization. Explaining the brute-force solution first demonstrates understanding of the scoring definition. Transitioning to an incremental update using a hash map and sliding window shows algorithmic maturity and the ability to reduce repeated work from O(n*k) to near linear time.
Solution
We use a hash table cnt to maintain the elements of the window of size k and their frequencies.
First, calculate the score of all elements in the initial window of size k. Then, use a sliding window to add one element at a time and remove the leftmost element, while updating the score using fast power.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
class Solution:
def maxFrequencyScore(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
cnt = Counter(nums[:k])
ans = cur = sum(pow(k, v, mod) for k, v in cnt.items()) % mod
i = k
while i < len(nums):
a, b = nums[i - k], nums[i]
if a != b:
cur += (b - 1) * pow(b, cnt[b], mod) if cnt[b] else b
cur -= (a - 1) * pow(a, cnt[a] - 1, mod) if cnt[a] > 1 else a
cur %= mod
cnt[b] += 1
cnt[a] -= 1
ans = max(ans, cur)
i += 1
return ansclass Solution {
private final int mod = (int) 1e9 + 7;
public int maxFrequencyScore(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < k; ++i) {
cnt.merge(nums[i], 1, Integer::sum);
}
long cur = 0;
for (var e : cnt.entrySet()) {
cur = (cur + qpow(e.getKey(), e.getValue())) % mod;
}
long ans = cur;
for (int i = k; i < nums.length; ++i) {
int a = nums[i - k];
int b = nums[i];
if (a != b) {
if (cnt.getOrDefault(b, 0) > 0) {
cur += (b - 1) * qpow(b, cnt.get(b)) % mod;
} else {
cur += b;
}
if (cnt.getOrDefault(a, 0) > 1) {
cur -= (a - 1) * qpow(a, cnt.get(a) - 1) % mod;
} else {
cur -= a;
}
cur = (cur + mod) % mod;
cnt.put(b, cnt.getOrDefault(b, 0) + 1);
cnt.put(a, cnt.getOrDefault(a, 0) - 1);
ans = Math.max(ans, cur);
}
}
return (int) ans;
}
private long qpow(long a, long n) {
long ans = 1;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
ans = ans * a % mod;
}
a = a * a % mod;
}
return ans;
}
}class Solution {
public:
int maxFrequencyScore(vector<int>& nums, int k) {
using ll = long long;
const int mod = 1e9 + 7;
auto qpow = [&](ll a, ll n) {
ll ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans = ans * a % mod;
}
a = a * a % mod;
}
return ans;
};
unordered_map<int, int> cnt;
for (int i = 0; i < k; ++i) {
cnt[nums[i]]++;
}
ll cur = 0;
for (auto& [k, v] : cnt) {
cur = (cur + qpow(k, v)) % mod;
}
ll ans = cur;
for (int i = k; i < nums.size(); ++i) {
int a = nums[i - k], b = nums[i];
if (a != b) {
cur += cnt[b] ? (b - 1) * qpow(b, cnt[b]) % mod : b;
cur -= cnt[a] > 1 ? (a - 1) * qpow(a, cnt[a] - 1) % mod : a;
cur = (cur + mod) % mod;
ans = max(ans, cur);
cnt[b]++;
cnt[a]--;
}
}
return ans;
}
};func maxFrequencyScore(nums []int, k int) int {
cnt := map[int]int{}
for _, v := range nums[:k] {
cnt[v]++
}
cur := 0
const mod int = 1e9 + 7
qpow := func(a, n int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
for k, v := range cnt {
cur = (cur + qpow(k, v)) % mod
}
ans := cur
for i := k; i < len(nums); i++ {
a, b := nums[i-k], nums[i]
if a != b {
if cnt[b] > 0 {
cur += (b - 1) * qpow(b, cnt[b]) % mod
} else {
cur += b
}
if cnt[a] > 1 {
cur -= (a - 1) * qpow(a, cnt[a]-1) % mod
} else {
cur -= a
}
cur = (cur + mod) % mod
ans = max(ans, cur)
cnt[b]++
cnt[a]--
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recompute Frequency for Every Window | O(n * k log k) | O(k) | Useful for understanding the scoring logic or when constraints are very small |
| Hash Table + Sliding Window + Fast Power | O(n log k) | O(k) | Best general solution for large arrays; avoids recomputation by updating contributions incrementally |
Frequently asked questions
Is Maximum Frequency Score of a Subarray easy or hard?
Maximum Frequency Score of a Subarray is classified as Hard on LeetCode. The difficulty comes from maintaining the score efficiently while the window slides and handling exponentiation with large numbers under modular arithmetic.
Maximum Frequency Score of a Subarray Python/Java solution
Implement a sliding window of length k and store frequencies in a dictionary (Python) or HashMap (Java). Maintain a running score and update it using modular fast power whenever frequencies change. The same logic works in C++ and Go with unordered_map or map structures.
How to solve Maximum Frequency Score of a Subarray in O(n)?
Use a sliding window of size k and maintain a hash map storing frequencies of elements in the window. Track the score dynamically by replacing the previous contribution x^f with x^(f+1) when adding an element, and reversing the update when removing it. With efficient modular exponentiation, the window moves through the array in near linear time.
What is the best approach for Maximum Frequency Score of a Subarray?
The optimal approach uses a sliding window with a hash table to track element frequencies and modular fast power to compute value^frequency contributions. The score is updated incrementally whenever an element enters or leaves the window. This reduces repeated work and runs in O(n log k) time with O(k) extra space.
Is Maximum Frequency Score of a Subarray asked at Google/Amazon/Meta?
Problems combining sliding window, frequency counting, and modular arithmetic appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test the ability to maintain aggregate values while a window moves across an array.
What data structure is used in Maximum Frequency Score of a Subarray?
The primary data structure is a hash table (or hashmap) that stores the frequency of each element in the current window. Combined with a sliding window over the array, it allows constant-time updates when elements are added or removed.
What is the time complexity of Maximum Frequency Score of a Subarray?
The optimized solution runs in O(n log k) time because each element enters and leaves the sliding window once, and each update requires a fast exponentiation operation. Space complexity is O(k) due to the frequency map storing elements inside the current window.