Find X-Sum of All K-Long Subarrays I solution and explanation
Google
9 more videos on this problem
Find X-Sum of All K-Long Subarrays I | Revise DSA Fundamentals | Dry Run | Leetcode 3318 | MIKcodestorywithMIK · 19:06 · 7K views
Find X-Sum of All K-Long Subarrays I - Leetcode 3318 PythonNeetCodeIO · 15:57 · 7K views
Find X-Sum of All K-Long Subarrays I | LeetCode 3318 | Java Code | Developer CoderDeveloper Coder · 10:44 · 1K views
3318. Find X-Sum of All K-Long Subarrays I (Leetcode Easy)Programming Live with Larry · 6:04 · 1K views
Find X-Sum of All K-Long Subarrays | LeetCode 3318 | Brute Force to Optimal ApproachSanyam IIT Guwahati · 26:50 · 1K views
Daily Leetcode #2044: Nov 04, 2025 - 3318. Find X-Sum of All K-Long Subarrays IProgramming Live with Larry · 21:56 · 526 views
3318. Find X-Sum of All K-Long Subarrays I | Leetcode Daily - PythonLeetcode Daily · 9:09 · 524 views
Find X Sum of All K Long Subarrays I Leetcode 3318 Java HindiKernel Queen 👑 · 11:58 · 397 views
Find X Sum of All K Long Subarrays I | LeetCode 3318 - Pythonimpoldev · 10:02 · 287 views
Leetcode 3318. Find X-Sum of All K-Long Subarrays I | Sliding Window + Heap | Python SolutionStatLearn Tech · 13:35 · 136 views
The problem
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
Approach overview
Problem Overview: You receive an array nums and integers k and x. For every contiguous subarray of length k, compute the x-sum. The x-sum is formed by selecting the x numbers with the highest frequency in that window (tie broken by larger value) and summing frequency * value for those numbers. The result is an array containing the x-sum for each window.
Approach 1: Brute Force with Sorting (Time: O(n * k log k), Space: O(k))
Process each window independently. For every starting index, iterate through the next k elements and build a frequency map using a hash table. Convert the map entries into a list of (value, frequency) pairs. Sort this list by frequency descending, and if frequencies match, by value descending. Take the first x elements and add frequency * value to compute the window’s x-sum.
This approach is straightforward and mirrors the definition of the problem. The drawback is repeated work: each window rebuilds the frequency map and performs sorting again. Sorting up to k unique elements costs O(k log k), and this happens for roughly n windows. Still, this solution is easy to implement and works well when k is small.
Approach 2: Optimized Sliding Window with Heap (Time: O(n log k), Space: O(k))
Instead of recomputing everything for each window, maintain a running frequency map while sliding the window across the array. Add the new element entering the window and decrement the frequency of the element leaving it. This technique uses the classic sliding window pattern to avoid rebuilding counts.
To efficiently determine the top x elements by frequency and value, maintain a priority queue (max heap) containing pairs representing the current frequency and value. Each time the window changes, push updated entries into the heap. When computing the x-sum, repeatedly extract the best candidates from the heap while discarding outdated entries whose stored frequency no longer matches the value in the frequency map.
This method reduces the need to sort the entire frequency list every time. Heap operations cost O(log k), and each element update happens only when the window moves. The combination of a hash table for counting and a heap (priority queue) for ranking elements makes the process efficient for larger inputs.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the x-sum definition and ordering rule. Then transition to the optimized sliding window solution. Interviewers expect candidates to recognize that overlapping windows share most of their elements, so maintaining frequencies incrementally and using a heap to retrieve the top x contributors shows strong algorithmic thinking.
Approach 1: Brute Force with Sorting
This approach involves iterating over each possible k-length subarray, counting the occurrences of elements, and then selecting the top x elements by sorting the count and element value.
The sorted elements are then summed to determine the x-sum for each subarray. This method is simple but not optimal for larger input sizes.
def find_x_sum(nums, k, x):
n = len(nums)
result = []
for i in range(n - k + 1):
subarray = nums[i:i + k]
freq = [0] * 51
for num in subarray:
freq[num] += 1
freq_sorted = sorted([(i, f) for i, f in enumerate(freq) if f > 0], key=lambda item: (-item[1], -item[0]))
x_sum = 0
for i in range(min(x, len(freq_sorted))):
x_sum += freq_sorted[i][0] * freq_sorted[i][1]
result.append(x_sum)
return result
# Example usage
nums = [1, 1, 2, 2, 3, 4, 2, 3]
k = 6
x = 2
print(find_x_sum(nums, k, x))import java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 3, 4, 2, 3};
int k = 6, x = 2;
Main obj = new Main();
int[] result = obj.findXSum(nums, k, x);
for (int res : result) {
System.out.print(res + " ");
}
}
public int[] findXSum(int[] nums, int k, int x) {
int n = nums.length;
int[] result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
int[] freq = new int[51];
for (int j = i; j < i + k; j++) {
freq[nums[j]]++;
}
List<int[]> freqList = new ArrayList<>();
for (int j = 0; j < 51; j++) {
if (freq[j] > 0) {
freqList.add(new int[]{j, freq[j]});
}
}
freqList.sort((a, b) -> b[1] != a[1] ? b[1] - a[1] : b[0] - a[0]);
int x_sum = 0;
for (int j = 0; j < x && j < freqList.size(); j++) {
x_sum += freqList.get(j)[0] * freqList.get(j)[1];
}
result[i] = x_sum;
}
return result;
}
}#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> nums = {1, 1, 2, 2, 3, 4, 2, 3};
int k = 6, x = 2;
std::vector<int> result;
for (int i = 0; i <= nums.size() - k; ++i) {
std::vector<int> sub(nums.begin() + i, nums.begin() + i + k);
std::vector<int> freq(51, 0);
for (int num : sub) {
freq[num]++;
}
std::vector<std::pair<int, int>> freq_pairs;
for (int j = 0; j < 51; ++j) {
if (freq[j] > 0) {
freq_pairs.push_back({j, freq[j]});
}
}
std::sort(freq_pairs.begin(), freq_pairs.end(), [](const auto& a, const auto& b) {
return a.second > b.second || (a.second == b.second && a.first > b.first);
});
int x_sum = 0;
for (int j = 0; j < x && j < freq_pairs.size(); ++j) {
x_sum += freq_pairs[j].first * freq_pairs[j].second;
}
result.push_back(x_sum);
}
for (int res : result) {
std::cout << res << " ";
}
return 0;
}function findXSum(nums, k, x) {
const n = nums.length;
const result = [];
for (let i = 0; i <= n - k; i++) {
const subarray = nums.slice(i, i + k);
const freq = Array(51).fill(0);
subarray.forEach(num => freq[num]++);
const freqPairs = [];
for (let j = 0; j < 51; j++) {
if (freq[j] > 0) {
freqPairs.push([j, freq[j]]);
}
}
freqPairs.sort((a, b) => b[1] !== a[1] ? b[1] - a[1] : b[0] - a[0]);
let xSum = 0;
for (let j = 0; j < x && j < freqPairs.length; j++) {
xSum += freqPairs[j][0] * freqPairs[j][1];
}
result.push(xSum);
}
return result;
}
// Example usage
const nums = [1, 1, 2, 2, 3, 4, 2, 3];
const k = 6, x = 2;
console.log(findXSum(nums, k, x));#include <stdio.h>
#include <string.h>
void findXSum(int nums[], int n, int k, int x, int result[]) {
for (int i = 0; i <= n-k; i++) {
int count[51] = {0};
for (int j = i; j < i + k; j++) {
count[nums[j]]++;
}
int temp[51][2];
for (int j = 0; j < 51; j++) {
temp[j][0] = j;
temp[j][1] = count[j];
}
for (int j = 0; j < 51; j++) {
for (int m = j + 1; m < 51; m++) {
if ((temp[j][1] < temp[m][1]) ||
((temp[j][1] == temp[m][1]) && (temp[j][0] < temp[m][0]))) {
int t1 = temp[j][0];
int t2 = temp[j][1];
temp[j][0] = temp[m][0];
temp[j][1] = temp[m][1];
temp[m][0] = t1;
temp[m][1] = t2;
}
}
}
int x_sum = 0, count_x = 0;
for (int j = 0; j < 51 && count_x < x && temp[j][1] > 0; j++) {
x_sum += temp[j][0] * temp[j][1];
count_x++;
}
result[i] = x_sum;
}
}
int main() {
int nums[] = {1, 1, 2, 2, 3, 4, 2, 3};
int n = sizeof(nums) / sizeof(nums[0]);
int k = 6;
int x = 2;
int result[n - k + 1];
findXSum(nums, n, k, x, result);
for (int i = 0; i < n - k + 1; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] nums = { 1, 1, 2, 2, 3, 4, 2, 3 };
int k = 6, x = 2;
int[] result = FindXSum(nums, k, x);
Console.WriteLine(string.Join(" ", result));
}
static int[] FindXSum(int[] nums, int k, int x) {
int n = nums.Length;
var result = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
var freq = new int[51];
for (int j = i; j < i + k; j++) {
freq[nums[j]]++;
}
var freqList = new List<(int, int)>();
for (int j = 0; j < 51; j++) {
if (freq[j] > 0) {
freqList.Add((j, freq[j]));
}
}
freqList.Sort((a, b) => b.Item2 != a.Item2 ? b.Item2 - a.Item2 : b.Item1 - a.Item1);
int xSum = 0;
for (int j = 0; j < Math.Min(x, freqList.Count); j++) {
xSum += freqList[j].Item1 * freqList[j].Item2;
}
result[i] = xSum;
}
return result;
}
}The Python solution uses simple list and dictionary operations to keep count, sort, and calculate the x-sum efficiently. Sorting occurs primarily via a custom key to ensure the right elements are captured based on frequency and size.
Time Complexity: O((n-k+1)*51*log(51)), considering the sort. Space Complexity: O(51) to store frequencies.
Approach 2: Optimized Sliding Window
This approach employs a sliding window to maintain the frequency count between subarrays. This allows the reuse of previously calculated frequencies, significantly reducing redundant work by removing the frequency of the outgoing element while adding the frequency of the new incoming element.
def find_x_sum_sliding_window(nums, k, x):
n = len(nums)
result = []
freq = [0] * 51
for i in range(k):
freq[nums[i]] += 1
for i in range(n - k + 1):
if i > 0:
freq[nums[i - 1]] -= 1
freq[nums[i + k - 1]] += 1
freq_sorted = sorted([(i, f) for i, f in enumerate(freq) if f > 0], key=lambda item: (-item[1], -item[0]))
x_sum = 0
for j in range(min(x, len(freq_sorted))):
x_sum += freq_sorted[j][0] * freq_sorted[j][1]
result.append(x_sum)
return result
# Example usage
nums = [1, 1, 2, 2, 3, 4, 2, 3]
k = 6
x = 2
print(find_x_sum_sliding_window(nums, k, x))import java.util.*;
public class Main {
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 3, 4, 2, 3};
int k = 6, x = 2;
Main obj = new Main();
int[] result = obj.findXSumSlidingWindow(nums, k, x);
for (int r : result) {
System.out.print(r + " ");
}
}
public int[] findXSumSlidingWindow(int[] nums, int k, int x) {
int n = nums.length;
int[] result = new int[n - k + 1];
int[] freq = new int[51];
for (int i = 0; i < k; i++) {
freq[nums[i]]++;
}
for (int i = 0; i <= n - k; i++) {
if (i > 0) {
freq[nums[i - 1]]--;
freq[nums[i + k - 1]]++;
}
List<int[]> freqList = new ArrayList<>();
for (int j = 0; j < 51; j++) {
if (freq[j] > 0) {
freqList.add(new int[]{j, freq[j]});
}
}
freqList.sort((a, b) -> b[1] != a[1] ? b[1] - a[1] : b[0] - a[0]);
int x_sum = 0;
for (int j = 0; j < x && j < freqList.size(); j++) {
x_sum += freqList.get(j)[0] * freqList.get(j)[1];
}
result[i] = x_sum;
}
return result;
}
}#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> nums = {1, 1, 2, 2, 3, 4, 2, 3};
int k = 6, x = 2;
std::vector<int> result;
std::vector<int> freq(51, 0);
for (int i = 0; i < k; ++i) {
freq[nums[i]]++;
}
for (int i = 0; i <= nums.size() - k; ++i) {
if (i > 0) {
freq[nums[i - 1]]--;
freq[nums[i + k - 1]]++;
}
std::vector<std::pair<int, int>> freq_pairs;
for (int j = 0; j < 51; ++j) {
if (freq[j] > 0) {
freq_pairs.emplace_back(j, freq[j]);
}
}
std::sort(freq_pairs.begin(), freq_pairs.end(), [](const auto& a, const auto& b) {
return a.second > b.second || (a.second == b.second && a.first > b.first);
});
int x_sum = 0;
for (int j = 0; j < x && j < freq_pairs.size(); ++j) {
x_sum += freq_pairs[j].first * freq_pairs[j].second;
}
result.push_back(x_sum);
}
for (int r : result) {
std::cout << r << " ";
}
return 0;
}function findXSumSlidingWindow(nums, k, x) {
const n = nums.length;
const result = [];
const freq = Array(51).fill(0);
for (let i = 0; i < k; i++) {
freq[nums[i]]++;
}
for (let i = 0; i <= n - k; i++) {
if (i > 0) {
freq[nums[i - 1]]--;
freq[nums[i + k - 1]]++;
}
const freqPairs = [];
for (let j = 0; j < 51; j++) {
if (freq[j] > 0) {
freqPairs.push([j, freq[j]]);
}
}
freqPairs.sort((a, b) => b[1] !== a[1] ? b[1] - a[1] : b[0] - a[0]);
let xSum = 0;
for (let j = 0; j < x && j < freqPairs.length; j++) {
xSum += freqPairs[j][0] * freqPairs[j][1];
}
result.push(xSum);
}
return result;
}
// Example usage
const nums = [1, 1, 2, 2, 3, 4, 2, 3];
const k = 6, x = 2;
console.log(findXSumSlidingWindow(nums, k, x));#include <stdio.h>
#include <string.h>
void findXSumSlidingWindow(int nums[], int n, int k, int x, int result[]) {
int freq[51] = {0};
for (int i = 0; i < k; i++) {
freq[nums[i]]++;
}
for (int i = 0; i <= n - k; i++) {
if (i > 0) {
freq[nums[i - 1]]--;
freq[nums[i + k - 1]]++;
}
int temp[51][2];
for (int j = 0; j < 51; j++) {
temp[j][0] = j;
temp[j][1] = freq[j];
}
for (int j = 0; j < 51; j++) {
for (int m = j + 1; m < 51; m++) {
if ((temp[j][1] < temp[m][1]) ||
((temp[j][1] == temp[m][1]) && (temp[j][0] < temp[m][0]))) {
int t1 = temp[j][0];
int t2 = temp[j][1];
temp[j][0] = temp[m][0];
temp[j][1] = temp[m][1];
temp[m][0] = t1;
temp[m][1] = t2;
}
}
}
int x_sum = 0, count_x = 0;
for (int j = 0; j < 51 && count_x < x && temp[j][1] > 0; j++) {
x_sum += temp[j][0] * temp[j][1];
count_x++;
}
result[i] = x_sum;
}
}
int main() {
int nums[] = {1, 1, 2, 2, 3, 4, 2, 3};
int n = sizeof(nums) / sizeof(nums[0]);
int k = 6;
int x = 2;
int result[n - k + 1];
findXSumSlidingWindow(nums, n, k, x, result);
for (int i = 0; i <= n - k; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] nums = { 1, 1, 2, 2, 3, 4, 2, 3 };
int k = 6, x = 2;
int[] result = FindXSumSlidingWindow(nums, k, x);
Console.WriteLine(string.Join(" ", result));
}
static int[] FindXSumSlidingWindow(int[] nums, int k, int x) {
int n = nums.Length;
var result = new int[n - k + 1];
var freq = new int[51];
for (int i = 0; i < k; i++) {
freq[nums[i]]++;
}
for (int i = 0; i <= n - k; i++) {
if (i > 0) {
freq[nums[i - 1]]--;
freq[nums[i + k - 1]]++;
}
var freqList = new List<(int, int)>();
for (int j = 0; j < 51; j++) {
if (freq[j] > 0) {
freqList.Add((j, freq[j]));
}
}
freqList.Sort((a, b) => b.Item2 != a.Item2 ? b.Item2 - a.Item2 : b.Item1 - a.Item1);
int xSum = 0;
for (int j = 0; j < Math.Min(x, freqList.Count); j++) {
xSum += freqList[j].Item1 * freqList[j].Item2;
}
result[i] = xSum;
}
return result;
}
}The Python sliding window approach optimizes element frequency tracking by updating frequency counts as the window shifts, rather than recalculating from scratch for each new subarray.
Time Complexity: O(n*51*log(51)) due to sorting. Space Complexity: O(51).
Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with Sorting | Time Complexity: O((n-k+1)*51*log(51)), considering the sort. Space Complexity: O(51) to store frequencies. |
| Optimized Sliding Window | Time Complexity: O(n*51*log(51)) due to sorting. Space Complexity: O(51). |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Sorting | O(n * k log k) | O(k) | Simple implementation or when k is small and performance constraints are loose |
| Sliding Window with Heap | O(n log k) | O(k) | Large arrays where recomputing frequencies and sorting every window is too slow |
Frequently asked questions
Is Find X-Sum of All K-Long Subarrays I easy or hard?
The problem is rated Easy because the brute force solution is straightforward: count frequencies and sort them for each window. The challenge increases slightly when optimizing with a sliding window and heap, which introduces common interview data structures.
Find X-Sum of All K-Long Subarrays I Python/Java solution
In Python or Java, implement a sliding window with a dictionary or HashMap to track frequencies. Use a priority queue to keep elements ordered by frequency and value. For each window, extract the top x valid entries and compute the sum of frequency multiplied by value.
How to solve Find X-Sum of All K-Long Subarrays I in O(n)?
A strict O(n) solution is difficult because each window must determine the top x elements by frequency and value. The practical optimized solution achieves O(n log k) using a sliding window to update counts and a heap to retrieve the highest-ranked elements efficiently.
What is the best approach for Find X-Sum of All K-Long Subarrays I?
The most efficient approach uses a sliding window combined with a hash table and a max heap. The sliding window maintains element frequencies as the window moves, while the heap helps retrieve the top x elements by frequency and value. This reduces repeated sorting and runs in O(n log k) time with O(k) extra space.
Is Find X-Sum of All K-Long Subarrays I asked at Google/Amazon/Meta?
Problems involving sliding window frequency tracking and priority queues commonly appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the underlying techniques—frequency maps, window updates, and heap ranking—are standard interview patterns.
What data structure is used in Find X-Sum of All K-Long Subarrays I?
The solution typically uses a hash table to store frequencies of elements in the current window and a max heap (priority queue) to rank elements by frequency and value. The sliding window technique updates these structures efficiently as the window moves.
What is the time complexity of Find X-Sum of All K-Long Subarrays I?
The brute force method takes O(n * k log k) time because every window rebuilds a frequency map and sorts the elements. An optimized sliding window with a heap reduces the complexity to O(n log k) by updating counts incrementally and using heap operations instead of full sorting.