Tutorialspoint.dev

Smallest subarray with k distinct numbers

We are given an array a consisting of n integers and an integer k. We need to find the minimum range in array [l, r] (both l and r are inclusive) such that there are exactly k different numbers.

Examples:

Input : arr[] = { 1, 1, 2, 2, 3, 3, 4, 5} 
            k = 3
Output : 5 7

Input : arr[] = { 1, 2, 2, 3} 
            k = 2
Output : 0 1



A simple solution is to use two nested loops. The outer loop is used to pick a starting point and inner loop is used to pick an ending point. For every pair of starting-ending points, we count distinct elements in it and update result if the current window is smaller. We use hashing to count distinct elements in a range.

C++

// CPP program to find minimum range that
// contains exactly k distinct numbers.
#include <bits/stdc++.h>
using namespace std;
  
// Prints the minimum range that contains exactly
// k distinct numbers.
void minRange(int arr[], int n, int k)
{
    int l = 0, r = n;
  
    // Consider every element as starting
    // point.
    for (int i = 0; i < n; i++) {
  
        // Find the smallest window starting
        // with arr[i] and containing exactly
        // k distinct elements.
        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;
            }
        }
  
        // There are less than k distinct elements
        // now, so no need to continue.
        if (j == n)
            break;
    }
  
    // If there was no window with k distinct
    // elements (k is greater than total distinct
    // elements)
    if (l == 0 && r == n)
        cout << "Invalid k";
    else
        cout << l << " " << r;
}
  
// Driver code for above function.
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    minRange(arr, n, k);
    return 0;
}

Java

// Java program to find minimum 
// range that contains exactly 
// k distinct numbers.
import java.util.*;
  
class GFG 
{
      
// Prints the minimum range 
// that contains exactly k 
// distinct numbers.
static void minRange(int arr[], 
                     int n, int k)
{
    int l = 0, r = n;
  
    // Consider every element 
    // as starting point.
    for (int i = 0; i < n; i++)
    {
  
        // Find the smallest window 
        // starting with arr[i] and 
        // containing exactly k 
        // distinct elements.
        Set<Integer> s = new HashSet<Integer>();
        int j;
        for (j = i; j < n; j++) 
        {
            s.add(arr[j]);
            if (s.size() == k) 
            {
                if ((j - i) < (r - l))
                {
                    r = j;
                    l = i;
                }
                break;
            }
        }
  
        // There are less than k 
        // distinct elements now, 
        // so no need to continue.
        if (j == n)
            break;
    }
  
    // If there was no window 
    // with k distinct elements 
    // (k is greater than total 
    // distinct elements)
    if (l == 0 && r == n)
        System.out.println("Invalid k");
    else
        System.out.println(l + " " + r);
}
  
// Driver code 
public static void main(String args[])
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = arr.length;
    int k = 3;
    minRange(arr, n, k);
}
}
  
// This code is contributed 
// by Kirti_Mangal

Python 3

# Python 3 program to find minimum range 
# that contains exactly k distinct numbers.
  
# Prints the minimum range that contains 
# exactly k distinct numbers.
def minRange(arr, n, k):
  
    l = 0
    r = n
  
    # Consider every element as 
    # starting point.
    for i in range(n):
  
        # Find the smallest window starting
        # with arr[i] and containing exactly
        # k distinct elements.
        s = []
        for j in range(i, n) :
            s.append(arr[j])
            if (len(s) == k):
                if ((j - i) < (r - l)) :
                    r = j
                    l = i
                  
                break
  
        # There are less than k distinct 
        # elements now, so no need to continue.
        if (j == n):
            break
  
    # If there was no window with k distinct
    # elements (k is greater than total 
    # distinct elements)
    if (l == 0 and r == n):
        print("Invalid k")
    else:
        print(l, r)
  
# Driver code 
if __name__ == "__main__":
      
    arr = [ 1, 2, 3, 4, 5 ]
    n = len(arr)
    k = 3
    minRange(arr, n, k)
  
# This code is contributed 
# by ChitraNayal

C#

// C#  program to find minimum  
// range that contains exactly  
// k distinct numbers. 
using System;
using System.Collections.Generic;
  
public class GFG
{
  
// Prints the minimum range  
// that contains exactly k  
// distinct numbers. 
public static void minRange(int[] arr, int n, int k)
{
    int l = 0, r = n;
  
    // Consider every element  
    // as starting point. 
    for (int i = 0; i < n; i++)
    {
  
        // Find the smallest window  
        // starting with arr[i] and  
        // containing exactly k  
        // distinct elements. 
        ISet<int> s = new HashSet<int>();
        int j;
        for (j = i; j < n; j++)
        {
            s.Add(arr[j]);
            if (s.Count == k)
            {
                if ((j - i) < (r - l))
                {
                    r = j;
                    l = i;
                }
                break;
            }
        }
  
        // There are less than k  
        // distinct elements now,  
        // so no need to continue. 
        if (j == n)
        {
            break;
        }
    }
  
    // If there was no window  
    // with k distinct elements  
    // (k is greater than total  
    // distinct elements) 
    if (l == 0 && r == n)
    {
        Console.WriteLine("Invalid k");
    }
    else
    {
        Console.WriteLine(l + " " + r);
    }
}
  
// Driver code  
public static void Main(string[] args)
{
    int[] arr = new int[] {1, 2, 3, 4, 5};
    int n = arr.Length;
    int k = 3;
    minRange(arr, n, k);
}
}
  
// This code is contributed by Shrikant13

Output:

0 2


Time Complexity :
O(n2)
 

Optimization over above simple solution. The idea is to remove repetitions on left side after we find k distinct elements.

C++

// CPP program to find minimum range that
// contains exactly k distinct numbers.
#include <bits/stdc++.h>
using namespace std;
  
// prints the minimum range that contains exactly
// k distinct numbers.
void minRange(int arr[], int n, int k)
{
    // Initially left and right side is -1 and -1,
    // number of distinct elements are zero and
    // range is n.
    int l = 0, r = n;
  
    int j = -1; // Initialize right side
    map<int, int> hm;
    for (int i=0; i<n; i++)
    {
        while (j < n)
        {
            // increment right side.
            j++;
  
            // if number of distinct elements less
            // than k.
            if (hm.size() < k)
                hm[arr[j]]++;
  
            // if distinct elements are equal to k
            // and length is less than previous length.
            if (hm.size() == k && ((r - l) >= (j - i)))
            {
                l = i;
                r = j;
                break;
            }
        }
  
        // if number of distinct elements less
        // than k, then break.
        if (hm.size() < k)
            break;
  
        // if distinct elements equals to k then
        // try to increment left side.
        while (hm.size() == k)
        {
  
            if (hm[arr[i]] == 1)
                hm.erase(arr[i]);
            else
                hm[arr[i]]--;
  
            // increment left side.
            i++;
  
            // it is same as explained in above loop.
            if (hm.size() == k && (r - l) >= (j - i))
            {
                l = i;
                r = j;
            }
        }
        if (hm[arr[i]] == 1)
            hm.erase(arr[i]);
        else
            hm[arr[i]]--;
    }
  
    if (l == 0 && r == n)
        cout << "Invalid k" << endl;
    else
        cout << l << " " << r << endl;
}
  
// Driver code for above function.
int main()
{
    int arr[] = { 1, 1, 2, 2, 3, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    minRange(arr, n, k);
    return 0;
}

Python3

# Python3 program to find the minimum range 
# that contains exactly k distinct numbers. 
from collections import defaultdict
  
# Prints the minimum range that contains 
# exactly k distinct numbers. 
def minRange(arr, n, k): 
   
    # Initially left and right side is -1 
    # and -1, number of distinct elements 
    # are zero and range is n. 
    l, r = 0, n 
    i = 0
    j = -1 # Initialize right side 
      
    hm = defaultdict(lambda:0
    while i < n: 
       
        while j < n: 
           
            # increment right side. 
            j += 1 
    
            # if number of distinct elements less than k. 
            if len(hm) < k and j < n:
                hm[arr[j]] += 1 
    
            # if distinct elements are equal to k 
            # and length is less than previous length. 
            if len(hm) == k and ((r - l) >= (j - i)): 
               
                l, r = i, j 
                break 
    
        # if number of distinct elements less 
        # than k, then break. 
        if len(hm) < k:
            break 
    
        # if distinct elements equals to k then 
        # try to increment left side. 
        while len(hm) == k: 
    
            if hm[arr[i]] == 1
                del(hm[arr[i]]) 
            else:
                hm[arr[i]] -= 1 
    
            # increment left side. 
            i += 1
    
            # it is same as explained in above loop. 
            if len(hm) == k and (r - l) >= (j - i): 
               
                l, r = i, j 
           
        if hm[arr[i]] == 1
            del(hm[arr[i]]) 
        else:
            hm[arr[i]] -= 1 
              
        i += 1
    
    if l == 0 and r == n:
        print("Invalid k"
    else:
        print(l, r) 
   
# Driver code for above function. 
if __name__ == "__main__"
   
    arr = [1, 1, 2, 2, 3, 3, 4, 5]  
    n = len(arr) 
    k = 3 
    minRange(arr, n, k) 
      
# This code is contributed by Rituraj Jain 

Output:

5 7

Time complexity of this solution is O(n). In every nested iteration, we either add an element or remove an element. Every element is inserted and removed at most once.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter