Given an array of integers and a window size k, count the number of distinct elements in every window of size k as it slides from the start to the end of the array.
Input/Output Examples
plaintext
Example 1:
Input:
arr = [1, 2, 1, 3, 4, 2, 3]
k = 4
Output: [3, 4, 4, 3]
Explanation: The distinct elements in each window of size 4 are:
[1, 2, 1, 3] has 3 distinct elements: {1, 2, 3}
[2, 1, 3, 4] has 4 distinct elements: {1, 2, 3, 4}
[1, 3, 4, 2] has 4 distinct elements: {1, 2, 3, 4}
[3, 4, 2, 3] has 3 distinct elements: {2, 3, 4}
Example 2:
Input:
arr = [4, 1, 1, 1, 2, 3, 4]
k = 3
Output: [2, 1, 2, 3, 3]
Explanation: The distinct elements in each window of size 3 are:
[4, 1, 1] has 2 distinct elements: {1, 4}
[1, 1, 1] has 1 distinct element: {1}
[1, 1, 2] has 2 distinct elements: {1, 2}
[1, 2, 3] has 3 distinct elements: {1, 2, 3}
[2, 3, 4] has 3 distinct elements: {2, 3, 4}
Example 3:
Input:
arr = [2, 2, 2, 2]
k = 2
Output: [1, 1, 1]
Explanation: Each window has only 1 distinct element.
Approach to Count Distinct Elements in Every Window
- Use a Hash Map to Track Frequencies in the Current Window:
- Initialize a hash map to store the frequency of each element in the current window of size
k.
- Initialize a hash map to store the frequency of each element in the current window of size
- Slide the Window and Update the Distinct Count:
- For the first window, add elements to the map and count distinct elements.
- As you slide the window to the right, remove the element that goes out of the window and update its frequency. If its count reaches zero, remove it from the map.
- Add the new element that comes into the window, update its frequency, and adjust the count of distinct elements.
- Store the Count for Each Window:
- Append the count of distinct elements to the result list for each window.
C++ Program to Count Distinct Elements in Every Window
cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
// Function to count distinct elements in every window of size k
vector<int> countDistinctInWindow(const vector<int>& arr, int k) {
unordered_map<int, int> freqMap;
vector<int> result;
int distinctCount = 0;
// Initialize the first window
for (int i = 0; i < k; i++) {
if (++freqMap[arr[i]] == 1) {
distinctCount++;
}
}
result.push_back(distinctCount);
// Slide the window
for (int i = k; i < arr.size(); i++) {
// Remove the element going out of the window
if (--freqMap[arr[i - k]] == 0) {
distinctCount--;
freqMap.erase(arr[i - k]);
}
// Add the new element coming into the window
if (++freqMap[arr[i]] == 1) {
distinctCount++;
}
result.push_back(distinctCount);
}
return result;
}
int main() {
vector<int> arr = {1, 2, 1, 3, 4, 2, 3};
int k = 4;
vector<int> result = countDistinctInWindow(arr, k);
cout << "Distinct elements in each window of size " << k << ": ";
for (int count : result) {
cout << count << " ";
}
cout << endl;
return 0;
}
Java Program to Count Distinct Elements in Every Window
java
import java.util.*;
public class DistinctElementsInWindow {
// Function to count distinct elements in every window of size k
public static List<Integer> countDistinctInWindow(int[] arr, int k) {
Map<Integer, Integer> freqMap = new HashMap<>();
List<Integer> result = new ArrayList<>();
int distinctCount = 0;
// Initialize the first window
for (int i = 0; i < k; i++) {
freqMap.put(arr[i], freqMap.getOrDefault(arr[i], 0) + 1);
if (freqMap.get(arr[i]) == 1) {
distinctCount++;
}
}
result.add(distinctCount);
// Slide the window
for (int i = k; i < arr.length; i++) {
// Remove the element going out of the window
int outElement = arr[i - k];
if (freqMap.get(outElement) == 1) {
distinctCount--;
}
freqMap.put(outElement, freqMap.get(outElement) - 1);
if (freqMap.get(outElement) == 0) {
freqMap.remove(outElement);
}
// Add the new element coming into the window
int inElement = arr[i];
freqMap.put(inElement, freqMap.getOrDefault(inElement, 0) + 1);
if (freqMap.get(inElement) == 1) {
distinctCount++;
}
result.add(distinctCount);
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 1, 3, 4, 2, 3};
int k = 4;
List<Integer> result = countDistinctInWindow(arr, k);
System.out.println("Distinct elements in each window of size " + k + ": " + result);
}
}
Python Program to Count Distinct Elements in Every Window
python
from collections import defaultdict
# Function to count distinct elements in every window of size k
def count_distinct_in_window(arr, k):
freq_map = defaultdict(int)
result = []
distinct_count = 0
# Initialize the first window
for i in range(k):
if freq_map[arr[i]] == 0:
distinct_count += 1
freq_map[arr[i]] += 1
result.append(distinct_count)
# Slide the window
for i in range(k, len(arr)):
# Remove the element going out of the window
out_element = arr[i - k]
if freq_map[out_element] == 1:
distinct_count -= 1
freq_map[out_element] -= 1
if freq_map[out_element] == 0:
del freq_map[out_element]
# Add the new element coming into the window
in_element = arr[i]
if freq_map[in_element] == 0:
distinct_count += 1
freq_map[in_element] += 1
result.append(distinct_count)
return result
# Example usage
if __name__ == "__main__":
arr = [1, 2, 1, 3, 4, 2, 3]
k = 4
result = count_distinct_in_window(arr, k)
print("Distinct elements in each window of size", k, ":", result)
- Time Complexity:
O(n), wherenis the length of the array. Each element is processed at most twice: once when it enters the window and once when it exits. - Space Complexity:
O(k), due to the hash map used to store the frequency of elements within the current window.