We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum of Distinct Subarrays With Length K

Number: 2552

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, tcs, IBM, Microsoft, Nvidia, TikTok

Problem Description

Given an integer array nums and an integer k, find the maximum subarray sum among all contiguous subarrays of length k that contain all distinct elements. If no such subarray exists, return 0.

Key Insights

  • Use a sliding window of fixed length k to iterate through the array.
  • Maintain a frequency map (or hash table) for elements in the current window to easily check for duplicate elements.
  • Instead of recalculating the sum for each window, update the current sum by subtracting the element that is exiting the window and adding the new element.
  • Only consider the current window’s sum if the frequency map size is equal to k (no duplicates).

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in nums, as each element is added and removed from the sliding window exactly once. Space Complexity: O(k) in the worst-case scenario for maintaining the frequency map.

Solution

The problem is solved using a sliding window technique. We maintain a window of size k along with a hash table (or dictionary) to count the occurrence of elements in the window. For each move of the window:

  1. Add the new element and update the current window sum.
  2. If the window size exceeds k, remove the leftmost element and update the frequency map and current sum.
  3. Check if the current window contains distinct elements by verifying if the size of the frequency dictionary equals k.
  4. If valid, update the maximum sum. This approach ensures that each element is processed in constant time on average, and the sliding window guarantees that we only look at contiguous segments.

Code Solutions

# Python solution for Maximum Sum of Distinct Subarrays With Length K

def maximumSubarraySum(nums, k):
    # Dictionary to store frequencies of elements in current window
    freq = {}
    current_sum = 0
    max_sum = 0
    left = 0  # window left pointer
    
    # Loop through each element in the array using a sliding window approach
    for right in range(len(nums)):
        # Add the new element at the 'right' end of the window
        current = nums[right]
        freq[current] = freq.get(current, 0) + 1
        current_sum += current
        
        # Slide window if its size is greater than k
        if right - left + 1 > k:
            remove_val = nums[left]
            freq[remove_val] -= 1
            # Remove element from dictionary if its count becomes zero
            if freq[remove_val] == 0:
                del freq[remove_val]
            current_sum -= remove_val
            left += 1
        
        # Check the window only if it has exactly k elements and all are distinct
        if right - left + 1 == k and len(freq) == k:
            max_sum = max(max_sum, current_sum)
    
    return max_sum

# Example usage:
print(maximumSubarraySum([1,5,4,2,9,9,9], 3))  # Output: 15
← Back to All Questions