Prefix Sum and Sliding Window 08

Given an array of integers and a number K. Find the count of distinct elements in every window of size K in the array.

Problem link :- click here

Code

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//	COUNT DISTINCT ELEMENT IN EVERY WINDOW

public class Prefix_sum__Sliding_window_08
{
	
	static int[] countDistinctElementInEveryWindow(int arr[], int k)
	{
		int count = 0;
		
		int n = arr.length - (k - 1);
		int c_arr[] = new int[n];
		
		Map<Integer, Integer> hm = new HashMap<>();
		
		// step1: - First window where only adding is required and no removing
		for(int i=0; i<k; i++)
		{
			if( hm.containsKey(arr[i])  ==  false )
			{
				count++;
				hm.put(arr[i], 1);
			}
			else
				hm.put(arr[i], hm.get(arr[i]) + 1);
		}
		c_arr[0] = count;
		
		for(int i=k, j=1; i<arr.length; i++, j++)
		{
			//Removing arr[i - k]
			int first = arr[i - k];		//first element of window
			hm.put(first, hm.get(first) - 1);
			
			//Decrementing count if hm.get(first) == 0
			if( hm.get(first) == 0)
				count--;
			
			//Adding the next element to the window
			int next = arr[i];
			if( hm.containsKey(next) == false)
			{
				hm.put(next, 1);
				count++;
			}
			else if( hm.get(next) == 0)
			{
				hm.put(next, 1);
				count++;
			}
			else
				hm.put(next, hm.get(next) + 1 );
			
			//appending the count of next window
			c_arr[j] = count;
		}
		
		return c_arr;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		//	Taking size of array and array as input from the user
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		
		int[] arr = new int[n];
		System.out.println("Enter the array elements : ");
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
		System.out.print("Enter the value of k : ");
		int k = s.nextInt();
		
		int[] ans = countDistinctElementInEveryWindow(arr, k);
		for(int a:ans)
			System.out.print(a+ "\t");
		
		s.close();
	}

}