Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

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

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

👨‍💻 Алгоритм:

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution {
    function minSwaps($data) {
        $ones = array_sum($data);
        $cnt_one = 0;
        $max_one = 0;
        $left = 0;
        $right = 0;

        while ($right < count($data)) {
            $cnt_one += $data[$right++];
            if ($right - $left > $ones) {
                $cnt_one -= $data[$left++];
            }
            $max_one = max($max_one, $cnt_one);
        }
        return $ones - $max_one;
    }
}

Ставь 👍 и забирай 📚 Базу знаний