Минимальная длина подмассива в данном троичном массиве, имеющем 0 в качестве основного элемента

Дан целочисленный массив arr[] размера n , содержащий только три типа целых чисел : 0, 1 и 2 . Найдите минимальную длину подмассива массива arr[] длины >=2, чтобы частота появления нулей в нем превышала количество единиц и двоек . Если не найдено, выведите -1 .

Input : arr[] = {2, 0, 2, 0, 1, 2, 2, 2}
Output : 3
Explanation: {0, 2, 0} from index [2, 4] is the subarray with frequencies of 0’s greater frequencies of 1’s and 2’s.

Input: arr[] = {2, 2, 2, 2}
Output: -1 

Наивный подход: эту задачу можно решить, просматривая каждый подмассив и проверяя частоты 0, 1 и 2, а также проверяя, больше ли частота 0, чем 2 и 1, а затем сохраняя минимальную длину подмассива в качестве ответа.

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

Эффективный подход: поскольку существует только 3 типа целых чисел, возможные подмассивы длины > = 2 , удовлетворяющие вышеуказанному условию, будут

{0, 0}, {0, 1, 0}, {0, 2, 0}, {0, 1, 2, 0}, {0, 2, 1, 0}, {0, 0, 0, 1, 1, 2, 2}, ….

Максимально возможная минимальная длина подмассива будет 7 . Любой другой подмассив, который удовлетворяет вышеуказанному условию с длиной > 7, будет содержать в себе любой из вышеуказанных подмассивов, поэтому максимально возможная длина подмассива, удовлетворяющего вышеуказанному условию, равна 7.

Выполните следующие действия, чтобы решить эту проблему:

• Инициализировать переменную min_length как INT_MAX
• Выполните итерацию в диапазоне [0, n), используя переменную i , и выполните следующие задачи:
  • Инициализировать массив count[] с начальными частотами 0
  • Увеличьте частоту arr[i] с помощью count[arr[i]]++.
  • Выполните итерацию в диапазоне [i+1, min(n, i+7)) с использованием переменной j и выполните следующие задачи:
    • Увеличьте частоту arr[j] с помощью count[arr[j]]++ каждого подмассива размером <=7 .
    • Если count[0] больше, чем count[1] и count[2] , и если min_length > j-i+1 , тогда назначьте min_length = j-i+1
• Если min_length равно INT_MAX , вернуть -1.
• В противном случае напечатайте min_length в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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