Problem Statement
There is a road of N blocks and at each block, there is tree represented by a number. Groot is standing at the 1st block and he can see only K blocks ahead of him(including the standing block) and he starts walking block by block. Print distinct number of trees visible to Groot at each block. Groot will stop walking when the last tree becomes visible to him.
Input
First Line of the input contains an integer T denoting the number of test cases. The first line of each test case contains N and K. Next Line contains N space separated integers denoting types of tree.
Output
For each test case print visible number of distinct tree at each block separated by space in a separate line.
Constraints
1<=T<=10
1<=N<=100
1<=K<=N
Sample Input 1 7 4 1 2 1 3 4 2 3
Sample Output 3 4 4 3
The question is what approach should I have to solve this task?
The subarrays are: [1, 2, 1, 3] [2, 1, 3, 4] [1, 3, 4, 2] [3, 4, 2, 3]
And what is needed to do with it to get 3 4 4 3 for each subarray?
its simple 2 pointer problem, you can maintain a window of size k ( i pointing to starting index of window, j pointing to ending of window).
You can make 1st window by a simple for loop, then for each next window increase both i and j by 1, along with taking jth element in account and removing contribution of ith element.
You can use map<char, int> freq for keeping track of distinct characters, freq.size() will give number of distinct elements in each window.
while removing ith element, check if its freq becomes 0 or not, if it becomes 0 then remove that character from map.
create 2 pointer i =0, j=0 and then also use a count variable to keep the track of distinct numbers.
pseudo code for better Understanding----
i=0,j=0
count=0;
map<int,int> m; // for keeping the track of numbers frequencies.
for (j = 0 ; j < n; j++) {
if (m[arr[j]] == 0) {
count++;
}
m[arr[j]]++;
while (j - i + 1 > k ) {
m[arr[i]]--;
if (m[arr[i]] == 0)
count--;
i++;
}
// keeping track of k numbers
if (j - i + 1 == k) {
cout << count<<" ";
}
}
correct me if I am wrong.
I made a program and it passes only 1 case out of 3. Where am I wrong?
from collections import defaultdict
def countDistinct(arr, k, n):
out = []
mp = defaultdict(lambda: 0)
dist_count = 0
for i in range(k):
if mp[arr[i]] == 0:
dist_count += 1
mp[arr[i]] += 1
out.append(dist_count)
for i in range(k, n):
if mp[arr[i - k]] == 1:
dist_count -= 1
mp[arr[i - k]] -= 1
if mp[arr[i]] == 0:
dist_count += 1
mp[arr[i]] += 1
out.append(dist_count)
print(*out)
t = int(input())
for _ in range(t):
n, k = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
countDistinct(a, k, n)
. Use sliding window concept along with set data structure.