Skip to main content
Talentd

Sum of Weighted Modes in Subarrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableSliding WindowCounting10 min read
Practice this problem

Problem Statement

You are given an integer array nums and an integer k.

For every subarray of length k:

  • The mode is defined as the element with the highest frequency. If there are multiple choices for a mode, the smallest such element is taken.
  • The weight is defined as mode * frequency(mode).

Return the sum of the weights of all subarrays of length k.

Note:

  • A subarray is a contiguous non-empty sequence of elements within an array.
  • The frequency of an element 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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= nums.length

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Frequency RecalculationO(n³)O(n)Useful for understanding the problem or verifying small test cases
Frequency Map + Ordered SetO(n² log n)O(n)When you want structured ordering of elements by frequency
Hash Map + Priority Queue + Lazy DeletionO(n² log n)O(n)General case for efficiently tracking the mode during subarray expansion

Frequently Asked Questions

Is Sum of Weighted Modes in Subarrays easy or hard?
The problem is generally rated Medium because the brute force idea is straightforward but maintaining the mode efficiently requires combining multiple data structures. Understanding frequency updates and lazy deletion inside a heap is the main challenge.
Sum of Weighted Modes in Subarrays Python/Java solution
Typical implementations maintain a dictionary or HashMap for counts and a heap structure storing (frequency, value) pairs. Python solutions use heapq with negative frequencies, while Java solutions rely on PriorityQueue. C++ often uses priority_queue with lazy deletion checks against the current map.
How to solve Sum of Weighted Modes in Subarrays in O(n)?
An O(n) solution is generally not feasible because the problem requires evaluating properties across all O(n²) subarrays. Most optimized implementations focus on reducing the cost of maintaining the mode using heaps or ordered structures. This leads to an O(n² log n) complexity while keeping each update efficient.
What is the best approach for Sum of Weighted Modes in Subarrays?
The most practical approach uses a hash map for frequency counting combined with a priority queue (max heap) to track the current mode. Each time a value appears in the expanding window, its frequency is updated and pushed into the heap. Lazy deletion removes outdated entries when querying the top. This keeps mode retrieval efficient while processing all subarrays.
Is Sum of Weighted Modes in Subarrays asked at Google/Amazon/Meta?
Problems involving dynamic frequency tracking and mode maintenance appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test your ability to combine hash maps with heaps or ordered data structures to maintain statistics inside sliding windows or subarrays.
What data structure is used in Sum of Weighted Modes in Subarrays?
The main data structures are a hash map for frequency counting and a priority queue (max heap) for retrieving the element with the highest frequency. Some variations also use ordered sets or balanced trees to keep elements sorted by frequency.
What is the time complexity of Sum of Weighted Modes in Subarrays?
The optimized solution typically runs in O(n² log n) time. There are O(n²) subarrays, and each update to the heap or ordered structure costs O(log n). Space complexity is O(n) due to storing frequency counts and heap entries.

Ready to solve this problem?

Practice Sum of Weighted Modes in Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays