2461. Maximum Sum of Distinct Subarrays With Length K

Explanation

To solve this problem, we can use a sliding window approach with a HashSet to keep track of distinct elements in the current window. We will iterate through the array, maintaining a window of size k and calculating the sum of elements in the window as long as all elements are distinct. If we encounter a duplicate element, we will slide the window to the right until the duplicate element is no longer in the window.

At each step, we update the maximum sum of distinct subarrays encountered so far. Finally, we return the maximum sum found.

Time complexity: O(n), where n is the number of elements in the array nums.
Space complexity: O(k), where k is the size of the HashSet representing the window.

View Leetcode Problem

import java.util.HashSet;

class Solution {
    public int maxSumOfDistinctSubarrays(int[] nums, int k) {
        int n = nums.length;
        int maxSum = 0;
        int sum = 0;
        HashSet<Integer> set = new HashSet<>();
        
        for (int i = 0, j = 0; j < n; j++) {
            while (set.contains(nums[j])) {
                sum -= nums[i];
                set.remove(nums[i]);
                i++;
            }
            sum += nums[j];
            set.add(nums[j]);
            
            if (j - i + 1 == k) {
                maxSum = Math.max(maxSum, sum);
                sum -= nums[i];
                set.remove(nums[i]);
                i++;
            }
        }
        
        return maxSum;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.