Длина самой длинной последовательной последовательности, которая может быть сформирована из массива путем преобразования нулей

Учитывая массив arr из N целых чисел, задача состоит в том, чтобы вычислить длину самой длинной последовательности последовательных целых чисел, которая может быть сформирована из массива. Также известно, что 0 в массиве могут быть преобразованы в любое значение.

Пример:

Input: N = 7, A = {0, 6, 5, 10, 3, 0, 11}
Output: 5
Explanation: The maximum consecutive sequence formed can be {3, 4, 5, 6, 7}. As 4, 7 are not present in the array, we can change 2 zeroes to 4 and 7.

Input: N = 6, A = {0, 0, 1, 2, 6, 0}
Output: 6
Explanation: The maximum consecutive sequence formed can be {1, 2, 3, 4, 5, 6}

Подход: Данную задачу можно решить с помощью бинарного поиска и массива сумм префиксов:

• Вычислите общее количество нулей в массиве и сохраните их в переменной count , которая указывает общее количество возможных изменений, которые можно внести.
• Повторяющиеся и нулевые значения в данном массиве удаляются, чтобы массив содержал только уникальные ненулевые значения.
• Создайте вспомогательный массив и инициализируйте значение тех индексов равным 1, значения которых присутствуют в данном массиве.
• Вспомогательный массив превращается в массив префиксных сумм
• Итерировать массив префиксов и на каждой итерации выполнять бинарный поиск с нижним пределом в качестве текущего индекса и верхним пределом в качестве последнего индекса массива
• Пусть текущий индекс равен l , а самый правый возможный индекс — r . Для каждого mid = (l + r) / 2 проверьте, достижим ли этот диапазон [ l , mid ] с общим количеством разрешенных изменений.
• Обновить l = mid +1 , если приведенное выше утверждение верно, в противном случае r = mid – 1
• Рассчитать максимальную длину для всех начальных значений

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

Временная сложность: O (N * log (K)), где K — максимальное значение в массиве.
Вспомогательное пространство: O(N)