#3321

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find X-Sum of All K-Long Subarrays II

Calculate the x-sum for every k-length subarray using efficient array scanning and hash-based counting techniques.

array hash table sliding window heap priority queue

Problem Statement

Given an integer array nums and integers k and x, compute a list where each element represents the x-sum of a k-length subarray of nums. The x-sum is defined as the sum of the smallest x distinct elements in the subarray, or the sum of all elements if there are fewer than x distinct elements.

Return an array of length n - k + 1 containing the x-sums for all contiguous subarrays of length k. Implement a solution that efficiently handles large n up to 105 and uses the sliding window plus hash lookup pattern to avoid recalculating sums unnecessarily.

Examples

Example 1

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

Output: [6,10,12]

Example 2

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

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

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

Solution Approach

Sliding Window Initialization

Initialize a window of size k and build a hash map counting occurrences of each element. Sort the keys to quickly access the smallest x distinct elements and compute the initial x-sum.

Window Sliding and Hash Update

Slide the window one element at a time. Decrease the count of the outgoing element and remove it if count reaches zero. Add the incoming element to the hash map and update its count. Recalculate x-sum using the updated hash map.

Optimize Sum Calculation

Instead of fully sorting each window, maintain a min-heap or ordered structure for distinct elements to efficiently extract the smallest x values. This reduces repeated sorting overhead and maintains the array scanning plus hash lookup pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on maintaining the hash map and min-heap or ordered structure, roughly O(n log x) for all n-k+1 windows. Space complexity is O(k) for the hash map and auxiliary data structures.

What Interviewers Usually Probe

Expect clarification on handling fewer than x distinct elements in a window.
Check if candidate uses sliding window properly instead of recalculating sums naively.
Look for correct use of hash map or counting structure to track element frequencies.

Common Pitfalls or Variants

Common pitfalls

Recomputing sums from scratch for each window instead of updating incrementally.
Failing to handle windows with fewer than x distinct elements correctly.
Neglecting edge cases when elements repeat and the smallest x distinct elements change.

Follow-up variants

Compute the largest x distinct elements instead of the smallest for each k-length subarray.
Return the average of the x smallest distinct elements for each window instead of the sum.
Use a circular array where windows wrap around the end of the array.

FAQ

What is the x-sum in Find X-Sum of All K-Long Subarrays II?

The x-sum is the sum of the smallest x distinct elements in a k-length subarray, or the sum of all elements if there are fewer than x distinct elements.

Can I use a naive approach to solve this problem?

Naive recomputation for each subarray is too slow for large arrays; a sliding window plus hash lookup is required for efficiency.

How do I handle repeated elements in the subarray?

Track counts in a hash map and only consider distinct elements when calculating the x-sum, updating counts as the window slides.

Is sorting required for every window?

Full sorting is unnecessary; maintaining a min-heap or ordered structure for distinct elements suffices for efficient smallest x element retrieval.

What pattern does this problem exemplify?

It exemplifies array scanning plus hash lookup, combining sliding window techniques with frequency tracking for optimal performance.

terminal

Solution

Solution 1: Hash Table + Ordered Set

We use a hash table $\textit{cnt}$ to count the occurrences of each element in the window, an ordered set $\textit{l}$ to store the $x$ elements with the highest occurrences in the window, and another ordered set $\textit{r}$ to store the remaining elements.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

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

Continue Practicing

#3318 find x sum of all k long subarrays i #3505 minimum operations to make elements within k subarrays equal #3013 divide an array into subarrays with minimum cost ii