Scale Engineer

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
ArrayHash TableHeap (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 <= 105
  • 1 <= nums[i] <= 109
  • 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]:

  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.
  2. The entries of the frequency map are then transferred to a list.
  3. 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).
  4. We determine the number of top elements to consider, which is min(x, number of distinct elements).
  5. We iterate through these top elements, and for each one, we add value * frequency to a running sum for the current subarray.
  6. 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.

import java.util.*; class Solution {    public long[] getXSum(int[] nums, int k, int x) {        int n = nums.length;        long[] answer = new long[n - k + 1];         for (int i = 0; i <= n - k; i++) {            Map<Integer, Integer> freqMap = new HashMap<>();            for (int j = i; j < i + k; j++) {                freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1);            }             List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freqMap.entrySet());                        entries.sort((a, b) -> {                if (!a.getValue().equals(b.getValue())) {                    return b.getValue().compareTo(a.getValue());                }                return b.getKey().compareTo(a.getKey());            });             long currentXSum = 0;            for (int j = 0; j < Math.min(x, entries.size()); j++) {                Map.Entry<Integer, Integer> entry = entries.get(j);                currentXSum += (long) entry.getKey() * entry.getValue();            }                        answer[i] = currentXSum;        }        return answer;    }}

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

class 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 →

Next problem