Maximum Sum of a Distinct Length-K Subarray

Interview Problem Interview Medium Fixed-size Window Array Hash Map

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.maximumSubarraySum(nums, k). Return the maximum sum among length-k contiguous subarrays whose values are all distinct, or zero if none qualifies.

Starter code

class Solution:
    def maximumSubarraySum(self, nums, k):
        pass

Test cases

best-middle

Expected: 15

Wizard outline

Step 1: Initialize Solution.maximumSubarraySum
Replace the empty starter with the first real state owned by Solution.maximumSubarraySum. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Full Window case
Complete the readable core algorithm for one representative Interview case. Maintain a fixed window's sum and value frequencies, qualifying it when map size equals k.
Step 3: Harden the No Distinct Window boundary
Repair the reviewed boundary and pass the complete submission contract. The maintained state exactly represents the latest at-most-k values. At width k, map size k is equivalent to every value occurring once, so the algorithm considers precisely every eligible window and takes its maximum sum.

Footguns and prerequisites

Delete a frequency-map key when its count reaches zero or distinct-count checks become incorrect.
arrays strings two pointers sliding window
hashing and sets

Reviewed references

LeetCode 2461 — Maximum Sum of Distinct Subarrays With Length K

Practice prerequisites

Slide a Fixed Window(opens in a new tab)
Slide a Fixed Window isolates before appending a result, the rolling total contains exactly values[right - width + 1:right + 1]. That focused state discipline is required when implementing max sum distinct length k as a complete Interview Problem.

Recommended approach and implementation

Add each right value to a running sum and frequency map, remove the value k positions behind once the window grows, and update the answer when the width and number of keys both equal k.

Why it works: The maintained state exactly represents the latest at-most-k values. At width k, map size k is equivalent to every value occurring once, so the algorithm considers precisely every eligible window and takes its maximum sum.

class Solution:
    def maximumSubarraySum(self, nums, k):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        counts = {}
        window_sum = best = 0
        for right, value in enumerate(nums):
            counts[value] = counts.get(value, 0) + 1
            window_sum += value
            if right >= k:
                outgoing = nums[right - k]
                window_sum -= outgoing
                counts[outgoing] -= 1
                if counts[outgoing] == 0:
                    del counts[outgoing]
            if right >= k - 1 and len(counts) == k:
                best = max(best, window_sum)
        return best