2461. Maximum Sum of Distinct Subarrays With Length K

Problem Description

You are provided with an array nums consisting of integers and an integer k. The task is to locate the subarray (a contiguous non-empty sequence of elements within the array) with a length of exactly k elements such that all elements within the subarray are distinct. Once you identify such subarrays, you need to calculate their sums and determine the maximum sum that can be achieved under these constraints. If there are no subarrays that satisfy the conditions, you should return 0.

Intuition

The intuition behind the solution is based on a sliding window technique coupled with the use of a hash map (in Python, a Counter) to keep track of the distinct elements within the current window. The sliding window technique is a common approach for problems involving contiguous subarray (or substring) operations.

Instead of generating all possible subarrays which would be computationally expensive, we can use a sliding window to move across nums with a fixed length of k. At each step, update the sum of the current window as well as the Counter, which represents the frequency of each number within the window. The sum is updated by adding the new element that comes into the window and subtracting the one that gets removed.

If at any point, the size of the Counter is equal to k, it means all the elements in the window are distinct. This condition is checked after every move of the window one step forward. When this condition is met, we consider the current sum as a candidate for the maximum sum.

By maintaining a running sum of the elements in the current window and updating the Counter accordingly, we can efficiently determine the moment a subarray consisting of k distinct elements is formed and adjust the maximum sum if needed. The solution, therefore, arrives at finding the maximum subarray sum with the given constraints through the sliding window technique and a Counter to track the distinct elements within each window.

Learn more about Sliding Window patterns.

Solution Approach

The solution follows a sliding window approach to maintain a subarray of length k and a Counter from the collections module to track the frequency of elements within this subarray.

Here's a step-by-step explanation of how the implementation works:

Initialize a Counter with the first k elements of nums. This data structure will help efficiently track distinct elements by storing their frequency (number of occurrences).
Calculate the initial sum s of the first k elements. This serves as the starting subarray sum that we will update as we traverse the nums array.
Check if the initial Counter length is k, meaning all elements in the current window are distinct. If they are, assign that sum to ans. If not, ans is assigned a value of 0 to denote no valid subarray has been found yet.
Iterate through the nums array starting at index k and for every new element added to the window: a. Increase the count of the new element (nums[i]) in the Counter and add its value to the running sum s. b. Decrease the count of the element that is no longer within the window (nums[i-k]) and subtract its value from the running sum s. c. Remove the element from the Counter if its frequency drops to zero, ensuring only elements actually in the current window are considered.
After updating the Counter and the sum for the new window position, check again if the size of the Counter is k. If it is, check if the current sum s is greater than the previously recorded ans. If so, update ans with the new sum.
Continue this process until the end of the array is reached. The maintained ans will be the maximum sum of a subarray that satisfies the given conditions.
After completing the iteration, return the final value of ans.

The algorithm ensures that at any point, only subarrays of length k with all distinct elements are considered for updating the maximum sum. This is achieved using the Counter to check for distinct elements and a running sum mechanism to avoid recomputing the sum for each subarray from scratch. Thus, the implementation effectively finds the maximum subarray sum with all distinct elements within the defined length k.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose we have the following nums array and k value:

1nums = [4, 2, 4, 5, 6]
2k = 3

We want to find the subarray of length k where all elements are distinct and has the maximum sum. Let's apply our solution approach step by step:

We initialize a Counter with the first k elements of nums, which are [4, 2, 4]. The Counter will look like: {4: 2, 2: 1}.
Calculate the initial sum s of these k elements: 4 + 2 + 4 = 10.
The initial Counter length is not k (because we have only two distinct elements, and k is 3), so we do not have all distinct elements. We set ans to 0.
Now we start iterating from the index k in the nums array, which is nums[k] = nums[3] = 5.
- We increase the count of the new element (nums[3] = 5) in the Counter. So the Counter becomes {4: 1, 2: 1, 5: 1}.
- We add the new element's value to the sum: s = 10 - 4 + 5 = 11 (we subtract the first element of the current window 4 and add the new element 5).
- We decrease the count of the element that slid out of the window (4) in the Counter. Since its frequency drops to zero, it is removed from the Counter.
The Counter now looks like: {2: 1, 5: 1, 6: 1} with distinct counts and we have a new sum s = 11. As the size of the Counter is equal to k, we compare s to ans. Since 11 > 0, we update ans = 11.
Next, we slide the window by one more element and repeat steps 4 and 5:
- Add nums[4] = 6 to the Counter, updating it to {2: 1, 5: 1, 6: 1} and sum s = 11 - 2 + 6 = 15.
- Now, each element's count is 1 and the Counter size is equal to k, which means all elements are distinct. We compare the sum s to ans. Since 15 > 11, we update ans to 15.
After finishing the iteration, we end up with the final value of ans = 15, which is the maximum sum of a subarray where all elements are distinct for the given k.

Thus, the subarray [4, 5, 6] of length k = 3 gives us the maximum sum of 15 under the constraint that all elements within it are distinct.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
5        # Initialize a counter for the first 'k' elements
6        num_counter = Counter(nums[:k])
7      
8        # Calculate the sum of the first 'k' elements
9        current_sum = sum(nums[:k])
10      
11        # If the number of unique elements equals 'k', assign sum to 'max_sum', else 0
12        max_sum = current_sum if len(num_counter) == k else 0
13      
14        # Iterate over the rest of the elements, starting from the 'k'th element
15        for i in range(k, len(nums)):
16            # Add the new element to the counter and sum
17            num_counter[nums[i]] += 1
18            current_sum += nums[i]
19          
20            # Remove the (i-k)'th element from the counter and sum
21            num_counter[nums[i - k]] -= 1
22            current_sum -= nums[i - k]
23          
24            # If there's no more instances of the (i-k)'th element, remove it from the counter
25            if num_counter[nums[i - k]] == 0:
26                del num_counter[nums[i - k]]
27          
28            # Update 'max_sum' if the number of unique elements in the window equals 'k'
29            if len(num_counter) == k:
30                max_sum = max(max_sum, current_sum)
31      
32        # Return the maximum sum found that matches the unique count condition
33        return max_sum
34

1class Solution {
2    public long maximumSubarraySum(int[] nums, int k) {
3        int n = nums.length;   // Store the length of input array nums
4        // Create a HashMap to count the occurrences of each number in a subarray of size k
5        Map<Integer, Integer> countMap = new HashMap<>(k);
6        long sum = 0;  // Initialize sum of elements in the current subarray
7      
8        // Traverse the first subarray of size k and initialize the countMap and sum
9        for (int i = 0; i < k; ++i) {
10            countMap.merge(nums[i], 1, Integer::sum);
11            sum += nums[i];
12        }
13      
14        // Initialize the answer with the sum of the first subarray if all elements are unique
15        long maxSum = countMap.size() == k ? sum : 0;
16      
17        // Loop over the rest of the array, updating subarrays and checking for maximum sum
18        for (int i = k; i < n; ++i) {
19            // Add current element to the countMap and update the sum
20            countMap.merge(nums[i], 1, Integer::sum);
21            sum += nums[i];
22          
23            // Remove the element that's k positions behind the current one from countMap and update the sum
24            int count = countMap.merge(nums[i - k], -1, Integer::sum);
25            if (count == 0) {
26                countMap.remove(nums[i - k]);
27            }
28            sum -= nums[i - k];
29          
30            // Update maxSum if the countMap indicates that we have a subarray with k unique elements
31            if (countMap.size() == k) {
32                maxSum = Math.max(maxSum, sum);
33            }
34        }
35      
36        // Return the maximum sum found
37        return maxSum;
38    }
39}
40

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    // Function to compute the maximum subarray sum with exactly k unique elements
8    long long maximumSubarraySum(std::vector<int>& nums, int k) {
9        using ll = long long; // Alias for long long to simplify the code
10        int n = nums.size(); // Size of the input array
11        std::unordered_map<int, int> count; // Map to store the frequency of elements
12        ll sum = 0; // Initialize sum of the current subarray
13        // Initialize the window of size k
14        for (int i = 0; i < k; ++i) {
15            count[nums[i]]++; // Increment the frequency of the current element
16            sum += nums[i]; // Add the current element to the sum
17        }
18        // Initialize answer with the sum of the first window if it contains k unique elements
19        ll maxSum = count.size() == k ? sum : 0;
20        // Slide the window across the array
21        for (int i = k; i < n; ++i) {
22            count[nums[i]]++; // Increment frequency of the new element in the window
23            sum += nums[i]; // Add new element to current sum
24          
25            count[nums[i - k]]--; // Decrement frequency of the oldest element going out of the window
26            sum -= nums[i - k]; // Subtract this element from current sum
27            // If the oldest element frequency reaches 0, remove it from the count map
28            if (count[nums[i - k]] == 0) {
29                count.erase(nums[i - k]);
30            }
31            // Update maxSum if current window contains k unique elements
32            if (count.size() == k) {
33                maxSum = std::max(maxSum, sum);
34            }
35        }
36        // Return the maximum subarray sum with exactly k unique elements
37        return maxSum;
38    }
39};
40

1function maximumSubarraySum(nums: number[], k: number): number {
2    const n: number = nums.length;
3    const countMap: Map<number, number> = new Map();
4    let currentSum: number = 0;
5
6    // Initialize the count map and current sum with the first 'k' elements
7    for (let i: number = 0; i < k; ++i) {
8        countMap.set(nums[i], (countMap.get(nums[i]) ?? 0) + 1);
9        currentSum += nums[i];
10    }
11  
12    // Check if the first subarray of length 'k' has 'k' distinct numbers
13    let maxSum: number = countMap.size === k ? currentSum : 0;
14  
15    // Traverse the array starting from the 'k'th element
16    for (let i: number = k; i < n; ++i) {
17        // Add the next number to the count map and current sum
18        countMap.set(nums[i], (countMap.get(nums[i]) ?? 0) + 1);
19        currentSum += nums[i];
20
21        // Update the count map and current sum by removing the (i-k)'th number
22        const prevCount: number = countMap.get(nums[i - k])! - 1;
23        countMap.set(nums[i - k], prevCount);
24        currentSum -= nums[i - k];
25
26        // If after decrementing, the count is zero, remove it from the map
27        if (prevCount === 0) {
28            countMap.delete(nums[i - k]);
29        }
30
31        // If the current subarray has 'k' distinct elements, update maxSum
32        if (countMap.size === k) {
33            maxSum = Math.max(maxSum, currentSum);
34        }
35    }
36
37    // Return the maximum sum of a subarray with 'k' distinct numbers
38    return maxSum;
39}
40

Time and Space Complexity

The given Python code defines a method maximumSubarraySum within a class Solution to calculate the maximum sum of a subarray of size k with unique elements. The code uses a sliding window approach by keeping a counter for the number of occurrences of each element within the current window of size k and computes the sum of elements in the window.

Time Complexity:

The time complexity of the algorithm is O(n), where n is the total number of elements in the input list nums. This is because the code iterates through all the elements of nums once. For each element in the iteration, the time to update the cnt counter (Counter from the collections module) for the current window is constant on average due to the hash map data structure used internally. The operations inside the loop including incrementing, decrementing, deleting from the counter, and computing the sum are done in constant time. Since these operations are repeated for every element just once, it amounts to O(n).

Space Complexity:

The space complexity of the algorithm is O(k). The cnt counter maintains the count of elements within a sliding window of size k. In the worst-case scenario, if all elements within the window are unique, the counter will hold k key-value pairs. Hence, the amount of extra space used is proportional to the size of the window k.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know