Count Distinct Element in Every K Size Window
You are given an array ‘ARR’ of size ‘N’ and an integer ‘K’. Your task is to find the total number of distinct elements present in every ‘K’ sized window of the array. A ‘K’ sized window can also be viewed as a series of continuous ‘K’ elements present in the sequence.

Note:

1. The size of ‘ARR’ will always be greater than or equal to the ‘K’. 2. Here window refers to a subarray of ‘ARR’. Hence ‘K’ sized window means a subarray of size ‘K’. 3. You are not required to print the output explicitly. It has already been taken care of. Just implement the function and return an array of the count of all distinct elements in the ‘K’ size window.

Example

Consider ARR = [ 1, 2, 1, 3, 4, 2, 3 ] and K = 3.

As per the given input, we have a sequence of numbers of length 7, and we need to find the number of distinct elements present in all the windows of size 3. Window-1 has three elements { 1, 2, 1 } and only two elements { 1, 2 } are distinct because 1 is repeating two times. Window-2 has three elements { 2, 1, 3 } and all three elements are distinct { 2, 1, 3 }. Window-3 has three elements { 1, 3, 4 } and all three elements are distinct { 1, 3, 4 }. Window-4 has three elements { 3, 4, 2 } and all three elements are distinct { 3, 4, 2 }. Window-5 has three elements { 4, 2, 3 } and all three elements are distinct { 4, 2, 3 }. Hence, the count of distinct elements in all K sized windows is { 2, 3, 3, 3, 3 }.

Input format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains two space-separated integers, 'N' and ‘K’, denoting the number of elements in the array and the size of the window. The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

Output Format:

For each test case, print an array that contains the number of distinct elements in all ‘K’ size windows, and the count of distinct elements must be from the left to the right window. Print the output of each test case in a separate line.

Constraints:

1

Question

Count Distinct Element in Every K Size Window

You are given an array ‘ARR’ of size ‘N’ and an integer ‘K’. Your task is to find the total number of distinct elements present in every ‘K’ sized window of the array. A ‘K’ sized window can also be viewed as a series of continuous ‘K’ elements present in the sequence.

Note:

1. The size of ‘ARR’ will always be greater than or equal to the ‘K’.
2. Here window refers to a subarray of ‘ARR’. Hence ‘K’ sized window means a subarray of size ‘K’.
3. You are not required to print the output explicitly. It has already been taken care of. Just implement the function and return an array of the count of all distinct elements in the ‘K’ size window.

Example

Consider ARR = [ 1, 2, 1, 3, 4, 2, 3 ] and K = 3.

subsequence

As per the given input, we have a sequence of numbers of length 7, and we need to find the number of distinct elements present in all the windows of size 3.

Window-1 has three elements { 1, 2, 1 } and only two elements { 1, 2 } are distinct because 1 is repeating two times.
Window-2 has three elements { 2, 1, 3 } and all three elements are distinct { 2, 1, 3 }.
Window-3 has three elements { 1, 3, 4 } and all three elements are distinct { 1, 3, 4 }.
Window-4 has three elements { 3, 4, 2 } and all three elements are distinct { 3, 4, 2 }.
Window-5 has three elements { 4, 2, 3 } and all three elements are distinct { 4, 2, 3 }.

Hence, the count of distinct elements in all K sized windows is { 2, 3, 3, 3, 3 }.

Input format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and ‘K’, denoting the number of elements in the array and the size of the window.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.

Output Format:

For each test case, print an array that contains the number of distinct elements in all ‘K’ size windows, and the count of distinct elements must be from the left to the right window. 

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 10
1 <= N <= 10 ^ 5
1 <= K <= N
1 <=ARR[i] <= 10 ^ 9

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, ‘K’ denotes the size of the window, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'.

Time limit: 1 second

Accepted Answer

Brute Force

The basic idea of this approach is to check every window of size K and count the number of distinct elements in each window.

Our approach will be to maintain an array answer, which will store the count of the distinct elements in every window. We will traverse through each window and find the number of distinct elements in the current window.

For each element in the window, we will traverse through the window elements and check if the current number has already been included in the number of distinct elements of the current window.
In the end, insert the number of distinct elements in the current window in the array answer.

We will return the array answer.

Algorithm:

Create an array answer, which will store the number of distinct elements in all windows.
Iterate windowNumber from 0 to N - K.
- Set the variable count as 0, which will store the number of distinct elements in the current window.
- Iterate index from windowNumber to windowNumber + K - 1.
  - Set the variable distinctElement as true. The variable distinctElement will store if the current element is distinct in the current window or not.
  - Iterate pos from windowNumber to index - 1.
    - Check if ARR[index] is equal to ARR[pos], then assign distinctElement as false and terminate the loop.
  - Check if distinctElement is true.
    - Increment count by 1.
- Insert count in the array answer.
Return the array answer.

Space Complexity: O(1)Explanation:

O(1).

Constant space is being used. Hence, the overall Space Complexity is O(1).

Time Complexity: OtherExplanation:

O((N - K) * (K ^ 2)), Where N denotes the number of elements in the array, and K denotes the size of the window.

We are doing N - K iterations, and in each iteration, it takes O(K ^ 2) time to count the number of distinct elements in the window. Hence, the overall Time Complexity = O(N - K) * (K ^ 2) = O((N - K) * (K ^ 2)).

Java (SE 1.8)

/*

    Time complexity: O((N - K) * (K ^ 2))

    Space complexity: O(1)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

*/



import java.util.ArrayList;



public class Solution {



	public static ArrayList countDistinctElements(ArrayList arr, int k) {



		int n = arr.size();



		// Create an array to store the number of distinct elements in all windows

		ArrayList answer = new ArrayList(n - k + 1);



		// Traverse through each window

		for (int windowNumber = 0; windowNumber <= n - k; windowNumber++) {



			// The variable count store the number of distinct elements in the current window

			int count = 0;



			// Traverse through the elements present in the current window

			for (int index = windowNumber; index <= windowNumber + k - 1; index++) {



				// The variable distinctElement will store if the current element is distinct in the current window or not

				boolean distinctElement = true;



				for (int pos = windowNumber; pos <= index - 1; pos++) {

					// Check if ARR[index] is equal to ARR[pos]

					int first = arr.get(index), second = arr.get(pos);

					if (first == second) {

						distinctElement = false;

						break;

					}

				}



				// Check if distinctElement is true

				if (distinctElement == true) {

					count += 1;

				}

			}



			// Insert count in the array answer

			answer.add(count);

		}



		// Return the array answer

		return answer;

	}

}

Python (3.5)

'''

    Time complexity: O((N - K) * (K ^ 2))

    Space complexity: O(1)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

'''



def countDistinctElements(arr, k):



    n = len(arr)



    # Create an array to store the number of distinct elements in all windows

    answer = [ 0 for i in range(n - k + 1)]



    # Traverse through each window

    for windowNumber in range(n - k + 1):



        # The variable count store the number of distinct elements in the current window

        count = 0



        # Traverse through the elements present in the current window

        for index in range(windowNumber, windowNumber + k):



            # The variable distinctElement will store if the current element is distinct in the current window or not

            distinctElement = True



            for pos in range(windowNumber, index):



                # Check if ARR[index] is equal to ARR[pos]

                if (arr[index] == arr[pos]):

                    distinctElement = False

                    break

            

            # Check if distinctElement is true

            if (distinctElement == True):

                count += 1

            

        # Insert count in the array answer

        answer[windowNumber] = count



    # Return the array answer

    return answer

C++ (g++ 5.4)

/*

    Time complexity: O((N - K) * (K ^ 2))

    Space complexity: O(1)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

*/



vector countDistinctElements(vector &arr, int k) 

{

    int n = arr.size();



    // Create an array to store the number of distinct elements in all windows

    vector answer(n - k + 1);



    // Traverse through each window

    for (int windowNumber = 0; windowNumber <= n - k; windowNumber++) 

    {

        // The variable count store the number of distinct elements in the current window

        int count = 0;



        // Traverse through the elements present in the current window

        for (int index = windowNumber; index <= windowNumber + k - 1; index++) 

        {

            // The variable distinctElement will store if the current element is distinct in the current window or not

            bool distinctElement = true;



            for (int pos = windowNumber; pos <= index - 1; pos++) 

            {

                // Check if ARR[index] is equal to ARR[pos]

                if (arr[index] == arr[pos]) 

                {

                    distinctElement = false;

                    break;

                }

            }



            // Check if distinctElement is true

            if (distinctElement == true) 

            {

                count += 1;

            }

        }



        // Insert count in the array answer

        answer[windowNumber] = count;

    }



    // Return the array answer

    return answer;

}

Accepted Answer

HashMap

The basic idea of this approach is to store every distinct element present in the window in the HashMap, and we will find the number of distinct elements in the window with the help of HashMap.

Our approach will be to maintain an array answer, which will store the count of the distinct elements in every window. We will traverse through each window and find the number of distinct elements in the current window.

We will check if the current number is not present in the HashMap for each element in the window, then we will insert the current number in the HashMap.
In the end, we will insert the number of distinct elements present in the HashMap in the array answer.

We will return the array answer.

Algorithm:

Create an array answer, which will store the number of distinct elements in all windows.
Iterate windowNumber from 0 to N - K.
- Maintain a HashMap to store distinct elements in the current window.
- Iterate index from windowNumber to windowNumber + K - 1.
  - Check if ARR[index] is not present in the HashMap.
    - Insert ARR[index] in the HashMap.
- Insert the number of elements present in the HashMap in the array answer.
Return the array answer.

Space Complexity: OtherExplanation:

O(K), Where K denotes the size of the window.

The Space Complexity O(K) is used to store distinct elements present in the window in the HashMap. Hence, the overall Space Complexity is O(K).

Time Complexity: OtherExplanation:

O((N - K) * K), Where N denotes the number of elements in the array, and K denotes the size of the window.

We are doing N - K iterations, and in each iteration, it takes O(K) time the number of distinct elements in the window. The Time Complexity to insert an element in the HashMap is O(1). Hence, the overall Time Complexity = O(N - K) * (K) = O((N - K) * K).

Java (SE 1.8)

/*

    Time complexity: O((N - K) * K)

    Space complexity: O(K)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

*/



import java.util.HashMap;

import java.util.ArrayList;



public class Solution {



	public static ArrayList countDistinctElements(ArrayList arr, int k) {



		int n = arr.size();



		// Create an array to store the number of distinct elements in all windows

		ArrayList answer = new ArrayList(n - k + 1);



		// Traverse through each window

		for (int windowNumber = 0; windowNumber <= n - k; windowNumber++) {



			// Maintain a HashMap to store distinct elements in the current window

			HashMap hashMap = new HashMap<>();



			for (int index = windowNumber; index < windowNumber + k; index++) {



				// Check if ARR[index] is not present in the HashMap

				if ( hashMap.containsKey(arr.get(index)) == false) {

					hashMap.put(arr.get(index), true);

				}

			}



			// Insert count in the array answer

			int count = hashMap.size();

			answer.add(count);

		}



		// Return the array answer

		return answer;



	}

}

Python (3.5)

'''

    Time complexity: O((N - K) * K)

    Space complexity: O(K)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

'''



def countDistinctElements(arr, k):

    n = len(arr)



    # Create an array to store the number of distinct elements in all windows

    answer = [0 for i in range(n - k + 1)]



    # Traverse through each window

    for windowNumber in range(n - k + 1):



        # Maintain a HashMap to store distinct elements in the current window

        hashMap = {}



        for index in range(windowNumber, windowNumber + k): 



            # Check if ARR[index] is not present in the HashMap

            if arr[index] not in hashMap:

                hashMap[arr[index]] = True



        # Insert count in the array answer

        count = len(hashMap)

        answer[windowNumber] = count



    # Return the array answer

    return answer

C++ (g++ 5.4)

/*

    Time complexity: O((N - K) * K)

    Space complexity: O(K)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

*/



#include



vector countDistinctElements(vector &arr, int k) 

{

    int n = arr.size();



    // Create an array to store the number of distinct elements in all windows

    vector answer(n - k + 1);



    // Traverse through each window

    for (int windowNumber = 0; windowNumber <= n - k; windowNumber++) 

    {

        // Maintain a HashMap to store distinct elements in the current window

        unordered_map hashMap;



        for (int index = windowNumber; index < windowNumber + k; index++) 

        {

            // Check if ARR[index] is not present in the HashMap

            if (hashMap.find(arr[index]) == hashMap.end()) 

            {

                hashMap[arr[index]] = true;

            }

        }



        // Insert count in the array answer

        int count = hashMap.size();

        answer[windowNumber] = count;

    }



    // Return the array answer

    return answer;

}

Accepted Answer

Sliding Window

The basic idea of this approach is to maintain a window and then slide the window by one element at each step. We will achieve this by using a HashMap to maintain the frequency of elements present in the window. While we are sliding the window, we add an element in the window and remove an element from the window.

Our approach will be to maintain an array answer, which will store the count of the distinct and a HashMap to store the frequency of elements in the current window.

Iterate index from 0 to K - 1 and update the; frequency of ARR[index] in the HashMap. So, we will increment the frequency of ARR[index] in the HashMap by 1. Insert the number of elements present in the current window in the array answer with the help of the HashMap.
Iterate index from K to N - 1. In each iteration, we are deleting the ARR[index - K] from the window. We will decrement the frequency of ARR[index - K] in the HashMap by 1. We are inserting ARR[index] in the window, and we will increment the frequency of ARR[index] by 1. In the end, we will insert the number of the distinct elements present in the HashMap in the array answer.

We will return the array answer.

Algorithm:

Create an array answer, which will store the number of distinct elements in all windows.
Maintain a HashMap to store the frequency of elements in the current window.
Iterate index from 0 to K - 1.
- Increment the frequency of ARR[index] in the HashMap by 1.
Insert the number of elements present in the HashMap in the array answer.
Iterate index from K to N - 1.
- Decrement the frequency of ARR[index - K] in the HashMap by 1.
- Check if the frequency of ARR[index - K] in the HashMap is 0.
  - Delete ARR[index - K] from the HashMap.
- Increment the frequency of ARR[index] in the HashMap by 1.
- Insert the number of elements present in the HashMap in the array answer.
Return the array answer.

Space Complexity: OtherExplanation:

O(K), Where K denotes the size of the window.

The Space Complexity O(K) is used to store distinct elements present in the window in the HashMap. Hence, the overall Space Complexity is O(K).

Time Complexity: O(n)Explanation:

O(N), Where N denotes the number of elements in the array.

We are traversing through the array ARR to find the number of distinct elements in all windows that take O(N) time. The Time Complexity to insert an element in the HashMap and delete an element from the HashMap is O(1). Hence, the overall Time Complexity is O(N).

Java (SE 1.8)

/*

    Time complexity: O(N)

    Space complexity: O(K)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

*/



import java.util.HashMap;

import java.util.ArrayList;



public class Solution {



	public static ArrayList countDistinctElements(ArrayList arr, int k) {



		int n = arr.size();



		// Create an array to store the number of distinct elements in all windows

		ArrayList answer = new ArrayList(n - k + 1);



		// Maintain a HashMap to store the frequency of elements in the current window

		HashMap hashMap = new HashMap<>();



		// Add the frequency of first K element in the HashMap

		for (int i = 0; i < k; i++) {

			Integer j = hashMap.get(arr.get(i));

			hashMap.put(arr.get(i), (j == null) ? 1 : j + 1);

		}



		// Insert the number of distinct elements present in the first window in the array answer

		answer.add( hashMap.size());



		//  Iterate through all remaining windows

		for (int index = k; index < n; index++) {



			// Decrement the frequency of element in the HashMap by 1

			int element = arr.get(index - k);

			hashMap.put(element, hashMap.get(element) - 1);



			// Check if the frequency of element in the HashMap is 0

			if (hashMap.get(element) == 0) {

				hashMap.remove(element);

			}



			// Increment the frequency of ARR[index] in the HashMap by 1



			Integer j = hashMap.get(arr.get(index));

			hashMap.put(arr.get(index), (j == null) ? 1 : j + 1);



			// Insert the number of distinct elements present in the window in the array answer

			int windowNumber = index - k + 1;

			answer.add(hashMap.size());

		}



		// Return the array answer

		return answer;

	}

}

Python (3.5)

'''

    Time complexity: O(N)

    Space complexity: O(K)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

'''



def countDistinctElements(arr, k):

    n = len(arr)



    # Create an array to store the number of distinct elements in all windows

    answer = [0 for i in range(n - k + 1)]



    # Maintain a HashMap to store the frequency of elements in the current window

    hashMap = {}



    # Add the frequency of first K element in the HashMap

    for i in range(k):

        if arr[i] not in hashMap:

            hashMap[arr[i]] = 1

        else:

            hashMap[arr[i]] = hashMap[arr[i]] + 1



    # Insert the number of distinct elements present in the first window in the array answer

    answer[0] = len(hashMap)



    #  Iterate through all remaining windows

    for index in range(k, n):



        # Decrement the frequency of element in the HashMap by 1

        element = arr[index - k]

        if element in hashMap:

            hashMap[element] -= 1



        # Check if the frequency of element in the HashMap is 0

        if (element in hashMap):

            if hashMap[element] == 0:

                hashMap.pop(element)



        # Increment the frequency of ARR[index] in the HashMap by 1

        if arr[index] not in hashMap:

            hashMap[arr[index]] = 1

        else :

            hashMap[arr[index]] = hashMap[arr[index]] + 1

       

        # Insert the number of distinct elements present in the window in the array answer

        windowNumber = index - k + 1

        answer[windowNumber] = len(hashMap)



    # Return the array answer

    return answer

C++ (g++ 5.4)

/*

    Time complexity: O(N)

    Space complexity: O(K)



    Where N denotes the number of elements in the array, and K denotes the size of the window.

*/



#include



vector countDistinctElements(vector &arr, int k) 

{

    int n = arr.size();



    // Create an array to store the number of distinct elements in all windows

    vector  answer(n - k + 1);



    // Maintain a HashMap to store the frequency of elements in the current window

    unordered_map hashMap;



    // Add the frequency of first K element in the HashMap

    for (int i = 0; i < k; i++) 

    {

        hashMap[arr[i]] = hashMap[arr[i]] + 1;

    }



    // Insert the number of distinct elements present in the first window in the array answer

    answer[0] = hashMap.size();



    //  Iterate through all remaining windows

    for (int index = k; index < n; index++) 

    {

        // Decrement the frequency of element in the HashMap by 1

        int element = arr[index - k];

        hashMap[element] -= 1;



        // Check if the frequency of element in the HashMap is 0

        if (hashMap[element] == 0) 

        {

            hashMap.erase(element);

        }



        // Increment the frequency of ARR[index] in the HashMap by 1

        hashMap[arr[index]] = hashMap[arr[index]] + 1;



        // Insert the number of distinct elements present in the window in the array answer

        int windowNumber = index - k + 1;

        answer[windowNumber] = hashMap.size();

    }



    // Return the array answer

    return answer;

}

You are given an array ‘ARR’ of size ‘N’ and an integer ‘K’. Your task is to find the total number of distinct elements present in every ‘K’ sized window of the array. A ‘K’ sized window can also be viewed as a series of continuous ‘K’ elements present in the sequence.

Note:

Example

Input format:

Output Format:

Constraints:

Top WatchGuard Technologies Software Developer interview questions & answers

Popular interview questions of Software Developer