Distinct Numbers in Window Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/distinct-numbers-window

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array A  and a value k, find the number of distinct elements in each window(subarray) of size k.

Naive Approach

The naive approach is to check every subarray of length k and count the number of distinct elements present in it.

• For every index between i = 0 to i = n - k , run a loop from j = i to j = i + k which will be the current window.
• For each element in the window, compare it with all the previous elements in the same window and if the current element is not equal to any of the previous elements, increment the count of distinct elements in that window.
• Insert the count of distinct elements for each window in the answer array.

Analysis

• Time Complexity: O(n * k2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<int> distintNumbersInWindow(vector<int> &A, int k) {
	int n = A.size();
	vector<int> ans;
	for(int i = 0; i <= n - k; i++) {
		int distinctElements = 0;
		for(int j = i; j < i + k; j++) {
			int flag = 1;
			for(int indx = i; indx < j; indx++) {
				if(A[indx] == A[j]) {
					flag = 0;
					break;
				}
			}
			if(flag == 1) {
				distinctElements++;
			}
		}
		ans.push_back(distinctElements);
	}
	return ans;
}

Java

class Solution {
	int[] distintNumbersInWindow(int[] A, int k) {
	    int n = A.length;
		int[] ans = new int[n - k + 1];
		int ansIndex = 0;
		for(int i = 0; i <= n - k; i++) {
			int distinctElements = 0;
			for(int j = i; j < i + k; j++) {
				int flag = 1;
				for(int indx = i; indx < j; indx++) {
					if(A[indx] == A[j]) {
						flag = 0;
						break;
					}
				}
				if(flag == 1) {
					distinctElements++;
				}
			}
			ans[ansIndex++] = distinctElements;
		}
		return ans;
	}
}

Optimal Approach

The optimal solution is based on the idea that every two consecutive windows will have k - 1 common elements. Using the hashmap can efficiently count the number of distinct elements in a window since we have to just decrement the count of the first element of the previous window and increment the count of the last element of the new window while traversing the array.

• Create an empty hashmap.
• Traverse the array from i = 0 to i = n.
• For the first k elements, insert them in the hashmap while keeping the count of distinct elements. When the kth element is encountered, add the count of the distinct elements in the answer array.
• For the rest of the n - k elements remove the (i - k)th element from the hashmap and add the ith element while keeping the count of the distinct elements. Add the count of distinct elements in the answer array for every i up to n.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

vector<int> distintNumbersInWindow(vector<int> &A, int k) {
	int n = A.size();
	vector<int> ans;
	unordered_map<int, int> elementCnt;
	int distinctElements = 0;
	for(int i = 0; i < n; i++) {
		if(i < k) {
			if(elementCnt[A[i]] == 0) {
				distinctElements++;
			}
			elementCnt[A[i]]++;
			if(i == k - 1) {
				ans.push_back(distinctElements);
			}
		} else {
			if(elementCnt[A[i - k]] == 1) {
				distinctElements--;
			}
			elementCnt[A[i - k]]--;
			if(elementCnt[A[i]] == 0) {
				distinctElements++;
			}
			elementCnt[A[i]]++;
			ans.push_back(distinctElements);
		}
		
	}
	return ans;
}

Java

class Solution {
	int[] distintNumbersInWindow(int[] A, int k) {
	    int n = A.length;
		int[] ans = new int[n - k + 1];
		HashMap<Integer, Integer> elementCnt = new HashMap<Integer, Integer>();
		int ansIndx = 0;
		for(int i = 0; i < n; i++) {
			if(i < k) {
				elementCnt.put(A[i], elementCnt.getOrDefault(A[i], 0) + 1);
				if(i == k - 1) {
					ans[ansIndx++] = elementCnt.size();
				}
			} else {
				if(elementCnt.get(A[i - k]) == 1) {
					elementCnt.remove(A[i - k]);
				} else {
					elementCnt.put(A[i - k], elementCnt.get(A[i - k]) - 1);
				}
				elementCnt.put(A[i], elementCnt.getOrDefault(A[i], 0) + 1);
				ans[ansIndx++] = elementCnt.size();
			}

		}
		return ans;
	}
}