Maximum Sum of Almost Unique Subarray solution and explanation
9 more videos on this problem
Leetcode BiWeekly contest 112 - Medium - Maximum Sum of Almost Unique SubarrayPrakhar Agrawal · 7:41 · 963 views
2841. Maximum Sum of Almost Unique Subarray | Harder Follow-ups | Leetcode Biweekly 112codingMohan · 33:00 · 689 views
2841. Maximum Sum of Almost Unique Subarray (Leetcode Medium)Programming Live with Larry · 12:09 · 336 views
Leetcode 2841 : Maximum Sum of Almost Unique Subarray (Medium)TechieGanesh · 10:12 · 103 views
6989. Maximum Sum of Almost Unique Subarray || Biweekly Contest 112 || LeetCode || HindiAshish Kumar · 6:44 · 93 views
leetcode 2841 [Google Q]. Maximum Sum of Almost Unique Subarray - dictADT, sliding windowCode-Yao · 11:40 · 54 views
LeetCode-2841-Maximum Sum of Almost Unique Subarrayyou jack · 6:03 · 50 views
Leetcode 2841. Maximum Sum of Almost Unique Subarray (fixed sliding window)LetsCode · 4:33 · 25 views
Maximum Sum of Almost Unique Subarray Solution || Leetcode Bi-Weekly 112Mighty Coding · 8:35 · 19 views
Leetcode 2841 Maximum Sum of Almost Unique SubarrayDev_God · 11:36 · 13 views
The problem
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:
Input: nums = [2,6,7,3,1,7], m = 3, k = 4
Output: 18
Explanation: There are 3 almost unique subarrays of size k = 4. These subarrays are [2, 6, 7, 3], [6, 7, 3, 1], and [7, 3, 1, 7]. Among these subarrays, the one with the maximum sum is [2, 6, 7, 3] which has a sum of 18.
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:
Input: nums = [1,2,1,2,1,2,1], m = 3, k = 3 Output: 0 Explanation: There are no subarrays of sizek = 3that contain at leastm = 3distinct elements in the given array [1,2,1,2,1,2,1]. Therefore, no almost unique subarrays exist, and the maximum sum is 0.
Constraints:
1 <= nums.length <= 2 * 1041 <= m <= k <= nums.length1 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array nums, a window size k, and a threshold m. Among all subarrays of length k, return the maximum possible sum where the subarray contains at least m distinct elements.
Approach 1: Brute Force with Optimization Check (O(n * k) time, O(k) space)
Iterate over every possible subarray of length k. For each starting index, compute the sum of the next k elements and track distinct values using a hash set or frequency map. If the number of unique elements is at least m, update the maximum sum. The optimization comes from stopping the distinct count early once the threshold is met, but the algorithm still scans up to k elements for each window. Time complexity is O(n * k) because each window requires up to k operations, and space complexity is O(k) to store element frequencies.
Approach 2: Sliding Window with HashMap (O(n) time, O(k) space)
This problem naturally fits a fixed-size sliding window. Maintain a window of size k while tracking the current sum and the frequency of elements in a HashMap. As you expand the window to the right, add the new element to the sum and update its frequency. When the window size exceeds k, remove the leftmost element, subtract it from the sum, and update its frequency (removing it from the map when the count reaches zero). The number of keys in the map represents the count of distinct elements. Each time the window size equals k, check whether the distinct count is at least m and update the maximum sum. Each element enters and leaves the window once, so the time complexity is O(n) and space complexity is O(k).
The sliding window approach works well because the window size never changes. Instead of recomputing sums and distinct counts from scratch, you update them incrementally when elements enter or leave the window. This reduces repeated work and turns a quadratic-style scan into a linear pass.
Recommended for interviews: Interviewers expect the sliding window solution. The brute force method shows you understand the constraint of fixed-length subarrays, but the optimal approach demonstrates your ability to apply sliding window techniques with a hash table to maintain dynamic counts in an array. Linear-time solutions using incremental updates are a common expectation for medium-level array problems.
Approach 1: Sliding Window with HashMap
In this approach, we utilize the sliding window technique along with a hashmap to track the frequency of elements within the current subarray window. As we slide the window, we maintain the count of distinct elements and the sum of the subarray. This allows us to efficiently check if the current subarray is almost unique.
def max_sum_almost_unique(nums, m, k):
from collections import defaultdict
max_sum, current_sum, left = 0, 0, 0
freq = defaultdict(int)
distinct_count = 0
for right in range(len(nums)):
if freq[nums[right]] == 0:
distinct_count += 1
freq[nums[right]] += 1
current_sum += nums[right]
if right - left + 1 > k:
freq[nums[left]] -= 1
if freq[nums[left]] == 0:
distinct_count -= 1
current_sum -= nums[left]
left += 1
if right - left + 1 == k and distinct_count >= m:
max_sum = max(max_sum, current_sum)
return max_sum
# Example usage
nums = [2, 6, 7, 3, 1, 7]
m = 3
k = 4
print(max_sum_almost_unique(nums, m, k))import java.util.HashMap;
public class MaxSumAlmostUnique {
public static int maxSumAlmostUnique(int[] nums, int m, int k) {
int maxSum = 0, currentSum = 0;
HashMap<Integer, Integer> freqMap = new HashMap<>();
int distinctCount = 0;
int left = 0;
for (int right = 0; right < nums.length; right++) {
freqMap.put(nums[right], freqMap.getOrDefault(nums[right], 0) + 1);
if (freqMap.get(nums[right]) == 1) {
distinctCount++;
}
currentSum += nums[right];
if ((right - left + 1) > k) {
freqMap.put(nums[left], freqMap.get(nums[left]) - 1);
if (freqMap.get(nums[left]) == 0) {
distinctCount--;
}
currentSum -= nums[left];
left++;
}
if ((right - left + 1) == k && distinctCount >= m) {
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {2, 6, 7, 3, 1, 7};
int m = 3, k = 4;
System.out.println(maxSumAlmostUnique(nums, m, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int maxSumAlmostUnique(vector<int>& nums, int m, int k) {
int maxSum = 0, currentSum = 0;
unordered_map<int, int> freq;
int distinctCount = 0;
int left = 0;
for (int right = 0; right < nums.size(); ++right) {
freq[nums[right]]++;
if (freq[nums[right]] == 1) {
distinctCount++;
}
currentSum += nums[right];
while (right - left + 1 > k) {
freq[nums[left]]--;
if (freq[nums[left]] == 0) {
distinctCount--;
}
currentSum -= nums[left];
left++;
}
if (right - left + 1 == k && distinctCount >= m) {
maxSum = max(maxSum, currentSum);
}
}
return maxSum;
}
int main() {
vector<int> nums = {2, 6, 7, 3, 1, 7};
int m = 3, k = 4;
cout << maxSumAlmostUnique(nums, m, k) << endl;
return 0;
}function maxSumAlmostUnique(nums, m, k) {
let maxSum = 0, currentSum = 0;
const freq = new Map();
let distinctCount = 0;
let left = 0;
for (let right = 0; right < nums.length; right++) {
if (!freq.has(nums[right])) {
freq.set(nums[right], 0);
}
if (freq.get(nums[right]) === 0) distinctCount++;
freq.set(nums[right], freq.get(nums[right]) + 1);
currentSum += nums[right];
if (right - left + 1 > k) {
freq.set(nums[left], freq.get(nums[left]) - 1);
if (freq.get(nums[left]) === 0) distinctCount--;
currentSum -= nums[left];
left++;
}
if (right - left + 1 === k && distinctCount >= m) {
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}
console.log(maxSumAlmostUnique([2, 6, 7, 3, 1, 7], 3, 4));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int maxSumAlmostUnique(int* nums, int numsSize, int m, int k) {
int maxSum = 0;
int currentSum = 0;
int distinctCount = 0;
int* freq = (int*)calloc(1000000001, sizeof(int));
int left = 0;
for (int right = 0; right < numsSize; right++) {
freq[nums[right]]++;
if (freq[nums[right]] == 1) {
distinctCount++;
}
currentSum += nums[right];
while (right - left + 1 > k) {
freq[nums[left]]--;
if (freq[nums[left]] == 0) {
distinctCount--;
}
currentSum -= nums[left];
left++;
}
if (right - left + 1 == k && distinctCount >= m) {
maxSum = max(maxSum, currentSum);
}
}
free(freq);
return maxSum;
}
int main() {
int nums[] = {2, 6, 7, 3, 1, 7};
int m = 3;
int k = 4;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", maxSumAlmostUnique(nums, numsSize, m, k));
return 0;
}using System;
using System.Collections.Generic;
public class MaxSumAlmostUnique {
public int MaxSumAlmostUniqueSubarray(int[] nums, int m, int k) {
int maxSum = 0, currentSum = 0;
var freq = new Dictionary<int, int>();
int distinctCount = 0;
int left = 0;
for (int right = 0; right < nums.Length; right++) {
if (!freq.ContainsKey(nums[right])) freq[nums[right]] = 0;
if (freq[nums[right]] == 0) distinctCount++;
freq[nums[right]]++;
currentSum += nums[right];
if (right - left + 1 > k) {
freq[nums[left]]--;
if (freq[nums[left]] == 0) distinctCount--;
currentSum -= nums[left];
left++;
}
if (right - left + 1 == k && distinctCount >= m) {
maxSum = Math.Max(maxSum, currentSum);
}
}
return maxSum;
}
public static void Main(string[] args) {
int[] nums = {2, 6, 7, 3, 1, 7};
int m = 3, k = 4;
Console.WriteLine(new MaxSumAlmostUnique().MaxSumAlmostUniqueSubarray(nums, m, k));
}
}This Python solution utilizes a defaultdict to manage frequencies, which simplifies checking if an element exists. The approach iteratively updates the window maintaining the 'almost unique' criteria.
Time Complexity: O(n), as it goes through each number once.
Space Complexity: O(m) for maintaining the frequency dictionary.
Approach 2: Brute Force with Optimization Check
For this approach, a more straightforward brute force method generates all subarrays of length k. However, optimizing by early exit from impossible subarrays can reduce some checks. The 'almost unique' condition is verified for each subarray explicitly.
def max_sum_almost_unique_brute_force(nums, m, k):
n = len(nums)
max_sum = 0
for i in range(n - k + 1):
subarray = nums[i:i + k]
if len(set(subarray)) >= m:
max_sum = max(max_sum, sum(subarray))
return max_sum
# Example usage
print(max_sum_almost_unique_brute_force([2, 6, 7, 3, 1, 7], 3, 4))import java.util.HashSet;
public class MaxSumAlmostUniqueBruteForce {
public static int maxSumAlmostUniqueBruteForce(int[] nums, int m, int k) {
int n = nums.length;
int maxSum = 0;
for (int i = 0; i <= n - k; i++) {
HashSet<Integer> distinctElements = new HashSet<>();
int sum = 0;
for (int j = i; j < i + k; j++) {
distinctElements.add(nums[j]);
sum += nums[j];
}
if (distinctElements.size() >= m) {
maxSum = Math.max(maxSum, sum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = {2, 6, 7, 3, 1, 7};
int m = 3;
int k = 4;
System.out.println(maxSumAlmostUniqueBruteForce(nums, m, k));
}
}The Python brute force solution checks every possible subarray of length k from nums. It uses a set to track distinct elements, helping in validating the almost unique condition of each generated subarray for aggregation.
Time Complexity: O(n*k), where each subarray is evaluated for sum and distinctness.
Space Complexity: O(k) due to the use of sets for maintaining distinct numbers.
Approach 3: Sliding Window + Hash Table
We can traverse the array nums, maintain a window of size k, use a hash table cnt to count the occurrence of each element in the window, and use a variable s to sum all elements in the window. If the number of different elements in cnt is greater than or equal to m, then we update the answer ans = max(ans, s).
After the traversal ends, return the answer.
The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the array.
function maxSum(nums: number[], m: number, k: number): number {
const n = nums.length;
const cnt: Map<number, number> = new Map();
let s = 0;
for (let i = 0; i < k; ++i) {
cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
s += nums[i];
}
let ans = cnt.size >= m ? s : 0;
for (let i = k; i < n; ++i) {
cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
cnt.set(nums[i - k], cnt.get(nums[i - k])! - 1);
if (cnt.get(nums[i - k]) === 0) {
cnt.delete(nums[i - k]);
}
s += nums[i] - nums[i - k];
if (cnt.size >= m) {
ans = Math.max(ans, s);
}
}
return ans;
}func maxSum(nums []int, m int, k int) int64 {
cnt := map[int]int{}
var s int64
for _, x := range nums[:k] {
cnt[x]++
s += int64(x)
}
var ans int64
if len(cnt) >= m {
ans = s
}
for i := k; i < len(nums); i++ {
cnt[nums[i]]++
cnt[nums[i-k]]--
if cnt[nums[i-k]] == 0 {
delete(cnt, nums[i-k])
}
s += int64(nums[i]) - int64(nums[i-k])
if len(cnt) >= m {
ans = max(ans, s)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with HashMap | Time Complexity: O(n), as it goes through each number once. |
| Brute Force with Optimization Check | Time Complexity: O(n*k), where each subarray is evaluated for sum and distinctness. |
| Sliding Window + Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Optimization Check | O(n * k) | O(k) | Useful for understanding the problem or when constraints are small |
| Sliding Window with HashMap | O(n) | O(k) | Best general solution for large arrays and interview settings |
Frequently asked questions
Is Maximum Sum of Almost Unique Subarray easy or hard?
Maximum Sum of Almost Unique Subarray is classified as a medium difficulty problem. The challenge comes from combining sliding window logic with frequency tracking to enforce the distinct element constraint efficiently.
Maximum Sum of Almost Unique Subarray Python/Java solution
Most implementations use the sliding window technique with a dictionary in Python or a HashMap in Java. The algorithm maintains a running sum and updates frequencies as the window moves. This keeps the solution linear with O(n) time complexity.
How to solve Maximum Sum of Almost Unique Subarray in O(n)?
Use a fixed-size sliding window of length k. Keep a running sum of the window and store element frequencies in a hash map. As the window moves forward, add the new element and remove the old one while updating frequencies. When the map contains at least m distinct keys, update the maximum sum.
What is the best approach for Maximum Sum of Almost Unique Subarray?
The most efficient approach uses a sliding window with a hash map. Maintain a fixed window of size k, track the running sum, and store element frequencies in the map to count distinct values. When the window has at least m unique elements, update the maximum sum. This approach runs in O(n) time and O(k) space.
Is Maximum Sum of Almost Unique Subarray asked at Google/Amazon/Meta?
Sliding window and hash map problems similar to this one frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that involve fixed-length subarrays, distinct element constraints, or maximum sum windows are common in technical screening rounds.
What data structure is used in Maximum Sum of Almost Unique Subarray?
The main data structure is a hash map (or dictionary) used to track the frequency of elements inside the sliding window. This allows constant-time updates when elements enter or leave the window while also keeping track of the number of distinct values.
What is the time complexity of Maximum Sum of Almost Unique Subarray?
The optimal sliding window solution runs in O(n) time because each element is added to and removed from the window at most once. Space complexity is O(k) due to the hash map storing frequencies of elements inside the current window.