Pastry flavors (CRCFLAV)

Find the longest subarray which is not having at least one of the total flavors. If there are 4 flavors available, any subarray with 1,2 or 3 flavors is a valid candidate for our answer.


Maintain a map/array for keeping a count of total number of elements from each flavor within the subarray and also maintain a start index which will indicate the starting point of our window. Go through each subarrays that has at least 1 missing flavor and record the maximum size amongst all. And every time K turns to 0 we need to increase the K count back to 1 and here we start sliding our window. The start index will move towards the right along with removing the element from its old position from our map/array until K is back to 1.


Time : O(n)
Space : O(n)

public static void main (String[] args) throws java.lang.Exception
    Scanner s = new Scanner(;
	int t = s.nextInt();
	while(t-- > 0) {
		int n = s.nextInt(), k = s.nextInt();
		int [] arr = new int[n];
		for(int i=0;i<n;++i) {
		    arr[i] = s.nextInt();
		int [] map = new int[k+1];
		int max = 0, start = 0;
		for(int i=0;i<arr.length;++i) {
			if(map[arr[i]]++ == 0) --k;
			while(k == 0) {
				if(--map[arr[start++]] == 0) ++k;
			if(k > 0) max = Math.max(max,i-start+1);