Leetcode 2461: Maximum Sum of Distinct Subarrays With Length K
You are given an array of integers and an integer k. You need to find the maximum sum of all possible subarrays of length k, where all elements in the subarray are distinct. If no subarray meets the condition, return 0.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array nums and an integer k, where nums represents the array and k is the length of the subarray.
Example: nums = [1, 5, 4, 2, 9, 9, 9], k = 3
Constraints:
• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
Output: Return the maximum sum of all possible subarrays of length k where all elements are distinct. If no such subarray exists, return 0.
Example: For nums = [1, 5, 4, 2, 9, 9, 9], k = 3, the output is 15.
Constraints:
Goal: The goal is to calculate the maximum sum of all valid subarrays of length k where all elements are distinct.
Steps:
• 1. Initialize a sliding window to iterate over the array.
• 2. Maintain a hashmap to track the frequency of each element in the current window.
• 3. If the window size exceeds k or contains duplicates, adjust the window by removing elements from the left.
• 4. For each valid window of size k, calculate the sum and track the maximum sum.
Goal: The solution must handle arrays of size up to 100,000 efficiently.
Steps:
• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
Assumptions:
• The array will always have at least one element, and k will always be less than or equal to the length of the array.
• Input: nums = [1, 5, 4, 2, 9, 9, 9], k = 3
• Explanation: The subarrays of nums with length 3 are:
- [1, 5, 4], sum = 10 (valid)
- [5, 4, 2], sum = 11 (valid)
- [4, 2, 9], sum = 15 (valid)
- [2, 9, 9], sum = 20 (invalid, repeated 9)
- [9, 9, 9], sum = 27 (invalid, repeated 9)
The maximum sum of a valid subarray is 15.
Approach: We use a sliding window approach to evaluate each subarray of length k. For each window, we ensure that all elements are distinct. If the window is valid, we compute the sum and track the maximum sum.
Observations:
• The subarray must be of size k, and all elements in the subarray must be distinct.
• Using a sliding window technique allows us to efficiently evaluate subarrays of size k by adjusting the window as we traverse the array.
Steps:
• 1. Initialize the sliding window and a hashmap to store the frequency of elements in the window.
• 2. Traverse the array using the sliding window technique. For each element, add it to the window and update the frequency map.
• 3. If the window size exceeds k or contains duplicates, move the left pointer of the window to maintain the size and uniqueness.
• 4. For every valid window, calculate the sum and update the maximum sum.
Empty Inputs:
• The input array will never be empty, as the constraints guarantee at least one element.
Large Inputs:
• The algorithm should handle large inputs efficiently, with arrays up to 100,000 elements.
Special Values:
• If no subarray of length k has distinct elements, the function should return 0.
Constraints:
• The solution must operate within O(n) time complexity to handle the largest inputs.
long long maximumSubarraySum(vector<int>& nums, int k) {
long long sum = 0, ans = 0;
int n = nums.size(), j = 0;
map<int, int> mp;
for(int i = 0; i < n; i++) {
sum += nums[i];
mp[nums[i]]++;
while(i - j + 1 > k || mp[nums[i]] > 1) {
mp[nums[j]]--;
sum -= nums[j];
j++;
}
if((i - j + 1) == k) {
ans = max(sum, ans);
}
}
return ans;
}
1 : Function Definition
long long maximumSubarraySum(vector<int>& nums, int k) {
Defines the function to compute the maximum sum of a subarray of size `k`.
2 : Variable Initialization
long long sum = 0, ans = 0;
Initializes variables to track the current sum and the maximum sum found.
3 : Array Size
int n = nums.size(), j = 0;
Calculates the size of the input array and initializes a pointer `j` for the sliding window.
4 : Map Initialization
map<int, int> mp;
Defines a map to count the frequency of elements in the current sliding window.
5 : Loop Start
for(int i = 0; i < n; i++) {
Begins the loop to iterate through the array with index `i`.
6 : Update Sum
sum += nums[i];
Adds the current element to the running sum.
7 : Update Frequency Map
mp[nums[i]]++;
Increments the frequency count of the current element in the map.
8 : Sliding Window Adjustment
while(i - j + 1 > k || mp[nums[i]] > 1) {
Adjusts the window size or removes duplicates when the subarray size exceeds `k` or contains duplicates.
9 : Decrement Frequency
mp[nums[j]]--;
Decrements the frequency count of the element being removed from the sliding window.
10 : Update Sum After Removal
sum -= nums[j];
Subtracts the value of the removed element from the running sum.
11 : Increment Window Start
j++;
Moves the start of the sliding window forward by one.
12 : Check Subarray Size
if((i - j + 1) == k) {
Checks if the current window size is exactly `k`.
13 : Update Maximum
ans = max(sum, ans);
Updates the maximum sum if the current sum is greater.
14 : Return Result
return ans;
Returns the maximum sum of any valid subarray of size `k`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only need to iterate over the array once and adjust the sliding window as needed.
Best Case: O(k)
Worst Case: O(k)
Description: The space complexity is O(k) due to the hashmap used to store the elements in the sliding window.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus