Maximum Sum of Distinct Subarrays With Length K

Leetcode Problem 2461: Maximum Sum of Distinct Subarrays With Length K

Problem Summary

Given an integer array nums and an integer k, return the maximum sum of a subarray of length exactly k where all elements are distinct. Return 0 if no such subarray exists.

Constraints:

• The array has between 1 and 100,000 elements.
• Each element is a positive integer up to 100,000.
• k is between 1 and the array length.

Techniques

• Array
• Hash Table
• Sliding Window

Solution

function maximumSubarraySum(nums: number[], k: number): number {
    let maxSum = 0
    let numbersInSlidingWindow = new Map<number, number>()
    let currentSum = 0

    for (let i = 0; i < k; i++) {
        numbersInSlidingWindow.set(nums[i], (numbersInSlidingWindow.get(nums[i]) || 0) + 1)
        currentSum = currentSum + nums[i]
    }

    for (let i = k; i < nums.length; i++) {
        if (numbersInSlidingWindow.size === k) {
            maxSum = Math.max(maxSum, currentSum)
        }

        let countForElementToBeRemoved = numbersInSlidingWindow.get(nums[i - k])! 

        if (countForElementToBeRemoved > 1) {
            numbersInSlidingWindow.set(nums[i - k], countForElementToBeRemoved - 1)
        } else {
            numbersInSlidingWindow.delete(nums[i - k])
        }
    
        numbersInSlidingWindow.set(nums[i], (numbersInSlidingWindow.get(nums[i]) || 0) + 1)
        currentSum = currentSum + nums[i] - nums[i - k]
    }

    if (numbersInSlidingWindow.size === k) {
        maxSum = Math.max(maxSum, currentSum)
    }

    return maxSum
};