Find X-Sum of All K-Long Subarrays I

Easy

#2947Time: O(n * k log k). The outer loop runs `n - k + 1` times (O(n)). Inside the loop, building the frequency map takes O(k). Sorting the distinct elements takes O(d log d), where `d` is the number of distinct elements (`d <= k`). In the worst case, this is O(k log k). Thus, the total complexity is O(n * k log k).Space: O(n + k). We need O(n - k + 1) space for the answer array. Inside the loop, we use O(k) space for the frequency map and the list of entries, as there can be at most `k` distinct elements in a subarray of length `k`.

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:

1 <= n == nums.length <= 50
1 <= nums[i] <= 50
1 <= x <= k <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It iterates through each possible subarray of length k, and for each one, it calculates the x-sum independently. This method is straightforward to implement but is the least efficient due to redundant calculations for overlapping subarrays.

Algorithm

Iterate through each possible starting index i of a subarray, from 0 to n - k.
For each i, consider the subarray from nums[i] to nums[i + k - 1].
Create a helper function calculateXSum that takes a subarray (or its start/end indices) and x as input.
Inside calculateXSum:
- Calculate the frequency of each element in the current subarray using a hash map.
- Calculate the total sum of the subarray simultaneously.
- If the number of distinct elements (i.e., freqMap.size()) is less than x, return the total sum.
- Otherwise, convert the frequency map entries into a list.
- Sort the list. The primary sort key is the frequency in descending order. The secondary sort key for tie-breaking is the element's value, also in descending order.
- Create a set containing the top x elements from the sorted list for efficient lookup.
- Iterate through the subarray again, and add an element to the xSum if it is present in the set of top x elements.
- Return the final xSum.
Store the result of calculateXSum for each i in the answer array.

Walkthrough

The brute-force method involves a loop that iterates from the first possible subarray nums[0...k-1] to the last one nums[n-k...n-1]. In each iteration, we treat the current subarray as an independent problem.

For a given subarray, we first determine the frequency of each unique number it contains. A hash map is a suitable data structure for this. While counting frequencies, we can also compute the total sum of the subarray's elements. The problem states that if a subarray has fewer than x distinct elements, its x-sum is its total sum, so we handle this special case first.

If there are x or more distinct elements, we proceed to find the top x most frequent ones. To do this, we convert the frequency map into a list of (element, frequency) pairs and sort it. The sorting criteria are crucial: we sort primarily by frequency in descending order, and for elements with the same frequency, we sort by the element's value in descending order. After sorting, the first x items in the list are our top elements.

Finally, we calculate the x-sum by summing up all occurrences of these top x elements within the subarray. The result is stored, and the process repeats for the next subarray.

1import java.util.*;2 3class Solution {4    public int[] getXSum(int[] nums, int k, int x) {5        int n = nums.length;6        int[] answer = new int[n - k + 1];7 8        for (int i = 0; i <= n - k; i++) {9            answer[i] = calculateXSum(nums, i, i + k - 1, x);10        }11        return answer;12    }13 14    private int calculateXSum(int[] nums, int start, int end, int x) {15        Map<Integer, Integer> freqMap = new HashMap<>();16        int totalSum = 0;17        for (int i = start; i <= end; i++) {18            int num = nums[i];19            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);20            totalSum += num;21        }22 23        if (freqMap.size() < x) {24            return totalSum;25        }26 27        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(freqMap.entrySet());28 29        entryList.sort((a, b) -> {30            if (!a.getValue().equals(b.getValue())) {31                return b.getValue() - a.getValue(); // Descending frequency32            } else {33                return b.getKey() - a.getKey(); // Descending value34            }35        });36 37        Set<Integer> topXElements = new HashSet<>();38        for (int i = 0; i < x; i++) {39            topXElements.add(entryList.get(i).getKey());40        }41 42        int xSum = 0;43        for (int i = start; i <= end; i++) {44            if (topXElements.contains(nums[i])) {45                xSum += nums[i];46            }47        }48        return xSum;49    }50}

Complexity

Time

O(n * k log k). The outer loop runs `n - k + 1` times (O(n)). Inside the loop, building the frequency map takes O(k). Sorting the distinct elements takes O(d log d), where `d` is the number of distinct elements (`d <= k`). In the worst case, this is O(k log k). Thus, the total complexity is O(n * k log k).

Space

O(n + k). We need O(n - k + 1) space for the answer array. Inside the loop, we use O(k) space for the frequency map and the list of entries, as there can be at most `k` distinct elements in a subarray of length `k`.

Trade-offs

Pros

Simple to understand and implement.
Directly follows the logic from the problem description.
Sufficient for the given small constraints.

Cons

Highly inefficient for larger constraints as it recomputes frequencies and sorts for each subarray from scratch.
The time complexity has a factor of k log k, which can be slow if k is large.

This approach improves upon the brute-force method by using a sliding window. Instead of re-calculating frequencies for each subarray from scratch, it maintains a frequency map for the current window and updates it as the window slides. This avoids redundant computations, though it still requires re-sorting the frequencies at each step.

Algorithm

Initialize a frequency map for the first window nums[0...k-1].
Calculate the x-sum for this first window by sorting its frequencies and store it in answer[0].
Iterate from i = 1 to n - k to slide the window.
In each iteration, update the frequency map by decrementing the count of the element leaving the window (nums[i-1]) and incrementing the count of the element entering the window (nums[i+k-1]).
After updating the map, recalculate the x-sum for the new window's state.
This recalculation involves converting the map to a list, sorting it, and summing the contributions of the new top x elements.
Store the new x-sum in answer[i].

Walkthrough

The key insight for this optimization is that consecutive subarrays have a large overlap. When moving from nums[i...i+k-1] to nums[i+1...i+k], only one element is removed (nums[i]) and one is added (nums[i+k]).

We start by processing the initial window (nums[0...k-1]) to get the first x-sum. We build its frequency map and calculate the x-sum just as in the brute-force approach. Then, we loop from i = 1 to n - k.

In each step of the loop, we update the frequency map in O(1) time: decrement the count for nums[i-1] (the outgoing element) and increment the count for nums[i+k-1] (the incoming element). If an element's count drops to zero, we remove it from the map.

With the updated frequency map, we must find the new set of top x elements. We do this by converting the map's entries to a list and sorting it again based on the problem's criteria. Once the new top x elements are identified, we can calculate the new x-sum by iterating through these top x entries and summing up value * frequency. This sum is the answer for the current window.

1import java.util.*;2 3class Solution {4    public int[] getXSum(int[] nums, int k, int x) {5        int n = nums.length;6        int[] answer = new int[n - k + 1];7        Map<Integer, Integer> freqMap = new HashMap<>();8 9        // 1. Initialize the first window10        for (int i = 0; i < k; i++) {11            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);12        }13        answer[0] = calculateXSumFromMap(freqMap, x);14 15        // 2. Slide the window16        for (int i = 1; i <= n - k; i++) {17            // Remove the leftmost element18            int leftElement = nums[i - 1];19            freqMap.put(leftElement, freqMap.get(leftElement) - 1);20            if (freqMap.get(leftElement) == 0) {21                freqMap.remove(leftElement);22            }23 24            // Add the rightmost element25            int rightElement = nums[i + k - 1];26            freqMap.put(rightElement, freqMap.getOrDefault(rightElement, 0) + 1);27 28            // Recalculate x-sum for the new window29            answer[i] = calculateXSumFromMap(freqMap, x);30        }31        return answer;32    }33 34    private int calculateXSumFromMap(Map<Integer, Integer> freqMap, int x) {35        if (freqMap.size() < x) {36            int totalSum = 0;37            for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {38                totalSum += entry.getKey() * entry.getValue();39            }40            return totalSum;41        }42 43        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(freqMap.entrySet());44 45        entryList.sort((a, b) -> {46            if (!a.getValue().equals(b.getValue())) {47                return b.getValue() - a.getValue();48            } else {49                return b.getKey() - a.getKey();50            }51        });52 53        int xSum = 0;54        for (int i = 0; i < x; i++) {55            Map.Entry<Integer, Integer> entry = entryList.get(i);56            xSum += entry.getKey() * entry.getValue();57        }58        return xSum;59    }60}

Complexity

Time

O(n * d log d). Initializing the first window takes O(k + d log d). Each of the `n - k` sliding steps involves updating the map (O(1)) and then sorting the `d` distinct elements (O(d log d)). Since the number of distinct elements `d` is at most 50, `d log d` is a small constant, making the effective time complexity O(n).

Space

O(n + d). O(n) for the output array. The frequency map and the list for sorting take O(d) space, where `d` is the number of distinct elements. Since `nums[i] <= 50`, `d` is at most 50, making this O(1) auxiliary space. Total space is dominated by the output array, O(n).

Trade-offs

Pros

More efficient than brute force, especially if k is large.
Avoids rescanning the entire subarray to build frequencies at each step.
Time complexity is effectively linear in n given the problem's constraints on element values.

Cons

The re-sorting at each step is still a bottleneck, although it's performed on a smaller set of distinct elements (d) compared to k.
Implementation is slightly more complex than the brute-force approach.

Solutions

Solution

1class Solution {2private3  TreeSet<int[]> l =4      new TreeSet<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);5private6  TreeSet<int[]> r = new TreeSet<>(l.comparator());7private8  Map<Integer, Integer> cnt = new HashMap<>();9private10  int s;11public12  int[] findXSum(int[] nums, int k, int x) {13    int n = nums.length;14    int[] ans = new int[n - k + 1];15    for (int i = 0; i < n; ++i) {16      int v = nums[i];17      remove(v);18      cnt.merge(v, 1, Integer : : sum);19      add(v);20      int j = i - k + 1;21      if (j < 0) {22        continue;23      }24      while (!r.isEmpty() && l.size() < x) {25        var p = r.pollLast();26        s += p[0] * p[1];27        l.add(p);28      }29      while (l.size() > x) {30        var p = l.pollFirst();31        s -= p[0] * p[1];32        r.add(p);33      }34      ans[j] = s;35      remove(nums[j]);36      cnt.merge(nums[j], -1, Integer : : sum);37      add(nums[j]);38    }39    return ans;40  }41private42  void remove(int v) {43    if (!cnt.containsKey(v)) {44      return;45    }46    var p = new int[]{cnt.get(v), v};47    if (l.contains(p)) {48      l.remove(p);49      s -= p[0] * p[1];50    } else {51      r.remove(p);52    }53  }54private55  void add(int v) {56    if (!cnt.containsKey(v)) {57      return;58    }59    var p = new int[]{cnt.get(v), v};60    if (!l.isEmpty() && l.comparator().compare(l.first(), p) < 0) {61      l.add(p);62      s += p[0] * p[1];63    } else {64      r.add(p);65    }66  }67}

1class Solution {2public:3  vector<int> findXSum(vector<int> &nums, int k, int x) {4    using pii = pair<int, int>;5    set<pii> l, r;6    int s = 0;7    unordered_map<int, int> cnt;8    auto add = [&](int v) {9      if (cnt[v] == 0) {10        return;11      }12      pii p = {cnt[v], v};13      if (!l.empty() && p > *l.begin()) {14        s += p.first * p.second;15        l.insert(p);16      } else {17        r.insert(p);18      }19    };20    auto remove = [&](int v) {21      if (cnt[v] == 0) {22        return;23      }24      pii p = {cnt[v], v};25      auto it = l.find(p);26      if (it != l.end()) {27        s -= p.first * p.second;28        l.erase(it);29      } else {30        r.erase(p);31      }32    };33    vector<int> ans;34    for (int i = 0; i < nums.size(); ++i) {35      remove(nums[i]);36      ++cnt[nums[i]];37      add(nums[i]);38      int j = i - k + 1;39      if (j < 0) {40        continue;41      }42      while (!r.empty() && l.size() < x) {43        pii p = *r.rbegin();44        s += p.first * p.second;45        r.erase(p);46        l.insert(p);47      }48      while (l.size() > x) {49        pii p = *l.begin();50        s -= p.first * p.second;51        l.erase(p);52        r.insert(p);53      }54      ans.push_back(s);55      remove(nums[j]);56      --cnt[nums[j]];57      add(nums[j]);58    }59    return ans;60  }61};

1from sortedcontainers import SortedList class Solution : def findXSum ( self , nums : List [ int ], k : int , x : int ) -> List [ int ]: def add ( v : int ): if cnt [ v ] == 0 : return p = ( cnt [ v ], v ) if l and p > l [ 0 ]: nonlocal s s += p [ 0 ] * p [ 1 ] l . add ( p ) else : r . add ( p ) def remove ( v : int ): if cnt [ v ] == 0 : return p = ( cnt [ v ], v ) if p in l : nonlocal s s -= p [ 0 ] * p [ 1 ] l . remove ( p ) else : r . remove ( p ) l = SortedList () r = SortedList () cnt = Counter () s = 0 n = len ( nums ) ans = [ 0 ] * ( n - k + 1 ) for i , v in enumerate ( nums ): remove ( v ) cnt [ v ] += 1 add ( v ) j = i - k + 1 if j < 0 : continue while r and len ( l ) < x : p = r . pop () l . add ( p ) s += p [ 0 ] * p [ 1 ] while len ( l ) > x : p = l . pop ( 0 ) s -= p [ 0 ] * p [ 1 ] r . add ( p ) ans [ j ] = s remove ( nums [ j ]) cnt [ nums [ j ]] -= 1 add ( nums [ j ]) return ans

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