Минимальный MEX из всех подмассивов длины K

Учитывая массив arr[] , состоящий из N различных положительных целых чисел и целого числа K , задача состоит в том, чтобы найти минимальный MEX из всех подмассивов длины K .

The MEX is the smallest positive integer that is not present in the array.

Примеры:

Input: arr[] = {1, 2, 3}, K = 2
Output: 1
Explanation:
All subarrays of length 2 are {1, 2}, {2, 3}.
In subarray {1, 2}, the smallest positive integer which is not present is 3.
In subarray {2, 3}, the smallest positive integer which is not present is 1.
Therefore, the minimum of all the MEX for all subarrays of length K (= 2) is 1.

Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Output: 1

Наивный подход: самый простой подход к решению проблемы состоит в том, чтобы сгенерировать все подмассивы длины K и найти MEX для каждого подмассива. После нахождения всех MEX выведите минимум из полученных.
Временная сложность: O(K * N ² )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью метода «Установить и скользящее окно». Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную, скажем, mex , чтобы сохранить минимум среди всех MEX подмассивов размера K.
• Инициализируйте набор S для хранения значений, которых нет в текущем подмассиве. Изначально вставьте в него все числа из диапазона [1, N + 1] , потому что изначально размер окна равен 0 .
• Перебрать диапазон [0, K – 1] и удалить элемент arr[i] из набора.
• Теперь первым элементом набора является MEX подмассива в диапазоне [0, K] и сохраните это значение в mex .
• Теперь выполните итерацию по диапазону [K, N – 1] и выполните следующие шаги:
  • Вставьте элемент arr[i] в набор.
  • Сотрите elementarr[i – K] из набора.
  • Теперь первым элементом набора является MEX для текущего подмассива. Поэтому обновите значение mex до минимума mex и первого элемента набора .
• После выполнения вышеуказанных шагов выведите значение mex в качестве минимального MEX среди всех подмассивов размера K.

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

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