Sliding Window
Max Sum of Distinct Subarrays Length k
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given an integer array nums and an integer k, write a function to identify the highest possible sum of a subarray within nums, where the subarray meets the following criteria: its length is k, and all of its elements are unique. If no such subarray exists, return 0.
Example 1: Input:
nums = [3, 2, 2, 3, 4, 6, 7, 7, -1] k = 4
Output:
20
Explanation: The subarrays of nums with length 4 are:
[3, 2, 2, 3] # elements 3 and 2 are repeated. [2, 2, 3, 4] # element 2 is repeated. [2, 3, 4, 6] # meets the requirements and has a sum of 15. [3, 4, 6, 7] # meets the requirements and has a sum of 20. [4, 6, 7, 7] # element 7 is repeated. [6, 7, 7, -1] # element 7 is repeated.
We return 20 because it is the maximum subarray sum of all the subarrays that meet the conditions.
Example 2: Input:
nums = [5, 5, 5, 5, 5] k = 3
Output:
0
Explanation: Every subarray of length 3 contains duplicate elements, so no valid subarray exists. Return 0.
Explanation
This solution uses a fixed-length sliding window to iterate over all subarrays of length k in O(n) time and O(k) space. For each subarray of length k, we check if all elements are distinct. If they are, then we compute the sum of the subarray and compare it to the maximum sum we have seen so far, and return the maximum sum at the end.
We represent the state of the current window using two variables:
- curr_sum: The sum of all elements in the window.
- state: A dictionary mapping each element in the window to the number of times it appears in the window.
We use a for-loop to iterate through each element in nums. For each element, we increment its count in state and add its value to curr_sum. We do this until the window reaches size k:
Visualization
def maxSum(nums, k):max_sum = float("-inf")start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return 0 if max_sum == float("-inf") else max_sum
start
max sum distinct subarrays of size k
0 / 5
Expanding window until it reaches size k = 4
Each time the window is of size k, we check if the window contains all distinct elements by comparing the length of state to k (if len(state) == k, then all elements in the window are distinct):
If it is, then we compare curr_sum to max_sum and update max_sum if curr_sum is greater.
We then prepare for the next iteration by contracting the window, which involves decrementing the count of the leftmost element in the window and removing it from state if its count is 0. We also subtract the leftmost element from curr_sum. This allows us to maintain the fixed length of the window.
Visualization
def maxSum(nums, k):max_sum = float("-inf")start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return 0 if max_sum == float("-inf") else max_sum
curr_sum: 10
start: 0 | end: 3
expand window
0 / 4
Expanding and contracting the window until first valid subarray is found
We do this until the window reaches the end of nums and return max_sum at the end.
Visualization
def maxSum(nums, k):max_sum = float("-inf")start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return 0 if max_sum == float("-inf") else max_sum
curr_sum: 15
start: 2 | end: 5
expand window
0 / 10
Expanding and contracting the window until the end of the array.
Example Input 2
Let's look at an edge case: nums = [5, 5, 5, 5, 5] and k = 3.
At first glance, you might think the answer is 15 (since 5 + 5 + 5 = 15). But remember, the problem asks for the maximum sum of subarrays with distinct elements only.
In this case, every subarray of length 3 contains duplicate elements:
- [5, 5, 5] - all three elements are the same (not distinct)
- [5, 5, 5] - still all duplicates
- [5, 5, 5] - same issue
Since no subarray of length 3 contains all distinct elements, we can't sum any of them. The answer is 0.
Solution
Visualization
Try these examples:
def maxSum(nums, k):max_sum = float("-inf")start = 0state = {}curr_sum = 0for end in range(len(nums)):curr_sum = curr_sum + nums[end]state[nums[end]] = state.get(nums[end], 0) + 1if end - start + 1 == k:if len(state) == k:max_sum = max(max_sum, curr_sum)curr_sum = curr_sum - nums[start]state[nums[start]] = state[nums[start]] - 1if state[nums[start]] == 0:del state[nums[start]]start += 1return 0 if max_sum == float("-inf") else max_sum
start
max sum distinct subarrays of size k
0 / 19
Mark as read
Your account is free and you can post anonymously if you choose.