Smallest subarray with k distinct numbers in C++

In this tutorial, we are going to learn how to find the Smallest subarray with k distinct numbers in C++. Firstly we have an introduction to the on arrays and subarrays. Secondly, methods to solve the problem.

Introduction

The array is a data structure that can save data in sequential order. In this problem, we have an array which is consisting of n integers and integer k. We have to find the minimum range in array [l, h] such that there are exactly k different numbers between them.

One of the solutions is to use two nested loops. The first loop is used to pick a starting point and the inner loop is used to pick endpoint of the array. We change the result if the current window is smaller for each pair of starting and ending points we count different elements in it. We will use hashing to count distinct elements in a range.

C++ Program to find the Smallest subarray with k distinct numbers

#include <bits/stdc++.h> 
using namespace std; 

void range(int arr[], int n, int k) 
{ 
    int l = 0, r = n; 

    for (int i=0;i<n;i++) { 

        unordered_set<int> s; 
        int j; 
        for (j =i;j<n;j++) { 
            s.insert(arr[j]); 
            if (s.size() == k) { 
                if ((j - i) < (r - l)) { 
                    r = j; 
                    l = i; 
                } 
                break; 
            } 
        } 

        if (j == n) 
            break; 
    } 
 
    if (l == 0 && r == n) 
        cout << "Invalid k"; 
    else
        cout << l << " " << r; 
} 

int main() 
{
  int n,k;
  cout<<"Enter the size of array : ";
  cin>>n;
  int arr[n];
  cout<<"Enter the array : ";
  for(int i=0;i<n;i++){
    cin>>arr[i];
  }
  cout<<"Enter the value of 'k' : ";
  cin>>k;
  range(arr, n, k); 
    return 0; 
}

Input and Output : 

Enter the size of array : 5
Enter the array : 1 2 3 4 5
Enter the value of 'k' : 3
0 2

Conclusion

This is the solution of Smallest subarray with k distinct numbers in C++ problem. It has concepts like array and hashing. These both have a vast amount of usage in other problem-solving.

Also Checkout:

Check if a given matrix is sparse or not in C++

Leave a Reply

Your email address will not be published. Required fields are marked *