Smallest Subarray with k Distinct Numbers

Suppose, you have an integer array and a number k. The problem statement asks to find out the smallest sub-array of range (l, r) inclusively, in such a way there are exactly k distinct numbers present in that smallest sub-array.

Table of Contents

Example

Input:

{1, 2, 2, 3, 4, 5, 5}

k=3

Output:

2, 4

Explanation:

{2, 3, 4} is the smallest sub-array starting from 2^nd index to 4^th index with k i.e., 3 distinct elements.

Input:

{2, 5, 6, 7}

k=2

Output:

2, 3

Explanation:

{2, 5} is the smallest sub-array starting from 2nd index to 3rd index with k ie., 2 distinct elements.

Algorithm

Set the distinct element to 0 and left side and right side pointers to -1.
Traverse through the array,
Incrementing right side by 1, if no of distinct elements is less than the given number k,
Then increase the count and store the frequency of array element into the map.
If distinct elements are equal to the given number k and the length so formed is smaller than the previously updated length, then left and right side pointers and break.
If the number of distinct elements found to be less than k then break.
Check if the number of distinct elements found to be equal to k, then increase the right side pointers.
If distinct elements are equal to the given number k and the length so formed is smaller than the previously updated length, then left and right side pointers and break.
Check if the frequency of the element is found to be 1, then remove that element from the map, else decrease the count of the frequency of that element
If the left side pointer is found to be 0 and the right side to be equal to n, it means it is invalid.
Else, print the left side and right side values.

Explanation

Store each array elements frequency while traversing the array, and pick each array element, and check if map size is less than k if it is found to be less than k than we need to count and store the frequency of that array element and if the map size founds to be k(distinct element number) and also the current length is less than the previous length of the sub-array, then we will update the left side and right side pointers. This all will go in a loop, till the whole map is traversed once.

If the size of a map founds to be less than k, then break. We have got the values on a map. Loop will go till the size of the map found to be equal to k, the frequency of array element in a map is found to be equal to 1, then we need to remove that particular element from the map, else we need to decrease the frequency of that particular element from a map. Again we are going to check if the map size is equal to k and the length of the current sub-array is less than the previously updated length, then, update the left side and right side pointers. If the frequency of the array element is 1, then remove that element else decrease the frequency of the element.

After traversal of the array, if the left side pointer is found to be 0 and the right side pointer to n, that means it is an invalid k. Else print the value of the left and right side pointer, which would be the starting point and ending point of the smallest sub-array inclusively.

Implementation

C++ program for Smallest Subarray with k Distinct Numbers#include<iostream>

#include<map>

using namespace std;

void getSmallestSubarray(int arr[], int n, int k)
{
    int left = 0, right = n;
    int j = -1;
    map<int, int> MAP;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            j++;
            if (MAP.size() < k)
                MAP[arr[j]]++;

            if (MAP.size() == k && ((right - left) >= (j - i)))
            {
                left = i;
                right = j;
                break;
            }

        }
        if (MAP.size() < k)
            break;

        while (MAP.size() == k)
        {
            if (MAP[arr[i]] == 1)
                MAP.erase(arr[i]);
            else
                MAP[arr[i]]--;

            i++;

            if (MAP.size() == k && (right - left) >= (j - i))
            {
                left = i;
                right = j;
            }
        }
        if (MAP[arr[i]] == 1)
            MAP.erase(arr[i]);
        else
            MAP[arr[i]]--;
    }
    if (left == 0 && right == n)
        cout << "Invalid k" << endl;
    else
        cout << left << " " << right;
}
int main()
{
    int arr[] = {1, 2, 2, 3, 4, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    getSmallestSubarray(arr, n, k);
    return 0;
}

2 4

Java program for Smallest Subarray with k Distinct Numbers

import java.util.HashMap;
import java.util.Map;
class smallestSubArray
{
    public static void getSmallestSubarray(int arr[], int n, int k)
    {
        int left = 0, right = n;
        int j = -1;
        HashMap<Integer, Integer> MAP=new HashMap<>();
        for (int i=0; i<n; i++)
        {
            while (j < n-1)
            {
                j++;
                if (MAP.size() < k)
                {

                    if(MAP.containsKey( arr[j] ))
                        MAP.put( arr[j], MAP.get( arr[j] ) + 1 );
                    else
                        MAP.put(arr[j],1);
                }

                if (MAP.size() == k && ((right - left) >= (j - i)))
                {
                    left = i;
                    right = j;
                    break;
                }
            }
            if (MAP.size() < k)
                break;

            while (MAP.size() == k)
            {
                if (MAP.get(arr[i]) == 1)
                    MAP.remove(arr[i]);
                else
                    MAP.put(arr[i], MAP.get(arr[i])-1);

                i++;

                if (MAP.size() == k && (right - left) >= (j - i))
                {
                    left = i;
                    right = j;
                }
            }
            if (MAP.get(arr[i]) == 1)
                MAP.remove(arr[i]);
            else
                MAP.put(arr[i], MAP.get(arr[i])-1);
        }
        if (left == 0 && right == n)
            System.out.println("Invalid k");
        else
            System.out.println(left+" "+right);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, 2, 2, 3, 4, 5, 5};
        int n = arr.length;
        int k = 3;
        getSmallestSubarray(arr, n, k);

    }
}

2 4