Find X-Sum of All K-Long Subarrays I
EasyPrompt
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
xmost 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 <= 501 <= nums[i] <= 501 <= 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
iof a subarray, from0ton - k. - For each
i, consider the subarray fromnums[i]tonums[i + k - 1]. - Create a helper function
calculateXSumthat takes a subarray (or its start/end indices) andxas 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 thanx, 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
xelements from the sorted list for efficient lookup. - Iterate through the subarray again, and add an element to the
xSumif it is present in the set of topxelements. - Return the final
xSum.
- Store the result of
calculateXSumfor eachiin 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.
import java.util.*; class Solution { public int[] getXSum(int[] nums, int k, int x) { int n = nums.length; int[] answer = new int[n - k + 1]; for (int i = 0; i <= n - k; i++) { answer[i] = calculateXSum(nums, i, i + k - 1, x); } return answer; } private int calculateXSum(int[] nums, int start, int end, int x) { Map<Integer, Integer> freqMap = new HashMap<>(); int totalSum = 0; for (int i = start; i <= end; i++) { int num = nums[i]; freqMap.put(num, freqMap.getOrDefault(num, 0) + 1); totalSum += num; } if (freqMap.size() < x) { return totalSum; } List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(freqMap.entrySet()); entryList.sort((a, b) -> { if (!a.getValue().equals(b.getValue())) { return b.getValue() - a.getValue(); // Descending frequency } else { return b.getKey() - a.getKey(); // Descending value } }); Set<Integer> topXElements = new HashSet<>(); for (int i = 0; i < x; i++) { topXElements.add(entryList.get(i).getKey()); } int xSum = 0; for (int i = start; i <= end; i++) { if (topXElements.contains(nums[i])) { xSum += nums[i]; } } return xSum; }}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 ifkis large.
Solutions
Solution
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 int s;public int[] findXSum(int[] nums, int k, int x) { int n = nums.length; int[] ans = new int[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 += p[0] * p[1]; l.add(p); } while (l.size() > x) { var p = l.pollFirst(); s -= 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 -= 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 += 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.