JavaScript Program to Count Distinct Elements in Every Window
In this problem we are given an array of integers and a number M. We have to find the count of distinct elements in every window of size M in the array using JavaScript.
Example:
Input: arr[] = [1, 2, 1, 3, 4, 2, 3], K = 4
Output: 3 4 4 3
Explanation: First window is [1, 2, 1, 3], count of distinct numbers is 3
Second window is [2, 1, 3, 4] count of distinct numbers is 4
Third window is [1, 3, 4, 2] count of distinct numbers is 4
Fourth window is [3, 4, 2, 3] count of distinct numbers is 3
Table of Content
- Using Naive Approach
- Using HashMap
Using Naive Approach
This approach traverses the array from index 0 to index n-k and then iterates through each window of size k. Within each window, it iterates over the elements and checks for duplicates using a nested loop. If no duplicates are found, it increments the count of distinct elements.
Approach:
- Traverse the array from index 0 to index n-k, where n is the length of the array and k is the window size.
- For each window, iterate over the first k elements using a loop starting from 0 to k-1.
- For each element at index i, iterate over the elements before it (from 0 to i-1) and check if there is any element equal to arr[i].
- If no duplicate is found, increment the count variable indicating a distinct element.
- Return the value of the count variable, which represents the count of distinct elements in the current window.
Example: Implementation to count distinct elements in every window of size k using naive approach.
function windows(arr, k) {
let count = 0;
const seen = new Set();
for (let i = 0; i < k; i++) {
let j;
for (j = 0; j < i; j++) {
if (arr[i] === arr[j]) {
break;
}
}
if (j === i) {
count++;
}
}
return count;
}
function countDistinct(arr, n, k) {
for (let i = 0; i <= n - k; i++) {
console.log(windows(arr.slice(i, i + k), k));
}
}
const arr = [1, 2, 2, 3, 4, 3, 4];
const k = 4;
countDistinct(arr, arr.length, k);
Output
3 3 3 2
Time Complexity: O(n* k*k) Here,k is the window size.
Space Complexity: O(1)
Using HashMap
This approach utilizes a Map data structure to efficiently track the frequency of elements within each window. It employs two pointers, i and j, to define the start and end of the current window. As the window slides through the array, the algorithm updates the Map with the frequency of elements. When the window reaches the desired size k, the size of the Map represents the count of distinct elements within the window.
Approach:
- Create an empty array to store the counts of distinct elements in each window (ans) and initialize a Map (mp) to track the frequency of elements.
- Use two pointers, i and j, to define the start and end of the current window. Iterate over the array using pointer j until it reaches the end.
- For each element A[j], check if it is already present in the Map. If not, add it to the Map and set its frequency to 1. If it exists, increment its frequency in the Map.
- If the size of the current window (j – i + 1) becomes equal to k, push the size of the Map (representing the count of distinct elements) into the ans array.
- Move the window by incrementing pointer i. Update the frequency of the element at A[i] in the Map and delete it if its frequency becomes zero.
- Print or return the counts of distinct elements in each window stored in the ans array.
Example: Implementation to count distinct elements in every window of size k using map.
function countDistinct(A, n, k) {
const ans = [];
const mp = new Map();
let j = 0;
let i = 0;
while (j < n) {
if (!mp.has(A[j])) {
mp.set(A[j], 0);
}
mp.set(A[j], mp.get(A[j]) + 1);
if (j - i + 1 === k) {
ans.push(mp.size);
mp.set(A[i], mp.get(A[i]) - 1);
if (mp.get(A[i]) === 0) {
mp.delete(A[i]);
}
i++;
}
j++;
}
for (const x of ans) {
console.log(x + " ");
}
}
const arr = [1, 2, 2, 3, 4, 3, 4];
const k = 4;
countDistinct(arr, arr.length, k);
Output
3 3 3 2
Time Complexity: O(n)
Space Complexity: O(n)
Contact Us