Find X-Sum of All K-Long Subarrays II

Hard

#2950Time: O((n - k) * k log k) - For each of the `n - k + 1` windows, we build a frequency map in O(k) time. Then, we sort the distinct elements. If there are `D` distinct elements (where `D <= k`), sorting takes O(D log D). In the worst case, `D=k`, so sorting is O(k log k). The total time is dominated by this, resulting in O((n - k + 1) * k log k).Space: O(k) - For each window, we create a frequency map and a list that can store up to `k` distinct elements in the worst case. This space is reused for each window.

Patterns

Sliding Window

Data structures

Array Hash Table Heap (Priority Queue)

Prompt

You are given an array nums of n integers and two integers k and x.

The x-sum of an array is calculated by the following procedure:

Count the occurrences of all elements in the array.
Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.
Calculate the sum of the resulting array.

Note that if an array has less than x distinct elements, its x-sum is the sum of the array.

Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

Example 1:

Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

Output: [6,10,12]

Explanation:

For subarray [1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2.
For subarray [1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times.
For subarray [2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3.

Example 2:

Input: nums = [3,8,7,8,7,5], k = 2, x = 2

Output: [11,15,15,15,12]

Explanation:

Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1].

Constraints:

nums.length == n
1 <= n <= 10⁵
1 <= nums[i] <= 10⁹
1 <= x <= k <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward method is to iterate through each of the n - k + 1 possible subarrays of length k. For each subarray, we perform the full x-sum calculation from scratch. This involves counting element frequencies, sorting them according to the problem's criteria, identifying the top x elements, and summing their occurrences.

Algorithm

Initialize an empty list answer to store the results.
Iterate with a loop from i = 0 to n - k to represent the starting index of each subarray.
For each subarray nums[i...i+k-1]:
1. Create a HashMap to count the frequency of each element within this specific subarray.
2. Convert the HashMap entries into a List.
3. Sort this list based on the specified criteria: primarily by frequency in descending order, and secondarily by element value in descending order for tie-breaking.
4. Initialize a variable currentXSum to zero.
5. Iterate through the top min(x, list.size()) elements of the sorted list.
6. For each of these top elements, add its total contribution (value * frequency) to currentXSum.
7. Add currentXSum to the answer list.
After the loop finishes, return the answer array.

Walkthrough

We use a loop that iterates from i = 0 to n - k. In each iteration, i represents the starting index of a new subarray.

Inside the loop, for the subarray nums[i...i+k-1]:

A HashMap is used to store the frequency of each number in the current k-length subarray. We iterate from j = i to i+k-1 to populate this map.
The entries of the frequency map are then transferred to a list.
This list is sorted. The sorting criteria are: primarily by frequency in descending order, and secondarily by the element's value in descending order (for tie-breaking).
We determine the number of top elements to consider, which is min(x, number of distinct elements).
We iterate through these top elements, and for each one, we add value * frequency to a running sum for the current subarray.
This sum is the x-sum for the subarray starting at i, and it's added to our final answer array.

This process is repeated for all n - k + 1 subarrays.

1import java.util.*;2 3class Solution {4    public long[] getXSum(int[] nums, int k, int x) {5        int n = nums.length;6        long[] answer = new long[n - k + 1];7 8        for (int i = 0; i <= n - k; i++) {9            Map<Integer, Integer> freqMap = new HashMap<>();10            for (int j = i; j < i + k; j++) {11                freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1);12            }13 14            List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freqMap.entrySet());15            16            entries.sort((a, b) -> {17                if (!a.getValue().equals(b.getValue())) {18                    return b.getValue().compareTo(a.getValue());19                }20                return b.getKey().compareTo(a.getKey());21            });22 23            long currentXSum = 0;24            for (int j = 0; j < Math.min(x, entries.size()); j++) {25                Map.Entry<Integer, Integer> entry = entries.get(j);26                currentXSum += (long) entry.getKey() * entry.getValue();27            }28            29            answer[i] = currentXSum;30        }31        return answer;32    }33}

Complexity

Time

O((n - k) * k log k) - For each of the `n - k + 1` windows, we build a frequency map in O(k) time. Then, we sort the distinct elements. If there are `D` distinct elements (where `D <= k`), sorting takes O(D log D). In the worst case, `D=k`, so sorting is O(k log k). The total time is dominated by this, resulting in O((n - k + 1) * k log k).

Space

O(k) - For each window, we create a frequency map and a list that can store up to `k` distinct elements in the worst case. This space is reused for each window.

Trade-offs

Pros

Simple to understand and implement.
Correct for all cases, assuming no time constraints.

Cons

Highly inefficient due to redundant computations for overlapping parts of subarrays.
Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints.

Solutions

Solution

1class Solution { private TreeSet < int []> l = new TreeSet <>(( a , b ) -> a [ 0 ] == b [ 0 ] ? a [ 1 ] - b [ 1 ] : a [ 0 ] - b [ 0 ]); private TreeSet < int []> r = new TreeSet <>( l . comparator ()); private Map < Integer , Integer > cnt = new HashMap <>(); private long s ; public long [] findXSum ( int [] nums , int k , int x ) { int n = nums . length ; long [] ans = new long [ n - k + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; remove ( v ); cnt . merge ( v , 1 , Integer: : sum ); add ( v ); int j = i - k + 1 ; if ( j < 0 ) { continue ; } while (! r . isEmpty () && l . size () < x ) { var p = r . pollLast (); s += 1L * p [ 0 ] * p [ 1 ]; l . add ( p ); } while ( l . size () > x ) { var p = l . pollFirst (); s -= 1L * p [ 0 ] * p [ 1 ]; r . add ( p ); } ans [ j ] = s ; remove ( nums [ j ]); cnt . merge ( nums [ j ], - 1 , Integer: : sum ); add ( nums [ j ]); } return ans ; } private void remove ( int v ) { if (! cnt . containsKey ( v )) { return ; } var p = new int [] { cnt . get ( v ), v }; if ( l . contains ( p )) { l . remove ( p ); s -= 1L * p [ 0 ] * p [ 1 ]; } else { r . remove ( p ); } } private void add ( int v ) { if (! cnt . containsKey ( v )) { return ; } var p = new int [] { cnt . get ( v ), v }; if (! l . isEmpty () && l . comparator (). compare ( l . first (), p ) < 0 ) { l . add ( p ); s += 1L * p [ 0 ] * p [ 1 ]; } else { r . add ( p ); } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem