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.lengthWe 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).
Java
C++
Go
Practice Sum of Weighted Modes in Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor