Find X-Sum of All K-Long Subarrays II - Practice Coding Problems

Find X-Sum of All K-Long Subarrays II - 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 x most 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].

Input & Output

Example 1 — Basic Case

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

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

💡 Note: For subarray [3,8]: frequencies are 3→1, 8→1. Top 2 by frequency then value: 8,3. Sum = 8×1 + 3×1 = 11. For [8,7]: 8→1, 7→1. Top 2: 8,7. Sum = 8×1 + 7×1 = 15.

Example 2 — Single Top Element

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

› Output: [2,4,4]

💡 Note: For [1,1,1,2]: 1→3, 2→1. Top 1: element 1 with freq 3. Sum = 1×3 = 3. Wait, let me recalculate: 1 appears 3 times, 2 appears 1 time. Top 1 most frequent: 1 (freq=3). Sum = 1×3 = 3.

Example 3 — All Elements

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

› Output: [3]

💡 Note: Subarray [1,2] has only 2 distinct elements, which is less than x=3, so x-sum is just the sum of the array: 1 + 2 = 3.

Constraints

1 ≤ n ≤ 5 × 10⁴
1 ≤ nums[i] ≤ 50
1 ≤ k ≤ min(n, 50)
1 ≤ x ≤ k

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,8,7,8,7,5] with k=2, x=2

Process

For each k-length subarray, find top-x most frequent elements

Output

Array of x-sums: [11,15,15,15,12]

Key Takeaway

🎯 Key Insight: For each subarray, efficiently find the top-x most frequent elements using frequency counting and sorting/heaps.

Asked in

G Google 15 F Facebook 12 A Amazon 8

The key insight is to efficiently calculate the x-sum by counting element frequencies and selecting the top-x most frequent elements (with ties broken by larger value). The optimal approach uses sorting or heaps to find the top elements. Time: O((n-k) × k log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O((n-k) × k × log k)	O(k)	Calculate x-sum for each k-length subarray independently
Optimized Sliding Window with Heaps	O((n-k) × k × log k)	O(k)	Use two heaps to maintain top-x elements efficiently as window slides

Brute Force — Algorithm Steps

For each starting position i from 0 to n-k
Count frequencies in subarray nums[i..i+k-1]
Sort elements by frequency (desc), then by value (desc)
Take top x elements and sum their total contributions

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Subarray

Take k consecutive elements

Count & Sort

Count frequencies and sort by frequency then value

Sum Top X

Sum contributions of top x most frequent elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int value;
    int freq;
} Item;

int compare(const void* a, const void* b) {
    Item* itemA = (Item*)a;
    Item* itemB = (Item*)b;
    if (itemA->freq != itemB->freq) {
        return itemB->freq - itemA->freq; // frequency desc
    }
    return itemB->value - itemA->value; // value desc
}

long long* solution(int* nums, int n, int k, int x, int* returnSize) {
    *returnSize = n - k + 1;
    long long* result = (long long*)malloc(*returnSize * sizeof(long long));
    
    for (int i = 0; i <= n - k; i++) {
        // Count frequencies using simple array (assuming reasonable range)
        int freq[2001] = {0}; // assuming values in range [-1000, 1000]
        int offset = 1000;
        
        for (int j = i; j < i + k; j++) {
            freq[nums[j] + offset]++;
        }
        
        // Create items array
        Item items[2001];
        int itemCount = 0;
        for (int val = -1000; val <= 1000; val++) {
            if (freq[val + offset] > 0) {
                items[itemCount].value = val;
                items[itemCount].freq = freq[val + offset];
                itemCount++;
            }
        }
        
        // Sort items
        qsort(items, itemCount, sizeof(Item), compare);
        
        // Calculate x-sum
        long long xSum = 0;
        for (int j = 0; j < x && j < itemCount; j++) {
            xSum += (long long)items[j].value * items[j].freq;
        }
        
        result[i] = xSum;
    }
    
    return result;
}

int main() {
    // Simple parsing for demo
    int nums[] = {3, 8, 7, 8, 7, 5};
    int n = 6, k = 2, x = 2;
    int returnSize;
    
    long long* result = solution(nums, n, k, x, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%lld", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n-k) × k × log k)

For each of (n-k) subarrays, count frequencies in O(k) and sort in O(k log k)

⚡ Linearithmic

Space Complexity

O(k)

Hash map to store frequencies of at most k elements

✓ Linear Space

15.6K Views

Medium Frequency

~25 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler