2461. Maximum Sum of Distinct Subarrays With Length K

Maximum Sum of Distinct Subarrays With Length K (LeetCode 2461) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Variable Size (Condition-Based) subpattern.

How to solve Maximum Sum of Distinct Subarrays With Length K

Maximum Sum of Distinct Subarrays With Length K is a Variable Size Sliding Window problem, part of Sliding Window. Master variable-size sliding window for condition-based problems like longest substring without repeating characters.

Work towards the solution in these steps:

1. 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?
2. 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.
3. Iterate through each subarray of size k and keep track of the sum of the subarray and the frequency of each element.

The reference solution runs in O(n) time and O(k) space.

The Maximum Sum of Distinct Subarrays With Length K solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Array, Hash Table, Sliding Window.

How to practise Maximum Sum of Distinct Subarrays With Length K on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(k) space.

Open Maximum Sum of Distinct Subarrays With Length K in the code editor, or read the Maximum Sum of Distinct Subarrays With Length K editorial for a worked solution with its approach and complexity analysis.

Where Maximum Sum of Distinct Subarrays With Length K sits in the DSA pattern sheet

• Sliding Window pattern guide
• Variable Size (Condition-Based) subpattern
• The full DSA patterns sheet

Problems related to Maximum Sum of Distinct Subarrays With Length K

Other problems that use the same Variable Size (Condition-Based) and Sliding Window techniques:

• Contains Duplicate II — Easy, same subpattern
• Continuous Subarrays — Medium, same subpattern
• Find Longest Special Substring That Occurs Thrice I — Medium, same subpattern
• Frequency of the Most Frequent Element — Medium, same subpattern
• Fruit Into Baskets — Medium, same subpattern
• Jump Game VII — Medium, same subpattern

Maximum Sum of Distinct Subarrays With Length K FAQ