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

Find X-Sum of All K-Long Subarrays I - 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: 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,2,3,1], k = 3, x = 2

› Output: [8,5]

💡 Note: For subarray [3,2,3]: frequencies are {3:2, 2:1}. Since x=2, take all elements: 3×2 + 2×1 = 8. For subarray [2,3,1]: frequencies are {2:1, 3:1, 1:1}. Take top 2 by frequency,value: 3×1 + 2×1 = 5.

Example 2 — Less Than X Elements

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

› Output: [2,3]

💡 Note: For subarray [1,1]: only 1 distinct element < x=4, so sum all: 1+1 = 2. For subarray [1,2]: only 2 distinct elements < x=4, so sum all: 1+2 = 3.

Example 3 — Tiebreaker by Value

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

› Output: [12]

💡 Note: Subarray [2,4,2,4] has frequencies {2:2, 4:2}. Both have same frequency, so tiebreaker by value: take 4 (bigger) and 2. Sum: 4×2 + 2×2 = 12.

Constraints

1 ≤ n ≤ 50
1 ≤ nums[i] ≤ 50
1 ≤ k ≤ n
1 ≤ x ≤ k

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[3,2,3,1], k=3, x=2

Process

For each subarray: count frequencies, sort, take top x

Output

Array of x-sums: [8,5]

Key Takeaway

🎯 Key Insight: Efficiently count frequencies and use value as tiebreaker to find top x elements

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to efficiently count element frequencies in each k-length subarray and select the top x elements based on frequency (with value as tiebreaker). The brute force approach processes each subarray independently, while the sliding window optimizes by incrementally updating frequency counts. Best approach uses sliding window with frequency map. Time: O(n × k × log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Process Each Subarray	O(n × k × log k)	O(k)	For each subarray, count frequencies and find top x elements
Sliding Window with Frequency Map	O(n × k × log k)	O(k)	Use sliding window to efficiently update frequency counts

Brute Force - Process Each Subarray — Algorithm Steps

Iterate through each starting position
Count frequencies in current subarray
Sort elements by frequency (value breaks ties)
Take top x elements and sum them

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Subarray

Get k consecutive elements

Count Frequencies

Count how often each element appears

Sort & Select

Sort by frequency, then value, take top x

Calculate Sum

Sum the selected elements

Code -

solution.c — C

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

typedef struct {
    int value;
    int count;
} FreqItem;

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

int* solution(int* nums, int numsSize, int k, int x, int* returnSize) {
    *returnSize = numsSize - k + 1;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    
    for (int i = 0; i <= numsSize - k; i++) {
        // Count frequencies using simple array (assuming reasonable range)
        int freq[201] = {0}; // assuming nums[i] in [-100, 100]
        int offset = 100;
        int subarraySum = 0;
        int distinctCount = 0;
        
        for (int j = i; j < i + k; j++) {
            if (freq[nums[j] + offset] == 0) {
                distinctCount++;
            }
            freq[nums[j] + offset]++;
            subarraySum += nums[j];
        }
        
        // If less than x distinct elements, return sum of all
        if (distinctCount <= x) {
            result[i] = subarraySum;
        } else {
            // Convert to items array
            FreqItem items[distinctCount];
            int itemCount = 0;
            
            for (int val = -100; val <= 100; val++) {
                if (freq[val + offset] > 0) {
                    items[itemCount].value = val;
                    items[itemCount].count = freq[val + offset];
                    itemCount++;
                }
            }
            
            // Sort items
            qsort(items, itemCount, sizeof(FreqItem), compare);
            
            // Take top x elements and calculate sum
            int xSum = 0;
            for (int j = 0; j < x; j++) {
                xSum += items[j].value * items[j].count;
            }
            
            result[i] = xSum;
        }
    }
    
    return result;
}

int main() {
    // Parse array input
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3] format
    int nums[100];
    int numsSize = 0;
    char* ptr = strchr(line, '[');
    ptr++;
    
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k, x;
    scanf("%d", &k);
    scanf("%d", &x);
    
    int returnSize;
    int* result = solution(nums, numsSize, k, x, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k × log k)

For each of n-k+1 subarrays, we count frequencies (O(k)) and sort elements (O(k log k))

⚡ Linearithmic

Space Complexity

O(k)

Hash map stores at most k distinct elements for frequency counting

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

342 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 - Process Each Subarray — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler