We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Sum of Almost Unique Subarray

Number: 2954

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums and two positive integers m and k, find the maximum sum among all subarrays of length k that are "almost unique", meaning that the subarray contains at least m distinct elements. If no subarray meets the criteria, return 0.

Key Insights

  • Use a sliding window of fixed size k to iterate over the array.
  • Maintain a frequency map (hash table) to track the counts of elements within the window.
  • Track the total sum and the number of distinct elements as you slide the window.
  • When removing the old element from the window, update the frequency map and distinct count accordingly.
  • Only update the maximum sum when the current window satisfies the condition (distinct count >= m).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, because we slide the window in one pass. Space Complexity: O(k) in the worst case, due to the frequency map tracking elements in the current window.

Solution

Use the sliding window technique to efficiently inspect all subarrays of length k. Start by initializing the first window by computing the sum and frequency map for the first k elements. For every subsequent window, remove the effect of the outgoing element and add the new incoming element, adjusting the frequency map and distinct counter accordingly. If the window has at least m distinct elements, update a running maximum for the sum. The trick is carefully managing the frequency map when elements leave the window (decrementing counts and possibly reducing the distinct count) while maintaining the total sum quickly without needing to recalculate from scratch.

Code Solutions

def max_sum_almost_unique(nums, m, k):
    # Edge case
    n = len(nums)
    if n < k:
        return 0

    # Initialize frequency map, distinct counter and current sum for the first window
    freq = {}
    current_sum = 0
    distinct_count = 0
    for i in range(k):
        current_sum += nums[i]
        if nums[i] in freq:
            freq[nums[i]] += 1
        else:
            freq[nums[i]] = 1
            distinct_count += 1

    max_sum = current_sum if distinct_count >= m else 0

    # Slide the window through the rest of the array
    for i in range(1, n - k + 1):
        # Remove the left element of previous window
        left = nums[i - 1]
        freq[left] -= 1
        if freq[left] == 0:
            distinct_count -= 1
            del freq[left]
        current_sum -= left

        # Add the new right element into the current window
        right = nums[i + k - 1]
        current_sum += right
        if right in freq:
            freq[right] += 1
        else:
            freq[right] = 1
            distinct_count += 1

        # Check if current window satisfies the condition and update max sum
        if distinct_count >= m:
            max_sum = max(max_sum, current_sum)

    return max_sum

# Example usage:
print(max_sum_almost_unique([2,6,7,3,1,7], 3, 4))  # Expected output: 18
← Back to All Questions