# Smallest subarray with k distinct numbers

Here given code implementation process.

``````import java.util.HashSet;
/*
Java program for
Smallest subarray with k distinct numbers
*/
public class SubArray
{
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
}
public void kDistinctSmallArray(int[] arr, int n, int k)
{
if (k <= 0 || k > n)
{
return;
}
int sum = 0;
HashSet < Integer > record = new HashSet < Integer > ();
int result = Integer.MAX_VALUE;
int startBy = -1;
for (int i = 0; i < n; ++i)
{
if (record.contains(arr[i]))
{
// Remove all exist element in record
record.clear();
sum = 0;
}
if (record.size() < k)
{
sum += arr[i];
}
if (record.size() == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.remove(arr[(i + 1) - k]);
sum -= arr[(i + 1) - k];
}
}
System.out.print("\n Given Array element \n");
this.printArray(arr, n);
System.out.print("\n Smallest subarray of size k = " + k + " is \n");
if (startBy == -1)
{
// Means no distinct subarray of given k size
System.out.print("\nNone");
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
System.out.print("  " + arr[startBy]);
startBy++;
}
}
}
public static void main(String[] args)
{
int[] arr = {
9 , 1 , 2 , 2 , -2 , 2 , -3 , -3 , 4 , -5 , 5
};
// Get the number of element in array
int n = arr.length;
int k = 3;
}
}``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````// Include header file
#include <iostream>
#include <set>
#include <limits.h>

using namespace std;
/*
C++ program for
Smallest subarray with k distinct numbers
*/
class SubArray
{
public: void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
}
void kDistinctSmallArray(int arr[], int n, int k)
{
if (k <= 0 || k > n)
{
return;
}
int sum = 0;
set < int > record;
int result = INT_MAX;
int startBy = -1;
for (int i = 0; i < n; ++i)
{
if (record.find(arr[i]) != record.end())
{
// Remove all exist element in record
record.clear();
sum = 0;
}
if (record.size() < k)
{
record.insert(arr[i]);
sum += arr[i];
}
if (record.size() == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.erase(arr[(i + 1) - k]);
sum -= arr[(i + 1) - k];
}
}
cout << "\n Given Array element \n";
this->printArray(arr, n);
cout << "\n Smallest subarray of size k = " << k << " is \n";
if (startBy == -1)
{
// Means no distinct subarray of given k size
cout << "\nNone";
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
cout << "  " << arr[startBy];
startBy++;
}
}
}
};
int main()
{
int arr[] = {
9 , 1 , 2 , 2 , -2 , 2 , -3 , -3 , 4 , -5 , 5
};
// Get the number of element in array
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
return 0;
}``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Smallest subarray with k distinct numbers
*/
public class SubArray
{
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
}
public void kDistinctSmallArray(int[] arr, int n, int k)
{
if (k <= 0 || k > n)
{
return;
}
int sum = 0;
HashSet < int > record = new HashSet < int > ();
int result = int.MaxValue;
int startBy = -1;
for (int i = 0; i < n; ++i)
{
if (record.Contains(arr[i]))
{
// Remove all exist element in record
record.Clear();
sum = 0;
}
if (record.Count < k)
{
sum += arr[i];
}
if (record.Count == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.Remove(arr[(i + 1) - k]);
sum -= arr[(i + 1) - k];
}
}
Console.Write("\n Given Array element \n");
this.printArray(arr, n);
Console.Write("\n Smallest subarray of size k = " + k + " is \n");
if (startBy == -1)
{
// Means no distinct subarray of given k size
Console.Write("\nNone");
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
Console.Write("  " + arr[startBy]);
startBy++;
}
}
}
public static void Main(String[] args)
{
int[] arr = {
9 , 1 , 2 , 2 , -2 , 2 , -3 , -3 , 4 , -5 , 5
};
// Get the number of element in array
int n = arr.Length;
int k = 3;
}
}``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````package main
import "math"
import "fmt"
/*
Go program for
Smallest subarray with k distinct numbers
*/

func printArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
}
func kDistinctSmallArray(arr[] int, n int, k int) {
if k <= 0 || k > n {
return
}
var sum int = 0
var record = make(map[int] bool)
var result int = math.MaxInt64
var startBy int = -1
for i := 0 ; i < n ; i++ {
if _, found := record[arr[i]] ; found {
// Remove all exist element in record
for k := range record {
delete(record, k)
}
sum = 0
}
if len(record) < k {
record[arr[i]] = true
sum += arr[i]
}
if len(record) == k {
if result > sum {
result = sum
startBy = (i + 1) - k
}
// For next iteration
delete(record,arr[(i + 1) - k])
sum -= arr[(i + 1) - k]
}
}
fmt.Print("\n Given Array element \n")
printArray(arr, n)
fmt.Print("\n Smallest subarray of size k = ", k, " is \n")
if startBy == -1 {
// Means no distinct subarray of given k size
fmt.Print("\nNone")
} else {
sum = k + startBy
// Display resultant subarray
for (startBy < sum) {
fmt.Print("  ", arr[startBy])
startBy++
}
}
}
func main() {

var arr = [] int {9, 1, 2, 2,-2, 2, -3, -3, 4, -5, 5}
// Get the number of element in array
var n int = len(arr)
var k int = 3
kDistinctSmallArray(arr, n, k)
}``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````<?php
/*
Php program for
Smallest subarray with k distinct numbers
*/
class SubArray
{
public	function printArray(\$arr, \$n)
{
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
}
public	function kDistinctSmallArray(\$arr, \$n, \$k)
{
if (\$k <= 0 || \$k > \$n)
{
return;
}
\$sum = 0;
\$record = array();
\$result = PHP_INT_MAX;
\$startBy = -1;
for (\$i = 0; \$i < \$n; ++\$i)
{
if (in_array(\$arr[\$i], \$record, TRUE))
{
// Remove all exist element in record
\$sum = 0;
\$record = array();
}
if (count(\$record) < \$k)
{

\$record[] = \$arr[\$i];
\$sum += \$arr[\$i];
}
if (count(\$record) == \$k)
{
if (\$result > \$sum)
{
\$result = \$sum;
\$startBy = (\$i + 1) - \$k;
}
// For next iteration
unset(\$record[\$arr[(\$i + 1) - \$k]]);
\$sum -= \$arr[(\$i + 1) - \$k];
}
}
echo("\n Given Array element \n");
\$this->printArray(\$arr, \$n);
echo("\n Smallest subarray of size k = ".\$k.
" is \n");
if (\$startBy == -1)
{
// Means no distinct subarray of given k size
echo("\nNone");
}
else
{
\$sum = \$k + \$startBy;
// Display resultant subarray
while (\$startBy < \$sum)
{
echo("  ".\$arr[\$startBy]);
\$startBy++;
}
}
}
}

function main()
{
\$arr = array(9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5);
// Get the number of element in array
\$n = count(\$arr);
\$k = 3;
}
main();``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````/*
Node JS program for
Smallest subarray with k distinct numbers
*/
class SubArray
{
printArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
}
kDistinctSmallArray(arr, n, k)
{
if (k <= 0 || k > n)
{
return;
}
var sum = 0;
var record = new Set();
var result = Number.MAX_VALUE;
var startBy = -1;
for (var i = 0; i < n; ++i)
{
if (record.has(arr[i]))
{
// Remove all exist element in record
record.clear();
sum = 0;
}
if (record.size < k)
{
sum += arr[i];
}
if (record.size == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.delete(arr[(i + 1) - k]);
sum -= arr[(i + 1) - k];
}
}
process.stdout.write("\n Given Array element \n");
this.printArray(arr, n);
process.stdout.write("\n Smallest subarray of size k = " +
k + " is \n");
if (startBy == -1)
{
// Means no distinct subarray of given k size
process.stdout.write("\nNone");
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
process.stdout.write("  " + arr[startBy]);
startBy++;
}
}
}
}

function main()
{
var arr = [9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5];
// Get the number of element in array
var n = arr.length;
var k = 3;
}
main();``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````import sys
#    Python 3 program for
#    Smallest subarray with k distinct numbers
class SubArray :
def printArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

def kDistinctSmallArray(self, arr, n, k) :
if (k <= 0 or k > n) :
return

sum = 0
record = set()
result = sys.maxsize
startBy = -1
i = 0
while (i < n) :
if (arr[i] in record) :
#  Remove all exist element in record
record.clear()
sum = 0

if (len(record) < k) :
sum += arr[i]

if (len(record) == k) :
if (result > sum) :
result = sum
startBy = (i + 1) - k

#  For next iteration
record.remove(arr[(i + 1) - k])
sum -= arr[(i + 1) - k]

i += 1

print("\n Given Array element ")
self.printArray(arr, n)
print("\n Smallest subarray of size k = ", k ," is ")
if (startBy == -1) :
#  Means no distinct sublist of given k size
print("\nNone", end = "")
else :
sum = k + startBy
#  Display resultant sublist
while (startBy < sum) :
print("  ", arr[startBy], end = "")
startBy += 1

def main() :
arr = [9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5]
#  Get the number of element in list
n = len(arr)
k = 3

if __name__ == "__main__": main()``````

#### Output

`````` Given Array element
9  1  2  2  -2  2  -3  -3  4  -5  5
Smallest subarray of size k =  3  is
-3   4   -5``````
``````require 'set'
#    Ruby program for
#    Smallest subarray with k distinct numbers
class SubArray
def printArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

end

def kDistinctSmallArray(arr, n, k)
if (k <= 0 || k > n)
return
end

sum = 0
record = SortedSet.new()
result = (2 ** (0. size * 8 - 2))
startBy = -1
i = 0
while (i < n)
if (record.include?(arr[i]))
#  Remove all exist element in record
record.clear()
sum = 0
end

if (record.size() < k)
sum += arr[i]
end

if (record.size() == k)
if (result > sum)
result = sum
startBy = (i + 1) - k
end

#  For next iteration
record.delete(arr[(i + 1) - k])
sum -= arr[(i + 1) - k]
end

i += 1
end

print("\n Given Array element \n")
self.printArray(arr, n)
print("\n Smallest subarray of size k = ", k ," is \n")
if (startBy == -1)
#  Means no distinct subarray of given k size
print("\nNone")
else

sum = k + startBy
#  Display resultant subarray
while (startBy < sum)
print("  ", arr[startBy])
startBy += 1
end

end

end

end

def main()
arr = [9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5]
#  Get the number of element in array
n = arr.length
k = 3
end

main()``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````import scala.collection.mutable._;
/*
Scala program for
Smallest subarray with k distinct numbers
*/
class SubArray()
{
def printArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
}
def kDistinctSmallArray(
arr: Array[Int],
n: Int,
k: Int): Unit = {
if (k <= 0 || k > n)
{
return;
}
var sum: Int = 0;
var record = Set[Int]();
var result: Int = Int.MaxValue;
var startBy: Int = -1;
var i: Int = 0;
while (i < n)
{
if (record.contains(arr(i)))
{
// Remove all exist element in record
record.clear();
sum = 0;
}
if (record.size < k)
{
sum += arr(i);
}
if (record.size == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.remove(arr((i + 1) - k));
sum -= arr((i + 1) - k);
}
i += 1;
}
print("\n Given Array element \n");
this.printArray(arr, n);
print("\n Smallest subarray of size k = " + k + " is \n");
if (startBy == -1)
{
// Means no distinct subarray of given k size
print("\nNone");
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
print("  " + arr(startBy));
startBy += 1;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubArray = new SubArray();
var arr: Array[Int] = Array(9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5);
// Get the number of element in array
var n: Int = arr.length;
var k: Int = 3;
}
}``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````
``````import Foundation;
/*
Swift 4 program for
Smallest subarray with k distinct numbers
*/
class SubArray
{
func printArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
func kDistinctSmallArray(_ arr: [Int], _ n: Int, _ k: Int)
{
if (k <= 0 || k > n)
{
return;
}
var sum: Int = 0;
var record = Set<Int>();
var result: Int = Int.max;
var startBy: Int = -1;
var i: Int = 0;
while (i < n)
{
if (record.contains(arr[i]))
{
// Remove all exist element in record
record.removeAll();
sum = 0;
}
if (record.count < k)
{
record.insert(arr[i]);
sum += arr[i];
}
if (record.count == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.remove(arr[(i + 1) - k]);
sum -= arr[(i + 1) - k];
}
i += 1;
}
print("\n Given Array element ");
self.printArray(arr, n);
print("\n Smallest subarray of size k = ", k ," is ");
if (startBy == -1)
{
// Means no distinct subarray of given k size
print("\nNone", terminator: "");
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
print("  ", arr[startBy], terminator: "");
startBy += 1;
}
}
}
}
func main()
{
let arr: [Int] = [9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5];
// Get the number of element in array
let n: Int = arr.count;
let k: Int = 3;
}
main();``````

#### Output

`````` Given Array element
9  1  2  2  -2  2  -3  -3  4  -5  5
Smallest subarray of size k =  3  is
-3   4   -5``````
``````/*
Kotlin program for
Smallest subarray with k distinct numbers
*/
class SubArray
{
fun printArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
}
fun kDistinctSmallArray(arr: Array < Int > , n: Int, k: Int): Unit
{
if (k <= 0 || k > n)
{
return;
}
var sum: Int = 0;
var record: MutableSet <Int> = mutableSetOf <Int> ();
var result: Int = Int.MAX_VALUE;
var startBy: Int = -1;
var i: Int = 0;
while (i < n)
{
if (record.contains(arr[i]))
{
// Remove all exist element in record
record.clear();
sum = 0;
}
if (record.count() < k)
{
sum += arr[i];
}
if (record.count() == k)
{
if (result > sum)
{
result = sum;
startBy = (i + 1) - k;
}
// For next iteration
record.remove(arr[(i + 1) - k]);
sum -= arr[(i + 1) - k];
}
i += 1;
}
print("\n Given Array element \n");
this.printArray(arr, n);
print("\n Smallest subarray of size k = " + k + " is \n");
if (startBy == -1)
{
// Means no distinct subarray of given k size
print("\nNone");
}
else
{
sum = k + startBy;
// Display resultant subarray
while (startBy < sum)
{
print("  " + arr[startBy]);
startBy += 1;
}
}
}
}
fun main(args: Array < String > ): Unit
{
val arr: Array < Int > = arrayOf(9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5);
// Get the number of element in array
val n: Int = arr.count();
val k: Int = 3;
}``````

#### Output

`````` Given Array element
9 1 2 2 -2 2 -3 -3 4 -5 5
Smallest subarray of size k = 3 is
-3  4  -5``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.