Maximum Sum of Almost Unique Subarray
Medium · Sliding Window · Array · Hash Table · Sliding Window
Problem
You are given an integer array nums and two positive integers m and k. A subarray of length k is almost unique when it contains at least m distinct values.
Return the largest sum of any almost unique subarray of length k, or 0 if there is none. A subarray is a contiguous, non-empty part of the array.
Examples
Input: nums = [2,6,7,3,1,7], m = 3, k = 4 Output: 18
[2,6,7,3] (4 distinct values) and [7,3,1,7] (3 distinct) both sum to 18; [6,7,3,1] sums to 17.
Input: nums = [5,9,9,2,4,5,4], m = 1, k = 3 Output: 23
Any window has at least one distinct value. The best is [5,9,9] with sum 23.
Input: nums = [1,2,1,2,1], m = 3, k = 3 Output: 0
Every window of length 3 has only two distinct values, so the answer is 0.
Constraints
- 1 <= len(nums) <= 2 · 10^4
- 1 <= m <= k <= len(nums)
- 1 <= nums[i] <= 10^9
Approaches
- Recompute every window — time O(n · k), space O(k)
Follow-up
What if the window length is free and you want the longest subarray with at most m distinct values? Then the window grows on the right and shrinks on the left whenever it has too many keys: the same count map, with a variable window instead of a fixed one.
Related problems
Start free on Cariara · Coding problems · System design studio
