Watch the video solution for Maximum Frequency Score of a Subarray, a hard level problem involving Array, Hash Table, Math. This walkthrough by Code-Yao has 241 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
[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] <= 106Problem 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.
| 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 |