LeetCode 3318 - Find X-Sum of All K-Long Subarrays I

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sliding Window, Heap (Priority Queue)

Solution

Problem Understanding

The problem asks us to compute a special value called the x-sum for every contiguous subarray of length k.

For each window of size k, we first count how many times each number appears. After that, we only keep the contributions of the top x most frequent distinct values. If multiple values have the same frequency, the larger value is considered more important and wins the tie.

The final x-sum is not the sum of the distinct elements. Instead, it is the sum of all occurrences of the selected elements inside the window.

For example, suppose a window contains:

[1, 1, 2, 2, 3, 4]

The frequencies are:

1 -> 2
2 -> 2
3 -> 1
4 -> 1

If x = 2, we keep the two most frequent values. Values 1 and 2 both appear twice, so both are selected. Their total contribution is:

1 + 1 + 2 + 2 = 6

The input consists of:

nums, the original integer array
k, the fixed size of each sliding window
x, the number of most frequent distinct values we keep

The output should contain one answer for every valid window of size k. Since there are n - k + 1 such windows, the answer array has exactly that length.

The constraints are very small:

n <= 50
nums[i] <= 50

These limits tell us that even relatively inefficient approaches are acceptable. We do not need highly optimized balanced trees or advanced heap maintenance. A direct counting and sorting approach is completely feasible.

Several edge cases are important:

A window may contain fewer than x distinct elements. In that case, we keep everything.
Multiple elements may share the same frequency, so the tie-breaking rule using larger values must be handled carefully.
k may equal 1, meaning every window contains only one element.
x may equal k, which often means the entire window contributes to the sum.
All numbers may be identical, producing only one distinct element in every window.

Approaches

Brute Force Approach

The most direct solution is to process every window independently.

For each subarray of length k:

Count the frequency of every number using a hash map.
Convert the frequency map into a list of (frequency, value) pairs.
Sort the pairs by:

higher frequency first
larger value first if frequencies are equal

Take the first x pairs.
Add frequency * value for those selected pairs.

This works because the sorting order exactly matches the definition of the problem.

Although this approach recomputes frequencies from scratch for every window, the constraints are tiny, so it is still acceptable.

Optimal Sliding Window Approach

A better solution uses a sliding window frequency map.

Instead of rebuilding counts from scratch for every window, we maintain frequencies incrementally:

When the window moves right, remove the outgoing element.
Add the incoming element.

This reduces repeated work and makes the implementation cleaner and more scalable.

For each window, we still need to determine the top x frequent values. Since the number of distinct values is small, sorting the frequency entries is inexpensive.

The key insight is that maintaining frequencies incrementally is more efficient than recomputing them entirely for every window.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((n - k + 1) * k log k)	O(k)	Rebuilds frequencies for every window
Optimal	O((n - k + 1) * d log d)	O(d)	Uses sliding window counts, where d is distinct values

Since d <= 50, the optimal approach is very efficient.

Algorithm Walkthrough

Create a frequency map for the first window of size k.

We use a hash map because it gives efficient updates and lookups for element frequencies. 2. Define a helper function that computes the x-sum from the current frequency map.

Inside this helper:

Convert the map into a list of (value, frequency) pairs.
Sort by descending frequency.
If frequencies tie, sort by descending value.
Take the first x entries.
Add value * frequency for each selected entry.

Compute the answer for the first window and store it.
Slide the window one step at a time.

For every move:

Remove the leftmost outgoing element from the frequency map.
If its frequency becomes zero, delete it from the map.
Add the new incoming element.

After updating the map, compute the new x-sum using the helper function.
Continue until all windows are processed.

Why it works

At every step, the frequency map exactly represents the current window because we remove one outgoing element and add one incoming element. The sorting order matches the problem definition precisely:

Higher frequency comes first.
Larger value wins ties.

Therefore, the selected top x entries are always correct, and their contributions produce the required x-sum.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        freq = defaultdict(int)

        # Build frequency map for first window
        for i in range(k):
            freq[nums[i]] += 1

        def compute_x_sum() -> int:
            pairs = []

            for value, count in freq.items():
                pairs.append((count, value))

            # Sort by frequency descending, then value descending
            pairs.sort(key=lambda p: (-p[0], -p[1]))

            total = 0

            for i in range(min(x, len(pairs))):
                count, value = pairs[i]
                total += count * value

            return total

        answer = [compute_x_sum()]

        # Slide the window
        for right in range(k, len(nums)):
            left = right - k

            outgoing = nums[left]
            freq[outgoing] -= 1

            if freq[outgoing] == 0:
                del freq[outgoing]

            incoming = nums[right]
            freq[incoming] += 1

            answer.append(compute_x_sum())

        return answer

The implementation begins by constructing the frequency map for the first window. A defaultdict(int) is convenient because missing keys automatically start at zero.

The compute_x_sum() helper converts the current frequencies into sortable pairs. Each pair stores (count, value) so we can sort according to the problem rules. The sorting key uses negative values to achieve descending order.

After sorting, we only examine the first x entries because those represent the most important elements under the problem definition.

The sliding window loop updates the frequency map incrementally. The outgoing element is removed, and if its count becomes zero, the key is deleted entirely. Then the incoming element is added.

Because the frequency map always reflects the current window, each call to compute_x_sum() produces the correct answer for that window.

Go Solution

package main

import "sort"

func findXSum(nums []int, k int, x int) []int {
	freq := make(map[int]int)

	// Build first window
	for i := 0; i < k; i++ {
		freq[nums[i]]++
	}

	computeXSum := func() int {
		type Pair struct {
			count int
			value int
		}

		pairs := []Pair{}

		for value, count := range freq {
			pairs = append(pairs, Pair{count, value})
		}

		sort.Slice(pairs, func(i, j int) bool {
			if pairs[i].count != pairs[j].count {
				return pairs[i].count > pairs[j].count
			}
			return pairs[i].value > pairs[j].value
		})

		total := 0

		limit := x
		if len(pairs) < limit {
			limit = len(pairs)
		}

		for i := 0; i < limit; i++ {
			total += pairs[i].count * pairs[i].value
		}

		return total
	}

	answer := []int{computeXSum()}

	// Slide the window
	for right := k; right < len(nums); right++ {
		left := right - k

		outgoing := nums[left]
		freq[outgoing]--

		if freq[outgoing] == 0 {
			delete(freq, outgoing)
		}

		incoming := nums[right]
		freq[incoming]++

		answer = append(answer, computeXSum())
	}

	return answer
}

The Go implementation closely mirrors the Python solution. Since Go does not have tuples, a small Pair struct is used to store (count, value) entries.

The custom comparator inside sort.Slice implements the exact ordering required by the problem. Maps in Go are naturally suited for frequency counting.

All arithmetic safely fits inside Go's int type because the constraints are very small.

Worked Examples

Example 1

Input:

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

Initial Window

Window:

[1,1,2,2,3,4]

Frequency map:

Value	Count
1	2
2	2
3	1
4	1

Sorted by priority:

Count	Value
2	2
2	1
1	4
1	3

Top x = 2 values are 2 and 1.

Sum:

2*2 + 2*1 = 6

Answer becomes:

[6]

Slide Window Right

New window:

[1,2,2,3,4,2]

Remove 1, add 2.

Frequency map:

Value	Count
1	1
2	3
3	1
4	1

Sorted order:

Count	Value
3	2
1	4
1	3
1	1

Top two entries:

2 and 4

Sum:

3*2 + 1*4 = 10

Answer:

[6, 10]

Slide Again

New window:

[2,2,3,4,2,3]

Remove 1, add 3.

Frequency map:

Value	Count
2	3
3	2
4	1

Sorted order:

Count	Value
3	2
2	3
1	4

Top two entries:

2 and 3

Sum:

3*2 + 2*3 = 12

Final answer:

[6, 10, 12]

Example 2

Input:

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

Every window has at most two distinct elements, and x = 2, so every element contributes.

Window	Sum
[3,8]	11
[8,7]	15
[7,8]	15
[8,7]	15
[7,5]	12

Final answer:

[11, 15, 15, 15, 12]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n - k + 1) * d log d)	Each window sorts at most d distinct values
Space	O(d)	Frequency map stores distinct elements

Here, d is the number of distinct values in the current window. Since the constraints limit values to at most 50 distinct numbers, the algorithm is extremely efficient in practice.

The sliding window update itself is constant time, while the sorting dominates the complexity.

Test Cases

from typing import List

sol = Solution()

# Example 1
assert sol.findXSum([1,1,2,2,3,4,2,3], 6, 2) == [6,10,12]

# Example 2
assert sol.findXSum([3,8,7,8,7,5], 2, 2) == [11,15,15,15,12]

# Single element array
assert sol.findXSum([5], 1, 1) == [5]

# All elements identical
assert sol.findXSum([2,2,2,2], 2, 1) == [4,4,4]

# x larger than distinct count
assert sol.findXSum([1,2,1], 3, 5) == [4]

# Tie breaking by larger value
assert sol.findXSum([1,2,3,4], 2, 1) == [2,3,4]

# Window size equals array size
assert sol.findXSum([1,2,2,3], 4, 2) == [7]

# Multiple ties
assert sol.findXSum([4,3,2,1], 3, 2) == [7,5]

# k = 1
assert sol.findXSum([7,8,9], 1, 1) == [7,8,9]

# Distinct elements only
assert sol.findXSum([1,2,3,4,5], 3, 2) == [5,7,9]

Test	Why
Example 1	Validates core frequency ranking behavior
Example 2	Verifies case where all elements contribute
Single element array	Smallest valid input
All elements identical	Tests one distinct value
x larger than distinct count	Ensures all values are included
Tie breaking by larger value	Confirms larger value wins ties
Window size equals array size	Tests single-window scenario
Multiple ties	Verifies sorting correctness
k = 1	Tests smallest window size
Distinct elements only	Tests repeated tie situations

Edge Cases

One important edge case occurs when the number of distinct elements is smaller than x. In this situation, the problem states that all elements should contribute to the result. A buggy implementation might incorrectly try to access nonexistent entries after sorting. This implementation safely uses:

min(x, len(pairs))

so only existing distinct values are processed.

Another important case is frequency ties. Suppose multiple numbers appear the same number of times. The problem requires the larger number to be considered more frequent. If sorting only by frequency, the answer becomes incorrect. The implementation explicitly sorts by descending value as the secondary criterion, guaranteeing correct tie handling.

A third edge case appears when removing elements from the sliding window. After decrementing a frequency, the count may become zero. If zero-frequency entries remain in the map, later sorting may incorrectly include them. The implementation deletes keys whose frequency reaches zero, ensuring the map always reflects the exact contents of the current window.