#3318

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find X-Sum of All K-Long Subarrays I

Compute the x-sum of every subarray of length k efficiently using array scanning combined with hash lookup techniques.

array hash table sliding window heap priority queue

Problem Statement

You are given an integer array nums and two integers k and x. The task is to compute the x-sum for every contiguous subarray of length k. The x-sum of a subarray is the sum of its x largest distinct elements, or the sum of all elements if there are fewer than x distinct values.

Return an array of integers where each element corresponds to the x-sum of the subarray of nums starting at that index. Ensure that your solution accounts for repeated values and efficiently handles the scanning of overlapping subarrays using hash-based counting.

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

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

Solution Approach

Sliding Window with Hash Map

Use a sliding window of size k and maintain a hash map to count occurrences of elements within the window. Update the map incrementally as the window moves, which allows computing the x-sum without rescanning the entire subarray each time.

Sorting Distinct Elements in Window

For each window, extract the distinct elements from the hash map, sort them in descending order, and sum the top x elements. This approach ensures the x-sum is correctly calculated according to the definition and handles arrays with fewer than x distinct elements.

Optimization with Heap

Optionally, use a max heap to track the largest x distinct elements in the window dynamically. This avoids sorting every time and speeds up x-sum computation for larger arrays or repeated values, while still leveraging hash-based counts to handle duplicates.

Complexity Analysis

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

Time complexity is O(n * x log x) if sorting distinct elements per window or O(n log x) with a heap optimization. Space complexity is O(k) for the hash map storing window counts.

What Interviewers Usually Probe

Notice how the window shifts and affects element counts.
Expect candidates to handle duplicate values correctly in x-sum computation.
Look for incremental updates instead of recomputing sums from scratch each time.

Common Pitfalls or Variants

Common pitfalls

Failing to account for subarrays with fewer than x distinct elements.
Resorting the entire window each time instead of using incremental counts.
Overcounting elements when duplicates exist within the sliding window.

Follow-up variants

Compute x-sum for all subarrays of variable length instead of fixed k.
Return the y-sum of subarrays based on the smallest distinct elements rather than the largest.
Handle streaming input where the array is not fully available upfront, maintaining a rolling x-sum.

FAQ

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

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

Can I use a heap to optimize the x-sum calculation?

Yes, a max heap can maintain the largest x distinct elements dynamically, reducing the need to sort each window.

How do I handle duplicates when computing x-sum?

Use a hash map to count occurrences of elements within the window and only consider distinct elements when calculating the sum.

What should I do if the subarray has fewer than x distinct elements?

Simply sum all elements in that subarray as the x-sum definition defaults to the total in that case.

Does this problem rely on sliding window or hash lookup pattern?

Yes, the problem pattern focuses on array scanning combined with hash lookup to efficiently calculate x-sums for overlapping subarrays.

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

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