Sliding Window: Given an array and integer k, find the max sum of distinct subarray of length k

Problem Statement:

You are given an array with repeated integers and a number k.

You need to find the maximum sum of all the sub array wit size k and that are distinct.

Example:

Input: arr[] = [1, 2, 3, 4, 4, 4] k = 2

Output: 7

Explanation: The subarray [3, 4] is a sub array with size 2 and elements are distinct

Solution Explanation:

We will solve the problem by using hashmap and sliding window technique.

Take 2 pointers l and r that maintain a sliding window.

Use hashmap to store the frequency of the elements in the current window.

Increment right pointer ‘r’, add current element to the sum and update the frequency in the hashmap.

If the window is equal to k, then check if the hashmap elements are all distinct.

If true, update the sum, else move the left pointer “l” update its frequency and the sum.

Return the maximum sum.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int solution(vector<int>& nums, int k) 
{
    int l = 0, r = 0;
    int n = nums.size();

    int sum=0, maxi=0;
    map<int, int> mp;

    for(r=0; r<n; r++)
    {
        sum += nums[r];
        mp[nums[r]]++;

        if(r-l+1 == k)
        {
            if(mp.size() == r-l+1)
            {
                maxi = max(sum ,maxi);
            }
            
            sum-=nums[l];
            mp[nums[l]]--;
            
            if(mp[nums[l]] == 0) 
                mp.erase(nums[l]);
            l++;
        }
    }
    return maxi;
}



int main()
{
    vector<int> arr = {1, 2, 3, 4, 4, 4 };
    int k = 2;

    cout << solution(arr, k);
    return 0;
}

Output

7