Print distinct elements in every window of size k

 Suppose there is an array arr = {1, 2, 3, 4, 2, 3, 4, 5, 6, 7, 6, 7}

If window is of size 4

Distinct elements in {1, 2, 3, 4} are {1, 2, 3, 4} count is 4

Distinct elements in {2, 3, 4, 2} are {2, 3, 4} count is 3

Distinct elements in {3, 4, 2, 3} are {2, 3, 4} count is 3

Distinct elements in {4, 2, 3, 4} are {2, 3, 4} count is 3

We can solve this problem by using HashMap easily.

Step 1: Take first k elements and add them to HashMap. If elements is repeated more than one time store the frequency of element as value in HashMap.

for (i = 0; i < k; i++) {

         if (map.containsKey(arr[i])) {

                  int count = map.get(arr[i]);

                  map.put(arr[i], count + 1);

         } else {

                  map.put(arr[i], 1);

         }

}

Print keys of map.

Step 2: i=0

Step 3:

for(j=k to length of array){

Remove arr[i] from map, if value corresponding to arr[i] is 1, else decrement the value by 1.

i = i +1

if (map.containsKey(arr[j])) {

int count = map.get(arr[j]);

         map.put(arr[j], count + 1);

} else {

         map.put(arr[j], 1);

}

Print keys in Hashmap.

}

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

public class DistinctElements {
 private Map<Integer, Integer> map = new LinkedHashMap<>();

 private void printMap() {
  Set<Integer> keys = map.keySet();
  System.out.println(keys);
 }

 public void distinctElements(int arr[], int k) {

  /* Preconditions check */
  Objects.nonNull(arr);
  if (k > arr.length - 1)
   throw new IllegalArgumentException("window size " + k
     + " must less than array size " + arr.length);

  int i;

  for (i = 0; i < k; i++) {
   if (map.containsKey(arr[i])) {
    int count = map.get(arr[i]);
    map.put(arr[i], count + 1);
   } else {
    map.put(arr[i], 1);
   }
  }

  printMap();

  i = 0;

  for (int j = k; j < arr.length; j++) {

   int value = map.get(arr[i]);
   if (value == 1)
    map.remove(arr[i]);
   else {
    map.put(arr[i], value - 1);
   }

   i++;

   if (map.containsKey(arr[j])) {
    int count = map.get(arr[j]);
    map.put(arr[j], count + 1);
   } else {
    map.put(arr[j], 1);
   }
   printMap();
  }

 }
}

public class DistinctElementsTest {
 public static void main(String args[]){
  DistinctElements elements1 = new DistinctElements();
  DistinctElements elements2 = new DistinctElements();
  DistinctElements elements3 = new DistinctElements();
  DistinctElements elements4 = new DistinctElements();
  
  System.out.println("Distinct elements of window of size 2");
  elements1.distinctElements(new int[]{1, 2, 1, 3, 4, 2, 3, 6, 7}, 2);
  
  System.out.println("Distinct elements of window of size 3");
  elements2.distinctElements(new int[]{1, 2, 1, 3, 4, 2, 3, 6, 7}, 3);
  
  System.out.println("Distinct elements of window of size 4");
  elements3.distinctElements(new int[]{1, 2, 1, 3, 4, 2, 3, 6, 7}, 4);
  
  System.out.println("Distinct elements of window of size 5");
  elements4.distinctElements(new int[]{1, 2, 1, 3, 4, 2, 3, 6, 7}, 5);
 }
}