Maximum Sum of Distinct Subarrays With Length K

Maximum Sum of Distinct Subarrays With Length K - Problem

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

The length of the subarray is k, and
All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1,2,6,7,5,1], k = 3

› Output: 18

💡 Note: The subarray [6,7,5] has distinct elements and sum = 6 + 7 + 5 = 18, which is maximum among all valid subarrays.

Example 2 — No Valid Subarray

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

› Output: 0

💡 Note: Every 3-length subarray contains duplicate elements (like [1,2,1]), so no valid distinct subarray exists.

Example 3 — Single Valid Window

$ Input: nums = [4,4,4], k = 3

› Output: 0

💡 Note: The only subarray [4,4,4] has duplicate elements, so return 0.

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array [1,2,1,2,6,7,5,1] with k=3

Find Distinct Windows

Check each 3-length subarray for distinct elements

Maximum Sum

Return highest sum from valid windows: 18

Key Takeaway

🎯 Key Insight: Use sliding window with frequency map to efficiently track distinct elements while maintaining running sum

Asked in

a Amazon 45 G Google 38 M Microsoft 32 f Facebook 28

The key insight is to use a sliding window with frequency tracking to efficiently check for distinct elements. Best approach uses a frequency map to maintain O(n) time complexity by avoiding repeated sum calculations. Time: O(n), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n×k)	O(k)	Check every possible subarray of length k for distinct elements
Sliding Window with Hash Set	O(n×k)	O(k)	Use sliding window technique with hash set to track distinct elements
Optimized Sliding Window with Frequency Map	O(n)	O(k)	Use frequency map to efficiently track duplicates while maintaining running sum

Brute Force — Algorithm Steps

Iterate through all possible starting positions
For each position, check k elements for distinctness
If distinct, calculate sum and update maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Window 1

Examine first k elements for duplicates

Check Window 2

Move to next position, check again

Find Maximum

Track the highest sum from valid windows

Code -

solution.c — C

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

long long solution(int* nums, int numsSize, int k) {
    long long maxSum = 0;
    
    for (int i = 0; i <= numsSize - k; i++) {
        // Check for duplicates in current window
        bool hasDuplicate = false;
        for (int j = i; j < i + k && !hasDuplicate; j++) {
            for (int l = j + 1; l < i + k; l++) {
                if (nums[j] == nums[l]) {
                    hasDuplicate = true;
                    break;
                }
            }
        }
        
        if (!hasDuplicate) {
            long long sum = 0;
            for (int j = i; j < i + k; j++) {
                sum += nums[j];
            }
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            nums[numsSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    long long result = solution(nums, numsSize, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×k)

For each of n-k+1 positions, we check k elements for distinctness

✓ Linear Growth

Space Complexity

O(k)

Hash set to check distinctness stores up to k elements

✓ Linear Space

42.2K Views

Medium Frequency

~15 min Avg. Time

1.5K 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