Scale Engineer

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
ArrayHash 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 * 104
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 109

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

  1. Initialize maxSum to 0.
  2. Iterate through the array nums from index i = 0 to n - k.
  3. For each i, create a new HashSet and initialize currentSum to 0.
  4. Create a subarray of length k starting at i.
  5. Iterate through this subarray (from j = i to i + k - 1): a. Add nums[j] to the HashSet. b. Add nums[j] to currentSum.
  6. After iterating through the subarray, check if the size of the HashSet is greater than or equal to m.
  7. If it is, update maxSum = Math.max(maxSum, currentSum).
  8. 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.
import java.util.HashSet;import java.util.Set; class Solution {    public long maximumSubarraySum(int[] nums, int m, int k) {        long maxSum = 0;        int n = nums.length;         if (k > n) {            return 0;        }         for (int i = 0; i <= n - k; i++) {            Set<Integer> distinctElements = new HashSet<>();            long currentSum = 0;                        // Consider subarray nums[i...i+k-1]            for (int j = i; j < i + k; j++) {                distinctElements.add(nums[j]);                currentSum += nums[j];            }             // Check if the subarray is almost unique            if (distinctElements.size() >= m) {                maxSum = Math.max(maxSum, currentSum);            }        }        return maxSum;    }}

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.

Solutions

public class Solution {    public long MaxSum(IList < int > nums, int m, int k) {        Dictionary < int, int > cnt = new Dictionary < int, int > ();        int n = nums.Count;        long s = 0;        for (int i = 0; i < k; ++i) {            if (!cnt.ContainsKey(nums[i])) {                cnt[nums[i]] = 1;            } else {                cnt[nums[i]]++;            }            s += nums[i];        }        long ans = cnt.Count >= m ? s : 0;        for (int i = k; i < n; ++i) {            if (!cnt.ContainsKey(nums[i])) {                cnt[nums[i]] = 1;            } else {                cnt[nums[i]]++;            }            if (cnt.ContainsKey(nums[i - k])) {                cnt[nums[i - k]]--;                if (cnt[nums[i - k]] == 0) {                    cnt.Remove(nums[i - k]);                }            }            s += nums[i] - nums[i - k];            if (cnt.Count >= m) {                ans = Math.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 →

Next problem