Maximum Sum of Distinct Subarrays With Length K
Problem Description
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
Solve it on LeetCode
Approaches
1. Sliding Window with Brute Force
Intuition:
To find the maximum sum of distinct subarrays of a particular length ( K ), we can use a sliding window. However, a simple brute force approach involves generating all possible subarrays of length ( K ) and ensuring that each subarray consists of distinct elements. For each valid subarray, compute the sum and keep track of the maximum sum found.
Steps:
- Iterate over the array, building subarrays containing ( K ) elements.
- For each subarray, check if all the elements are distinct.
- If yes, compute the sum of the subarray. Update the maximum sum if it's larger than the current maximum.
- Return the maximum sum found.
Code:
- Time Complexity: O(n*k), where n is the length of the input array.
- Space Complexity: O(1) additional space if we consider the size of
visitedas a constant.
2. Sliding Window with HashSet
Intuition:
An improved approach still uses a sliding window but leverages a HashSet to maintain a set of distinct elements in the current window. This avoids the need to check distinctness explicitly for each subarray by allowing additions and removals of elements from the window in constant time.
Steps:
- Maintain a sliding window with two pointers, ( left ) and ( right ).
- Use a
HashSetto maintain the distinct elements within the current window. - Iterate over the array and attempt to build a window of size ( K ).
- If you've successfully built such a window with all distinct elements, compute the sum and update the maximum sum if necessary.
- Move the window by adjusting ( left ).
Code:
- Time Complexity: O(n), where n is the length of the input array.
- Space Complexity: O(k) for storing elements in the
HashSet.