You are given an integer array nums and an integer k.
For every subarray of length k:
mode * frequency(mode).Return the sum of the weights of all subarrays of length k.
Note:
x is the number of times it occurs in the array.
Example 1:
Input: nums = [1,2,2,3], k = 3
Output: 8
Explanation:
Subarrays of length k = 3 are:
| Subarray | Frequencies | Mode | Mode Frequency |
Weight |
|---|---|---|---|---|
| [1, 2, 2] | 1: 1, 2: 2 | 2 | 2 | 2 × 2 = 4 |
| [2, 2, 3] | 2: 2, 3: 1 | 2 | 2 | 2 × 2 = 4 |
Thus, the sum of weights is 4 + 4 = 8.
Example 2:
Input: nums = [1,2,1,2], k = 2
Output: 3
Explanation:
Subarrays of length k = 2 are:
| Subarray | Frequencies | Mode | Mode Frequency |
Weight |
|---|---|---|---|---|
| [1, 2] | 1: 1, 2: 1 | 1 | 1 | 1 × 1 = 1 |
| [2, 1] | 2: 1, 1: 1 | 1 | 1 | 1 × 1 = 1 |
| [1, 2] | 1: 1, 2: 1 | 1 | 1 | 1 × 1 = 1 |
Thus, the sum of weights is 1 + 1 + 1 = 3.
Example 3:
Input: nums = [4,3,4,3], k = 3
Output: 14
Explanation:
Subarrays of length k = 3 are:
| Subarray | Frequencies | Mode | Mode Frequency |
Weight |
|---|---|---|---|---|
| [4, 3, 4] | 4: 2, 3: 1 | 4 | 2 | 2 × 4 = 8 |
| [3, 4, 3] | 3: 2, 4: 1 | 3 | 2 | 2 × 3 = 6 |
Thus, the sum of weights is 8 + 6 = 14.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= k <= nums.lengthProblem Overview: You need to evaluate every subarray and compute its weighted mode, then return the sum of those values. The main challenge is maintaining the current mode efficiently while elements are added or removed as the window changes.
Approach 1: Brute Force Frequency Recalculation (O(n³) time, O(n) space)
Generate every subarray using two nested loops. For each subarray, maintain a frequency map and scan the map to determine the current mode and its weight. Because the mode must be recomputed repeatedly, each extension of a subarray can require a full scan of the map. This approach is easy to implement and useful for validating small inputs, but the repeated counting makes it impractical for large arrays.
Approach 2: Frequency Map with Ordered Set (O(n² log n) time, O(n) space)
Instead of recomputing the mode from scratch, track frequencies using a hash table. Maintain an ordered set or balanced structure keyed by (frequency, value). When a new element is added to the subarray, update its frequency and adjust its position in the ordered structure. The maximum element in this structure represents the current mode. This avoids scanning the entire frequency map each time but still requires iterating over all O(n²) subarrays.
Approach 3: Hash Map + Priority Queue + Sliding Window + Lazy Deletion (O(n² log n) time, O(n) space)
The practical optimized solution combines frequency tracking with a max heap. Use a hash map to store counts and a priority queue storing pairs such as (frequency, value). As the right boundary of the window expands, update the frequency in the map and push the updated pair into the heap. When retrieving the current mode, remove outdated heap entries using lazy deletion until the top matches the current frequency in the map. This avoids expensive updates inside the heap and keeps the mode query efficient.
This technique works well when iterating subarrays using a growing right pointer while maintaining counts incrementally. The heap always exposes the current mode candidate, and lazy deletion ensures correctness without costly heap updates. It combines ideas from array processing, hash table frequency counting, and priority-based ordering.
Recommended for interviews: Interviewers usually expect the hash map + heap strategy with lazy deletion. Showing the brute force first demonstrates understanding of the problem structure. Moving to the heap-based approach shows you know how to maintain dynamic frequency rankings efficiently, which is the core insight.
We use a hash map cnt to record the frequency of each number in the current window. We use a priority queue pq to store the frequency and value of each number in the current window, with priority given to higher frequency, and for equal frequency, to smaller numbers.
We design a function get_mode() to obtain the mode and its frequency in the current window. Specifically, we repeatedly pop the top element from the priority queue until its frequency matches the frequency recorded in the hash map; at that point, the top element is the mode and its frequency for the current window.
We use a variable ans to record the sum of weights for all windows. Initially, we add the first k numbers of the array to the hash map and priority queue, then call get_mode() to get the mode and its frequency for the first window, and add its weight to ans.
Next, starting from the k-th number, we add each number to the hash map and priority queue, and decrement the frequency of the leftmost number in the window in the hash map. Then, we call get_mode() to get the mode and its frequency for the current window, and add its weight to ans.
Finally, we return ans.
The time complexity is O(n log k), and the space complexity is O(k).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Frequency Recalculation | O(n³) | O(n) | Useful for understanding the problem or verifying small test cases |
| Frequency Map + Ordered Set | O(n² log n) | O(n) | When you want structured ordering of elements by frequency |
| Hash Map + Priority Queue + Lazy Deletion | O(n² log n) | O(n) | General case for efficiently tracking the mode during subarray expansion |
Practice Sum of Weighted Modes in Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor