Hash

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)
			{
				record.add(arr[i]);
				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)
	{
		SubArray task = new SubArray();
		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;
		task.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

// 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()
{
	SubArray *task = new SubArray();
	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;
	task->kDistinctSmallArray(arr, n, k);
	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)
			{
				record.Add(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];
			}
		}
		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)
	{
		SubArray task = new SubArray();
		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;
		task.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

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()
{
	$task = new SubArray();
	$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;
	$task->kDistinctSmallArray($arr, $n, $k);
}
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)
			{
				record.add(arr[i]);
				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 task = new SubArray();
	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;
	task.kDistinctSmallArray(arr, n, k);
}
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) :
				record.add(arr[i])
				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() :
	task = SubArray()
	arr = [9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5]
	#  Get the number of element in list
	n = len(arr)
	k = 3
	task.kDistinctSmallArray(arr, n, k)

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) 
				record.add(arr[i])
				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() 
	task = SubArray.new()
	arr = [9, 1, 2, 2, -2, 2, -3, -3, 4, -5, 5]
	#  Get the number of element in array
	n = arr.length
	k = 3
	task.kDistinctSmallArray(arr, n, k)
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)
			{
				record.add(arr(i));
				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;
		task.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

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 task: SubArray = SubArray();
	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;
	task.kDistinctSmallArray(arr, n, k);
}
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)
			{
				record.add(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 \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 task: SubArray = SubArray();
	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;
	task.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

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.

New Comment

Name