Maximum Sum of Almost Unique Subarray

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. For example:

Example 1: Input: nums = [2,6,7,3,1,7], m = 3, k = 4 Output: 18

Example 2: Input: nums = [5,9,9,2,4,5,4], m = 1, k = 3 Output: 23

Example 3: Input: nums = [1,2,1,2,1,2,1], m = 3, k = 3 Output: 0

def max_sum_almost_unique_subarray(nums, m, k):
    """Finds the maximum sum out of all almost unique subarrays of length k of nums.

    Args:
        nums: An integer array.
        m: A positive integer representing the minimum number of distinct elements required.
        k: A positive integer representing the length of the subarray.

    Returns:
        The maximum sum of an almost unique subarray of length k, or 0 if none exists.
    """
    n = len(nums)
    if k > n:
        return 0

    max_sum = 0

    for i in range(n - k + 1):
        subarray = nums[i:i+k]
        distinct_count = len(set(subarray))

        if distinct_count >= m:
            current_sum = sum(subarray)
            max_sum = max(max_sum, current_sum)

    return max_sum

# Example Usage
nums1 = [2, 6, 7, 3, 1, 7]
m1 = 3
k1 = 4
print(f"Example 1: {max_sum_almost_unique_subarray(nums1, m1, k1)}")  # Output: 18

nums2 = [5, 9, 9, 2, 4, 5, 4]
m2 = 1
k2 = 3
print(f"Example 2: {max_sum_almost_unique_subarray(nums2, m2, k2)}")  # Output: 23

nums3 = [1, 2, 1, 2, 1, 2, 1]
m3 = 3
k3 = 3
print(f"Example 3: {max_sum_almost_unique_subarray(nums3, m3, k3)}")  # Output: 0


# Optimal Solution
def max_sum_almost_unique_subarray_optimal(nums, m, k):
    n = len(nums)
    if k > n:
        return 0

    max_sum = 0
    window_sum = 0
    window_counts = {}
    distinct_count = 0

    # Initialize the window
    for i in range(k):
        if nums[i] not in window_counts:
            window_counts[nums[i]] = 0
            distinct_count += 1
        window_counts[nums[i]] += 1
        window_sum += nums[i]

    if distinct_count >= m:
        max_sum = window_sum

    # Slide the window
    for i in range(k, n):
        # Remove the leftmost element
        left_element = nums[i - k]
        window_counts[left_element] -= 1
        window_sum -= left_element

        if window_counts[left_element] == 0:
            del window_counts[left_element]
            distinct_count -= 1

        # Add the rightmost element
        right_element = nums[i]
        if right_element not in window_counts:
            window_counts[right_element] = 0
            distinct_count += 1
        window_counts[right_element] += 1
        window_sum += right_element

        if distinct_count >= m:
            max_sum = max(max_sum, window_sum)

    return max_sum


print(f"Example 1 Optimal: {max_sum_almost_unique_subarray_optimal(nums1, m1, k1)}")
print(f"Example 2 Optimal: {max_sum_almost_unique_subarray_optimal(nums2, m2, k2)}")
print(f"Example 3 Optimal: {max_sum_almost_unique_subarray_optimal(nums3, m3, k3)}")


"""Big O Analysis:

Naive Approach:
Time Complexity: O(n*k) where n is length of input array and k is subarray length.
This is because we iterate through array (O(n)) and at each iteration,
compute sum (O(k)) and determine distinct elements (O(k)).

Space Complexity: O(k) since we are creating a subarray with a max length of k.

Optimal Approach:
Time Complexity: O(n) because we iterate through the array once.
Window count operations (add/remove elements) take constant time.

Space Complexity: O(k) where k is the size of the window. This is because
the dictionary 'window_counts' and the sliding window itself store at most k elements.
"""

Code Explanation

The problem asks to find the maximum sum of an almost unique subarray of length k in a given array nums. A subarray is considered almost unique if it contains at least m distinct elements.

Naive Approach:

1. Iterate through all possible subarrays of length k.
2. For each subarray, count the number of distinct elements using a set.
3. If the distinct count is greater than or equal to m, calculate the sum of the subarray.
4. Keep track of the maximum sum encountered so far.

Optimal Approach (Sliding Window):

1. Use a sliding window of size k to iterate through the array.
2. Maintain a dictionary window_counts to store the count of each element in the window and calculate running window sum.
3. Maintain a variable distinct_count to store the number of distinct elements in the window.
4. When sliding the window, remove the leftmost element and add the rightmost element.
5. Update window_counts and distinct_count accordingly.
6. If the distinct_count is greater than or equal to m, update the maximum sum.

Big O Analysis

Naive Approach:

• Time Complexity: O(n*k), where n is the length of the input array and k is the subarray length. This is because we iterate through the array (O(n)) and, at each iteration, compute the sum (O(k)) and determine distinct elements (O(k)).
• Space Complexity: O(k), since we are creating a subarray with a max length of k.

Optimal Approach:

• Time Complexity: O(n) because we iterate through the array once. Window count operations (add/remove elements) take constant time.
• Space Complexity: O(k), where k is the size of the window. This is because the dictionary window_counts and the sliding window itself store at most k elements.