• Leetcode POTDs

Problem 2461 Maximum Sum of Distinct Subarrays With Length K

Problem Statement

Link - Problem 2461

Question

You are given an integer array nums and an integer k. Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

• The length of the subarray is k, and
• All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105

Solution

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long ans = 0;
        long long curr_sum = 0;
        unordered_map<int, int> freq;

        for (int i = 0; i < nums.size(); ++i) {
            curr_sum += nums[i];
            freq[nums[i]]++;

            if (i >= k) {
                int to_remove = nums[i - k];
                curr_sum -= to_remove;
                freq[to_remove]--;

                if (freq[to_remove] == 0) {
                    freq.erase(to_remove);
                }
            }

            if (freq.size() == k) {
                ans = max(ans, curr_sum);
            }
        }

        return ans;
    }
};

Complexity Analysis

| Algorithm                   | Time Complexity | Space Complexity |
| --------------------------- | --------------- | ---------------- |
| Sliding Window with Hashing | O(n)            | O(min(n, k))     |

Explanation

1. Intuition

• The problem requires finding the maximum subarray sum of all subarrays of length k with distinct elements.
• To solve this problem, we can use a sliding window approach to efficiently calculate the sum of subarrays.
• We need to keep track of the frequency of elements in the current window to ensure all elements are distinct.
• Using an unordered_map to store the frequency of elements allows for efficient insertion and deletion of elements.
• The maximum subarray sum is updated whenever we find a window with k distinct elements.
• This approach ensures that we consider all possible subarrays of length k with distinct elements.
• The time complexity of this approach is O(n), where n is the length of the input array.

2. Implementation

• We initialize variables ans to store the maximum subarray sum, curr_sum to store the sum of the current window, and freq to store the frequency of elements in the current window.
• We iterate over the input array using a for loop, and for each element, we add it to curr_sum and increment its frequency in freq.
• If the window size exceeds k, we remove the leftmost element from curr_sum and decrement its frequency in freq.
• If the frequency of an element becomes 0, we remove it from freq to ensure efficient lookup.
• We update ans with the maximum of ans and curr_sum whenever the size of freq equals k.
• Finally, we return ans as the maximum subarray sum.
• The use of unordered_map allows for efficient insertion and deletion of elements, making the overall time complexity O(n).

Complexity Analysis

Time Complexity:

• The algorithm iterates over the input array (for (int i = 0; i < nums.size(); ++i)), resulting in a time complexity directly proportional to the size of the input array.
• Within the loop, each element is processed a constant number of times: added to curr_sum and updated in the freq hash table (curr_sum += nums[i];, freq[nums[i]]++).
• Since these operations occur once for each element, and the hash table operations take average O(1) time, the overall time complexity is O(n), where n is the number of elements in the input array.

Space Complexity:

• The input array is not modified or copied; the additional memory used comes from the freq unordered_map, storing frequency of elements within the current window.
• In the worst case, if all elements in the window are unique, the size of the frequency map can grow up to k elements, hence the space complexity is O(min(n, k))
• In practice, this will usually be closer to the value of k, as the algorithm enforces a fixed window size.

Footnote

This question is rated as Medium difficulty.

Hints

Which elements change when moving from the subarray of size k that ends at index i to the subarray of size k that ends at index i + 1?

Only two elements change, the element at i + 1 is added into the subarray, and the element at i - k + 1 gets removed from the subarray.

Iterate through each subarray of size k and keep track of the sum of the subarray and the frequency of each element.

Similar Questions: