Sliding Window: Return length of longest subarray with having at most k frequency

Problem Statement:

You are given an array of integers and a value k.

You need to find the length of the longest subarray, such that the frequency of each element is less than or equal to k.

Example:

Input: arr[] = {1, 2, 3, 1, 2, 3, 1, 2}, K = 2

Output: 6

Explanation: 1, 2, 3, 1, 2, 3

Solution Explanation:

Take 2 pointers l and r, that will represent the window.

Take unordered_map to store the frequency in the window.

If the frequency exceeds k, then shrink window from left, until the frequency of the element is decreased by one.

update the max length and return the result at the end.

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

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

int solution(vector<int>& nums, int k) 
{
    int ans=0;
    unordered_map<int,int>mp;
    int n= nums.size();

    for(int l=0,r=0;r<n;r++)
    {
        mp[nums[r]]++;  

        if(mp[nums[r]]>k)
        {
            while(nums[l]!=nums[r])
            {
                mp[nums[l]]--;
                l++;
            }
            mp[nums[l]]--;
            l++;
        }
        ans=max(ans,r-l+1);
    }
    return ans;
}

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

    cout << solution(arr, k) << endl;

    return 0;
}

Output

6