Skip to main content
Talentd

Maximum Sum of Almost Unique Subarray - Solution & Explanation

MediumArrayHash TableSliding Window15 min readAsked at: Amazon
Practice this problem

Problem Statement

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 size k = 3 that contain at least m = 3 distinct 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 * 104
  • 1 <= m <= k <= nums.length
  • 1 <= 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.

The C solution uses a frequency array to track occurrences of elements within the sliding window. If the window exceeds size k, we shrink it from the left. We check the distinct element count to ensure the 'almost unique' condition is met before calculating the sum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the array due to the sliding window mechanism.
Space Complexity: O(1) if we consider fixed maximum value range, otherwise O(m) where m is the number of unique integers in the range.

Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window with HashMap

Time Complexity: O(n) where n is the length of the array due to the sliding window mechanism.
Space Complexity: O(1) if we consider fixed maximum value range, otherwise O(m) where m is the number of unique integers in the range.

Brute Force with Optimization Check

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.

Sliding Window + Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with Optimization CheckO(n * k)O(k)Useful for understanding the problem or when constraints are small
Sliding Window with HashMapO(n)O(k)Best general solution for large arrays and interview settings

Video Solution

Leetcode BiWeekly contest 112 - Medium - Maximum Sum of Almost Unique Subarray • Prakhar Agrawal • 963 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Sum of Almost Unique Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays