Maximum Sum of Almost Unique Subarray

Med

#2540Time: O(n * k), where `n` is the length of `nums`. The outer loop runs `n-k+1` times, and for each iteration, we loop `k` times to build the set and calculate the sum. This results in a quadratic time complexity in the worst case (when `k` is proportional to `n`).Space: O(k), as we use a `HashSet` to store up to `k` elements for each subarray.

Patterns

Sliding Window

Data structures

Array Hash Table

Prompt

You are given an integer array nums and two positive integers m and k.

Return the maximum sum out of all almost unique subarrays of length k of nums. If no such subarray exists, return 0.

A subarray of nums is almost unique if it contains at least m distinct elements.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

k = 4

Example 2:

Input: nums = [5,9,9,2,4,5,4], m = 1, k = 3
Output: 23
Explanation: There are 5 almost unique subarrays of size k. These subarrays are [5, 9, 9], [9, 9, 2], [9, 2, 4], [2, 4, 5], and [4, 5, 4]. Among these subarrays, the one with the maximum sum is [5, 9, 9] which has a sum of 23.

Example 3:

k = 3

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= m <= k <= nums.length
1 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through all possible subarrays of length k. For each subarray, we check if it meets the 'almost unique' criteria (at least m distinct elements) and, if so, calculate its sum. We keep track of the maximum sum found across all valid subarrays.

Algorithm

Initialize maxSum to 0.
Iterate through the array nums from index i = 0 to n - k.
For each i, create a new HashSet and initialize currentSum to 0.
Create a subarray of length k starting at i.
Iterate through this subarray (from j = i to i + k - 1): a. Add nums[j] to the HashSet. b. Add nums[j] to currentSum.
After iterating through the subarray, check if the size of the HashSet is greater than or equal to m.
If it is, update maxSum = Math.max(maxSum, currentSum).
After the outer loop finishes, return maxSum.

Walkthrough

The brute-force method systematically examines every contiguous subarray of the specified length k.

We use a loop that starts from the first element and ends at the last possible starting position for a subarray of length k (nums.length - k).
Inside this loop, for each starting position i, we form a subarray nums[i...i+k-1].
To determine if this subarray is 'almost unique', we use a HashSet. We populate the set with the elements of the current subarray. The size of the HashSet gives us the count of distinct elements.
If the count of distinct elements is m or more, we proceed to calculate the sum of the elements in this subarray.
This sum is then compared with a running maximum, which is updated if the current sum is greater.
After checking all possible subarrays, the final maximum sum is returned. If no 'almost unique' subarray is found, the initial maximum sum of 0 is returned.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public long maximumSubarraySum(int[] nums, int m, int k) {6        long maxSum = 0;7        int n = nums.length;8 9        if (k > n) {10            return 0;11        }12 13        for (int i = 0; i <= n - k; i++) {14            Set<Integer> distinctElements = new HashSet<>();15            long currentSum = 0;16            17            // Consider subarray nums[i...i+k-1]18            for (int j = i; j < i + k; j++) {19                distinctElements.add(nums[j]);20                currentSum += nums[j];21            }22 23            // Check if the subarray is almost unique24            if (distinctElements.size() >= m) {25                maxSum = Math.max(maxSum, currentSum);26            }27        }28        return maxSum;29    }30}

Complexity

Time

O(n * k), where `n` is the length of `nums`. The outer loop runs `n-k+1` times, and for each iteration, we loop `k` times to build the set and calculate the sum. This results in a quadratic time complexity in the worst case (when `k` is proportional to `n`).

Space

O(k), as we use a `HashSet` to store up to `k` elements for each subarray.

Trade-offs

Pros

Simple to conceptualize and implement.
Correct for all cases, though not efficient.

Cons

Highly inefficient due to redundant calculations.
The time complexity of O(n*k) will lead to a 'Time Limit Exceeded' (TLE) error on larger test cases.

A more efficient approach is to use a sliding window of size k. Instead of re-calculating the sum and distinct elements for each subarray, we maintain these values as the window slides across the array. We add the new element entering the window and remove the element leaving it, updating the sum and the count of distinct elements in constant time on average.

Algorithm

Initialize maxSum = 0, currentSum = 0, and a HashMap called freqMap to store element frequencies.
Create the initial window of the first k elements: a. Iterate from i = 0 to k-1. b. Add nums[i] to currentSum. c. Update the frequency of nums[i] in freqMap.
Check if the initial window is 'almost unique' (freqMap.size() >= m). If so, set maxSum = currentSum.
Slide the window across the rest of the array, from i = k to n-1: a. Add the new element nums[i] to the window: currentSum += nums[i] and update its count in freqMap. b. Remove the leftmost element nums[i-k] from the window: currentSum -= nums[i-k] and decrement its count in freqMap. c. If the count of nums[i-k] becomes 0 after decrementing, remove it from freqMap. d. Check if the current window is 'almost unique' (freqMap.size() >= m). If so, update maxSum = Math.max(maxSum, currentSum).
Return maxSum.

Walkthrough

This optimized method avoids the repeated work of the brute-force approach by using a sliding window.

We maintain a window of size k and a HashMap to store the frequency of each number within that window. The size of the HashMap directly tells us the number of distinct elements.
We also keep a running sum of the elements in the window.
First, we initialize the window with the first k elements of the array. We calculate their sum and populate the frequency map. We check if this initial window is 'almost unique' and update our maximum sum if it is.
Then, we iterate from the k-th element to the end of the array. In each step, we 'slide' the window one position to the right:
1. Add new element: The element at the right end of the new window (nums[i]) is added. We update the sum and its frequency in the map.
2. Remove old element: The element that just left the window from the left end (nums[i-k]) is removed. We update the sum and its frequency. If its frequency becomes zero, we remove the element from the map entirely to keep the map's size accurate for the distinct count.
After each slide, we check if the number of distinct elements (the map's size) is at least m. If it is, we compare the current window's sum with our overall maximum sum and update it if necessary.
This process continues until the window has passed over the entire array.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public long maximumSubarraySum(int[] nums, int m, int k) {6        long maxSum = 0;7        long currentSum = 0;8        int n = nums.length;9        Map<Integer, Integer> freqMap = new HashMap<>();10 11        // Initialize the first window12        for (int i = 0; i < k; i++) {13            currentSum += nums[i];14            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);15        }16 17        // Check the first window18        if (freqMap.size() >= m) {19            maxSum = currentSum;20        }21 22        // Slide the window from k to the end23        for (int i = k; i < n; i++) {24            // Add the new element to the window25            currentSum += nums[i];26            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);27 28            // Remove the element that is leaving the window29            int oldElement = nums[i - k];30            currentSum -= oldElement;31            freqMap.put(oldElement, freqMap.get(oldElement) - 1);32            if (freqMap.get(oldElement) == 0) {33                freqMap.remove(oldElement);34            }35 36            // Check if the current window is almost unique37            if (freqMap.size() >= m) {38                maxSum = Math.max(maxSum, currentSum);39            }40        }41 42        return maxSum;43    }44}

Complexity

Time

O(n), where `n` is the length of `nums`. We iterate through the array once. The HashMap operations (get, put, remove) take O(1) on average.

Space

O(k), as the `HashMap` stores at most `k` distinct elements from the window.

Trade-offs

Pros

Optimal time complexity of O(n).
Efficiently reuses calculations from the previous window.
Passes all test cases within the time limit.

Cons

Slightly more complex to implement due to managing the sliding window state (sum and frequency map).

Solutions

Solution

1public class Solution {2    public long MaxSum(IList < int > nums, int m, int k) {3        Dictionary < int, int > cnt = new Dictionary < int, int > ();4        int n = nums.Count;5        long s = 0;6        for (int i = 0; i < k; ++i) {7            if (!cnt.ContainsKey(nums[i])) {8                cnt[nums[i]] = 1;9            } else {10                cnt[nums[i]]++;11            }12            s += nums[i];13        }14        long ans = cnt.Count >= m ? s : 0;15        for (int i = k; i < n; ++i) {16            if (!cnt.ContainsKey(nums[i])) {17                cnt[nums[i]] = 1;18            } else {19                cnt[nums[i]]++;20            }21            if (cnt.ContainsKey(nums[i - k])) {22                cnt[nums[i - k]]--;23                if (cnt[nums[i - k]] == 0) {24                    cnt.Remove(nums[i - k]);25                }26            }27            s += nums[i] - nums[i - k];28            if (cnt.Count >= m) {29                ans = Math.Max(ans, s);30            }31        }32        return ans;33    }34}

1class Solution {2public3  long maxSum(List<Integer> nums, int m, int k) {4    Map<Integer, Integer> cnt = new HashMap<>();5    int n = nums.size();6    long s = 0;7    for (int i = 0; i < k; ++i) {8      cnt.merge(nums.get(i), 1, Integer : : sum);9      s += nums.get(i);10    }11    long ans = 0;12    if (cnt.size() >= m) {13      ans = s;14    }15    for (int i = k; i < n; ++i) {16      cnt.merge(nums.get(i), 1, Integer : : sum);17      if (cnt.merge(nums.get(i - k), -1, Integer : : sum) == 0) {18        cnt.remove(nums.get(i - k));19      }20      s += nums.get(i) - nums.get(i - k);21      if (cnt.size() >= m) {22        ans = Math.max(ans, s);23      }24    }25    return ans;26  }27}

1class Solution {2public:3  long long maxSum(vector<int> &nums, int m, int k) {4    unordered_map<int, int> cnt;5    long long s = 0;6    int n = nums.size();7    for (int i = 0; i < k; ++i) {8      cnt[nums[i]]++;9      s += nums[i];10    }11    long long ans = cnt.size() >= m ? s : 0;12    for (int i = k; i < n; ++i) {13      cnt[nums[i]]++;14      if (--cnt[nums[i - k]] == 0) {15        cnt.erase(nums[i - k]);16      }17      s += nums[i] - nums[i - k];18      if (cnt.size() >= m) {19        ans = max(ans, s);20      }21    }22    return ans;23  }24};

1class Solution:2    def maxSum(self, nums: List[int], m: int, k: int) -> int: cnt = Counter(nums[: k]) s = sum(nums[: k]) ans = 0 if len(cnt) >= m: ans = s for i in range(k, len(nums)): cnt[nums[i]] += 1 cnt[nums[i - k]] -= 1 s += nums[i] - nums[i - k] if cnt[nums[i - k]] == 0: cnt . pop(nums[i - k]) if len(cnt) >= m: ans = max(ans, s) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem