Sliding Window: Subarray with k different integers

Problem Statement:

You are given an array and a value k.

You need to return subarray with k different integers.

A subarray is a continuous part of the array.

Example:

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

Output: 3

Solution Explanation:

We will use sliding window technique to solve the problem.

First we will calculate the count of all the subarray that contain at most K distinct integers.

Next we will count the subarray that has atmost k-1 distinct integers.

Their difference will give the number of subarrays that has exactly k distinct integers.

Counting exactly k distinct integers is difficult, because you need to track the distinct count for each subarray.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

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

int subArray(vector<int>& nums,int k)
{
    unordered_map<int,int> map;
    int left = 0, right = 0, ans = 0;

    while(right<nums.size())
    {
        map[nums[right]]++;
        while(map.size()>k)
        {
            map[nums[left]]--;
            if(map[nums[left]]==0)map.erase(nums[left]);
            	left++;
        }

        ans += right-left+1;
        
        right++;
    }
    return ans;
}

int solution (vector<int>& nums, int k) 
{

    return subArray(nums, k) - subArray(nums, k - 1);
}

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

    cout << solution(arr, k);

    return 0;
}

Output

3