MediumArrayHash TableSliding WindowUpdated Sep 2026

2461. Maximum Sum of Distinct Subarrays With Length K

Asked at Walmart, JPMorgan

Difficulty

Medium

Time

O(n)

Space

O(k)

Pattern

Array

Companies

2

Problem

You are given an integer array nums and an integer k. Look at every subarray of nums that has exactly length k. A subarray means a block of neighbours — the elements must be next to each other in the array.

Among those length-k blocks, keep only the ones where all elements are different (no value appears twice inside the block). From the blocks that pass this test, return the largest sum. If no block passes the test, return 0.

Note that a block can fail only because of a repeated value. Its position in the array does not matter, and you never need to sort or reorder anything.

Only clean blocks of length k count

numssum 10sum 1515429990123456The block [4,2,9] has all distinct values and the biggestsum, so it wins.nums9 repeats9 repeats15429990123456The two blocks on the right contain two 9s, so they areinvalid no matter how large their sum is.
Every block of 3 neighbours is checked; blocks with a repeated value are rejected, and the best sum among the rest is 15.

Constraints

  • ●1 <= k <= nums.length <= 10^5
  • ●1 <= nums[i] <= 10^5

Examples

Example 1
Inputnums = [1,5,4,2,9,9,9], k = 3
Output15
WhyThe length-3 blocks are [1,5,4] (sum 10), [5,4,2] (sum 11), [4,2,9] (sum 15), [2,9,9] and [9,9,9]. The last two contain a repeated 9, so they are thrown away. The best valid sum is 15.
Example 2
Inputnums = [4,4,4], k = 3
Output0
WhyThere is only one length-3 block, [4,4,4], and it repeats the value 4. No valid block exists, so the answer is 0.

Asked At

2 companies
CompanyDifficulty
WalmartMediumView all Walmart questions →
JPMorganMediumView all JPMorgan questions →

How to Think About It

1

Brute force: check every subarray of length k, verify uniqueness with a set, and track the maximum sum.

2

Optimize by using a sliding window of fixed size k with a hash map to count element frequencies.

3

Expand the window by adding elements from the right; when window size exceeds k, remove the leftmost element.

4

When a duplicate is detected, shrink the window from the left until the duplicate is removed.

5

Maintain a running sum, add the new element on expansion, subtract the removed element on shrink, and update the max sum.

Optimal Approach

Use a sliding window of fixed size k with a hash map tracking element frequencies. As you expand the right pointer, add elements and their counts. When a duplicate is detected (count > 1), shrink from the left until the duplicate is removed. When the window reaches size k, update the maximum sum. This runs in O(n) time with O(k) space.

Sliding window with a frequency map

numssum 10, 3 distinct15429990123456leftrightFirst window: [1,5,4], sum 10, map size 3 = k, so it isvalid and best = 10.numssum 15, 3 distinct15429990123456leftrightSlide right: drop 1, add 9. Window [4,2,9] has sum 15 and3 distinct values, so best becomes 15.numsmap size 2 < k15429990123456leftrightWindow [2,9,9] has only 2 distinct values, so map size isless than k and this window is skipped.add nums[right], then remove nums[left] if size > kvalid when window size == k and map size == kbest = max(best, curr_sum)
The window always has length k; a map counts values inside it, and the sum is updated as elements enter and leave.
ComplexityTime O(n)Space O(k)Each element enters and leaves the window at most once, and the hash map holds at most k distinct values.

What Trips People Up in Real Interviews

1

Clarify whether elements must be strictly distinct or if the subarray itself must contain no duplicates.

2

Edge case: all elements in the array are the same — the answer is 0 since no subarray of length k has distinct elements.

3

Edge case: array length equals k — check if all k elements are distinct and return their sum.

4

Distinguish this from classic maximum sum subarray problems — the distinct constraint changes the approach entirely.

5

Watch for integer overflow if element values are large; use long for the running sum in production code.

Solution Code

O(n) time
def maximumSubarraySum(nums, k):
    from collections import defaultdict
    count = defaultdict(int)
    curr_sum = 0
    max_sum = 0
    left = 0
    for right in range(len(nums)):
        count[nums[right]] += 1
        curr_sum += nums[right]
        if right - left + 1 > k:
            count[nums[left]] -= 1
            curr_sum -= nums[left]
            if count[nums[left]] == 0:
                del count[nums[left]]
            left += 1
        if right - left + 1 == k and len(count) == k:
            max_sum = max(max_sum, curr_sum)
    return max_sum

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Sum of Distinct Subarrays With Length K problem?

Given an integer array nums and an integer k, find the maximum sum of a subarray of length k where all elements are distinct. If no such subarray exists, return 0. A subarray is a contiguous non-empty sequence of elements within an array.

How do you solve Maximum Sum of Distinct Subarrays With Length K?

The optimal approach runs in O(n) time and O(k) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Sum of Distinct Subarrays With Length K?

Maximum Sum of Distinct Subarrays With Length K is asked at Walmart, JPMorgan. It is a medium difficulty problem.

What are common mistakes on Maximum Sum of Distinct Subarrays With Length K?
  • Clarify whether elements must be strictly distinct or if the subarray itself must contain no duplicates.
  • Edge case: all elements in the array are the same — the answer is 0 since no subarray of length k has distinct elements.
  • Edge case: array length equals k — check if all k elements are distinct and return their sum.
  • Distinguish this from classic maximum sum subarray problems — the distinct constraint changes the approach entirely.
  • Watch for integer overflow if element values are large; use long for the running sum in production code.