Задача с собеседования в Josh Technology

Обмен определяется как выбор двух различных позиций в массиве и перестановка их значений местами.
Круговой массив определяется как массив, в котором первый и последний элементы считаются соседними.

Дан бинарный круговой массив nums. Верните минимальное количество обменов, необходимых для того, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте.

Пример 1:
Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Есть несколько способов сгруппировать все 1 вместе:
[0,0,1,1,1,0,0] с использованием 1 обмена.
[0,1,1,1,0,0,0] с использованием 1 обмена.
[1,1,0,0,0,0,1] с использованием 2 обменов (используя круговое свойство массива).
Не существует способа сгруппировать все 1 вместе, не выполнив ни одного обмена.
Таким образом, минимальное необходимое количество обменов - 1.

Пример 2:
Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Есть несколько способов сгруппировать все 1 вместе:
[1,1,1,0,0,0,0,1,1] с использованием 2 обменов (используя круговое свойство массива).
[1,1,1,1,1,0,0,0,0] с использованием 2 обменов.
Не существует способа сгруппировать все 1 вместе с использованием 0 или 1 обменов.
Таким образом, минимальное необходимое количество обменов - 2.

Пример 3:
Input: nums = [1,1,0,0,1]
Output: 0
Explanation: Все 1 уже сгруппированы вместе, учитывая круговое свойство массива.
Таким образом, минимальное количество обменов - 0.

Ограничения:
1 <= nums.length <= 10⁵
nums[i] равно 0 или 1.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Обратим внимание, что кол-во единиц, которые нужно сгруппировать, фиксировано и равняется общему кол-ву единиц в массиве (total_ones). Так как единицы могут быть разбросаны по массиву, необходимо проверить каждый подмассив длиной total_ones и определить среди них тот, в котором уже находится максимальное кол-во единиц (а следовательно потребуется меньше обменов).
=> Кол-во необходимых обменов равняется кол-ву нулей в подмассиве с максимумом единиц (кол-во нулей = total_ones - максимальное кол-во единиц в окне).

Чтобы избежать повторного подсчёта нулей в подмассиве, используем метод "скользящего окна" с двумя указателями.

total_ones - размер окна (определяем методом count())
window_ones - счётчик единиц в текущем окне
max_window_ones - лучший результат по кол-ву единиц в окне
l - левая граница окна
r - правая граница окна

Если общее кол-во единиц в массиве равно 1 или 0:
- возвращаем 0, так как группировать нечего.

Для корректной обработки окон в циклическом массиве - проходим 2n итераций, беря индексы по модулю (% n), что позволит вернуться в начало при выходе за правую границу.

Проходим по массиву правым указателем:
- Добавляем правый эл-т в окно.

- Если длина окна превысила total_ones:
- убираем один эл-т слева;
- сдвигаем l вправо.

- Обновляем max_window_ones.

Возвращаем ответ как разность между общим кол-вом единиц и кол-вом единиц в наиболее «единичном» окне.

Сложность
O(n) - по времени (проходим 2n итераций, константа отбрасывается)
O(1) - по памяти (храним некоторое кол-во переменных)

Код
class Solution:
def minSwaps(self, nums: list[int]) -> int:
n = len(nums)
total_ones = nums.count(1)

if total_ones <= 1:
return 0

l = 0
window_ones = max_window_ones = 0

for r in range(n * 2):
window_ones += nums[r % n]

if r - l + 1 > total_ones:
window_ones -= nums[l % n]
l += 1

max_window_ones = max(max_window_ones, window_ones)

return total_ones - max_window_ones

Оптимизация
Решение можно оптимизировать, сохранив текущую асимптотику:
Так как размер окна фиксирован (total_ones), можем обойтись без левого указателя: считаем кол-во единиц в первом окне, а затем проходим по массиву, совершая n сдвигов. На каждой итерации прибавляем входящий эл-т и вычитаем уходящий. Проверка на превышение длины окна не требуется.
Кол-во операций сократится до n (сдвиги) + total_ones (построение первого окна).
Пишите оптимизированный вариант кода в комментариях!

@algoses