AlgoInsight

DSA problem

Maximum Sum of Distinct Subarrays With Length K

MediumSliding Window - Fixed SizePattern: Fixed-Size Sliding Windowtop300AmazonGoogleMicrosoft

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:

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.

This combines a fixed-size window of width k with a distinctness check. We slide the window across the array, maintaining both the running sum and a frequency map of the elements currently inside the window. Whenever the window has exactly k elements and every element appears exactly once, the window is a valid candidate.

Examples

Example 1
Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of length 3 with distinct elements are [1,5,4] (sum 10), [5,4,2] (sum 11), and [4,2,9] (sum 15). The maximum is 15. The subarrays [2,9,9] and [9,9,9] contain duplicates and do not qualify.
Example 2
Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The only subarray of length 3 is [4,4,4], which contains repeated elements. No valid subarray exists, so the answer is 0.
Example 3
Input: nums = [9,9,9,1,2,3], k = 3
Output: 6
Explanation: The only window with all distinct elements is [1,2,3] with sum 6.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

sliding-windowarrayhash-table

Browse all DSA problems