Проверьте, отсутствует ли подпоследовательность размера K в данном массиве.

Дан массив размера N и два целых числа M и K. Все целые числа в массиве находятся в диапазоне [1, M]. Найдите, отсутствует ли в массиве какая-либо возможная подпоследовательность размера K , такая, что все целые числа этой подпоследовательности также находятся в диапазоне [1, M].

Примеры:

Input: arr[] = {2, 3, 3, 1, 2, 3, 2}, M = 3, K = 3
Output: YES
Explanation: The sequence {1, 3, 2} of size 3 is missing in the array 
and there are many other subsequences also which are missing in the array

Input: arr[] = {4, 3, 1, 3, 2, 4, 1, 1, 2, 3}, M = 4, K = 2
Output: NO
Explanation: No subsequence of size 2 is missing from the array

Найдите недостающую подпоследовательность размера K, используя хеширование:

Find continuous blocks of integers in the array, which contains all the numbers in the range [1, M]. If one such block is found then every subsequence of size 1 is present in the array, as every number appears once in this block. 

Similarly if two such blocks are found in the array, then every subsequence of size 2 is present in the array and so on. So if  count of such blocks is less than K, then the answer is “YES”, else “NO”

Выполните указанные шаги, чтобы решить проблему:

• Объявите карту для хранения количества каждого целого числа и двух переменных count и freq для хранения количества найденных блоков и количества различных целых чисел, найденных в этом текущем блоке соответственно.
• Итерация по массиву
  • Увеличьте количество каждого элемента на карте
  • Если элемент виден впервые, то увеличить частоту на единицу
  • Если freq равна M (что означает, что найден один блок), то увеличьте переменную count на единицу и очистите карту, и установите переменную freq обратно в ноль, чтобы можно было найти следующий блок
• Если количество таких блоков меньше K , то ответ «ДА», иначе «НЕТ».

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)