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

Asked in

G Google 15 F Facebook 12 A Amazon 8

The key insight is efficiently maintaining the top x most frequent elements across sliding windows. The brute force approach recalculates everything for each subarray in O(n×k×log k). The optimal approach uses sliding window with heaps to incrementally update frequencies and maintain sorted order in O(n×log k) time, making it much more efficient for large inputs.

Common Approaches

✓ Advanced Heap Management

⏱️ Time: O(n × log k) Space: O(k)

Maintains two heaps (top x elements and remaining) while sliding the window. Uses lazy deletion and careful heap management to efficiently track the top x most frequent elements.

Brute Force

⏱️ Time: O(n × k × log k) Space: O(k)

For each k-length subarray, count element frequencies, sort by frequency then value, take top x elements and sum their contributions. Simple but inefficient for large inputs.

Optimized Sliding Window with Heaps

⏱️ Time: O(n × log k) Space: O(k)

Uses a sliding window approach with frequency tracking and two balanced heaps. As the window slides, efficiently updates frequencies and maintains the top x elements using heap operations.

Advanced Heap Management — Algorithm Steps

Initialize two heaps: top heap (size ≤ x) and bottom heap
For first window, add all elements to appropriate heap
When sliding window: remove old element, add new element
Rebalance heaps to maintain top x elements in top heap
Handle lazy deletion of invalid entries

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Heaps

Create max heap for top x elements and min heap for others

Process Window

Count frequencies and add to appropriate heap

Extract Top X

Pop top x elements from max heap

Calculate Sum

Sum element × frequency for each top element

Code -

solution.c — C

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

typedef struct {
    int val;
    int freq;
} Element;

int compare(const void *a, const void *b) {
    Element *ea = (Element*)a;
    Element *eb = (Element*)b;
    if (ea->freq != eb->freq) {
        return eb->freq - ea->freq;
    }
    return eb->val - ea->val;
}

static char result[10000];

char* solution() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Remove newline
    int len = strlen(line);
    if (len > 0 && line[len-1] == '\n') {
        line[len-1] = '\0';
    }
    
    // Parse array
    int nums[1000];
    int n = 0;
    
    // Skip '['
    char *p = line + 1;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        nums[n] = (int)strtol(p, &p, 10);
        n++;
    }
    
    int k, x;
    scanf("%d", &k);
    scanf("%d", &x);
    
    if (n == 0 || k == 0) {
        strcpy(result, "[]");
        return result;
    }
    
    strcpy(result, "[");
    
    for (int i = 0; i < n - k + 1; i++) {
        // Count frequencies in current window
        Element elements[1000];
        int elemCount = 0;
        
        for (int j = i; j < i + k; j++) {
            int found = 0;
            for (int p = 0; p < elemCount; p++) {
                if (elements[p].val == nums[j]) {
                    elements[p].freq++;
                    found = 1;
                    break;
                }
            }
            if (!found) {
                elements[elemCount].val = nums[j];
                elements[elemCount].freq = 1;
                elemCount++;
            }
        }
        
        // Sort elements by frequency (desc), then value (desc)
        qsort(elements, elemCount, sizeof(Element), compare);
        
        // Take top x items and calculate sum
        int xSum = 0;
        int minCount = (x < elemCount) ? x : elemCount;
        for (int j = 0; j < minCount; j++) {
            xSum += elements[j].val * elements[j].freq;
        }
        
        if (i > 0) strcat(result, ",");
        char temp[20];
        sprintf(temp, "%d", xSum);
        strcat(result, temp);
    }
    
    strcat(result, "]");
    return result;
}

int main() {
    printf("%s\n", solution());
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log k)

Each window update requires O(log k) heap operations

⚡ Linearithmic

Space Complexity

O(k)

Two heaps storing up to k elements total

✓ 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

Find X-Sum of All K-Long Subarrays II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Advanced Heap Management — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler