Maximum Sum Of Distinct Subarrays With Length K

Maximum Sum of Distinct Subarrays with Length k

Finding the maximum sum of distinct subarrays of a fixed length k is a common interview problem that blends sliding‑window techniques with hash‑based uniqueness checks. The goal is to scan an array, consider every contiguous block of k elements, check that the block contains no duplicate values, and keep track of the largest total among all such valid blocks. This article walks through the intuition, algorithm design, complexity analysis, and a complete implementation, providing a clear path from brute force to an optimal O(n) solution Less friction, more output..

Introduction

The maximum sum of distinct subarrays with length k problem asks: given an integer array arr and a positive integer k, what is the greatest sum achievable by any subarray of exactly k consecutive elements that contains all distinct numbers? If no such subarray exists, the answer is typically defined as 0 or -∞ depending on the variant. This problem appears in coding contests and technical interviews because it tests two core skills: maintaining a sliding window efficiently and detecting duplicates inside that window in constant time Small thing, real impact..

Problem Understanding

Key Definitions

• Subarray: a contiguous segment of the original array.
• Length k: the subarray must contain exactly k elements.
• Distinct: all elements inside the subarray must be pairwise different; no value may appear twice.
• Maximum sum: among all subarrays satisfying the length and distinctness constraints, we select the one with the highest arithmetic sum.

Example

Consider arr = [4, 2, 1, 2, 5, 3, 2] and k = 3.

The maximum sum among distinct windows is 10.

Brute‑Force Approach

A naïve solution enumerates every possible start index i (0 ≤ i ≤ n‑k), extracts the slice arr[i:i+k], checks for duplicates (e.Now, g. , by inserting into a set and comparing sizes), and updates the answer if the slice is valid.

Pseudo‑code

maxSum = -∞
for i from 0 to n-k:
    window = arr[i : i+k]
    if len(set(window)) == k:          # all distinct
        maxSum = max(maxSum, sum(window))
return maxSum if maxSum != -∞ else 0

Complexity

• Time: O(n · k) for building each window and O(k) for the set → overall O(n·k).
• Space: O(k) for the temporary set.

When k is large (comparable to n), this degrades to O(n²), which is inefficient for typical constraints (n up to 10⁵ or more).

Optimized Sliding‑Window with Frequency Map

We can achieve linear time by maintaining a sliding window of size k while tracking element frequencies. The window moves one step to the right each iteration: we remove the leftmost element and add the new rightmost element, updating a hash map (freq) that stores how many times each value appears in the current window. The window is distinct iff every frequency equals 1, which we can monitor with a counter dupCount that tracks how many values have a frequency > 1.

Algorithm Steps

1. Initialise an empty frequency map freq, dupCount = 0, windowSum = 0, and maxSum = -∞.
2. First window (indices 0 to k‑1):
   • For each element x:
     • Increment freq[x].
     • If freq[x] becomes 2, increment dupCount (a duplicate appeared).
     • Add x to windowSum.
   • After processing, if dupCount == 0, update maxSum = max(maxSum, windowSum).
3. Slide the window from start = 1 to n‑k:
   • Remove left element out = arr[start-1]:
     • Decrement freq[out].
     • If freq[out] becomes 1, decrement dupCount (we resolved a duplicate).
     • If freq[out] becomes 0, delete the entry (optional).
     • Subtract out from windowSum.
   • Add right element in = arr[start+k-1]:
     • Increment freq[in].
     • If freq[in] becomes 2, increment dupCount.
     • Add in to windowSum.
   • If dupCount == 0, update maxSum.
4. After the loop, return maxSum (or 0 if no valid window was found).

Correctness Sketch

• The frequency map always reflects the exact multiset of elements in the current window because we update it precisely when elements leave or enter.
• dupCount equals the number of distinct values whose frequency exceeds 1. Hence dupCount == 0 ⇔ every frequency is 1 ⇔ the window contains all distinct elements.
• The window sum is maintained incrementally, so it always equals the sum of the current k‑length segment.
• So, whenever we record a candidate sum, it corresponds to a valid distinct subarray, and we keep the maximum over all such candidates.

Complexity Analysis

• Time: Each array element is added and removed exactly once → O(n).
• Space: The frequency map holds at most k distinct keys → O(k) (worst‑case O(n) if all elements are unique, but still linear).

Step‑by‑Step Walkthrough

Let’s trace the algorithm on arr = [1, 2, 2, 3, 4, 2, 5] with k = 4 The details matter here. No workaround needed..

| Step