Daily DSA: Sliding Window Maximum Unique Subsegment (Medium)
Advertisement
Problem Statement
You are given an array of integers nums and an integer k. Your goal is to find the maximum sum of a contiguous subsegment (subarray) of nums of length at most k such that all elements within the subsegment are distinct. If no such subsegment exists, return 0.
Examples
Example 1:
- Input:
nums = [1, 2, 1, 3, 2],k = 3 - Output:
6 - Explanation: The subsegment
[1, 3, 2]has length 3 (which is $\le 3$), all elements are unique, and its sum is1 + 3 + 2 = 6. Another valid subsegment is[2, 1, 3]with sum2 + 1 + 3 = 6.
Example 2:
- Input:
nums = [4, 4, 4, 4],k = 2 - Output:
4 - Explanation: Subsegments of length at most 2 with all distinct elements are single elements like
[4]. The maximum sum is4.
Example 3:
- Input:
nums = [1, 2, 3, 4, 5],k = 3 - Output:
12 - Explanation: The subsegment
[3, 4, 5]has length 3, distinct elements, and a sum of3 + 4 + 5 = 12.
Constraints
- $1 \le nums.length \le 10^5$
- $1 \le k \le nums.length$
- $-10^4 \le nums[i] \le 10^4$
Approach / Hint
- Sliding Window + Hash Map: Use a variable-size sliding window defined by a left pointer
Land a right pointerR. Maintain a frequency map or hash table to track the elements currently inside the window. - Window Constraints:
- The window size (
R - L + 1) must not exceedk. - All elements in the window must be unique (i.e., no elementโs frequency exceeds
1).
- The window size (
- Shrinking Strategy: As you expand
Rand addnums[R]to the window and its sum, if the window size exceedskor ifnums[R]already appears more than once, incrementL(subtractingnums[L]from the sum and updating the frequency map) until both conditions are satisfied. - Tracking Maximum: Keep a running maximum of the window sums whenever the window satisfies all conditions.
C++ Solution
#include <vector>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
long long maximumUniqueSubarraySum(std::vector<int>& nums, int k) {
std::unordered_map<int, int> count;
long long max_sum = 0;
long long current_sum = 0;
int L = 0;
for (int R = 0; R < nums.size(); ++R) {
count[nums[R]]++;
current_sum += nums[R];
// Shrink window if it violates the maximum length k
// or contains duplicate elements
while ((R - L + 1) > k || count[nums[R]] > 1) {
count[nums[L]]--;
current_sum -= nums[L];
L++;
}
max_sum = std::max(max_sum, current_sum);
}
return max_sum;
}
};
Complexity Analysis
- Time Complexity: $\mathcal{O}(N)$ where $N$ is the number of elements in
nums. Each element is visited at most twice (once byRand once byL). - Space Complexity: $\mathcal{O}(min(N, k))$ to store the frequency map of elements in the current window.
Advertisement