Sliding Window / Stuck with subarray

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.

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.

For each test case print visible number of distinct tree at each block separated by space in a separate line.


Sample Input
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?

Obligatory question to ask, problem source ?

1 Like

Uh, not knowing what to do with subarrays. I have to idea.

Using a set data structure would help :thinking:. Use sliding window concept along with set data structure.

1 Like

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.

1 Like

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----
map<int,int> m; // for keeping the track of numbers frequencies.

for (j = 0 ; j < n; j++) {

if (m[arr[j]] == 0) {
while (j - i + 1 > k ) {
  if (m[arr[i]] == 0)


// keeping track of k numbers
if (j - i + 1 == k) {
cout << count<<" ";
correct me if I am wrong.

1 Like

In this problem you can even use brute force O(N* K) instead of O(n*logK).
You can check the code here code


I had mistaken. The naive set data structure will not help here. We need to keep track of frequencies too, so using a map or a dictionary would help.

1 Like

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


    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

t = int(input())
for _ in range(t):
    n, k = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
    countDistinct(a, k, n)