1151. Minimum Swaps to Group All 1's Together

leetcode medium

#array#csharp#leetcode#math#medium#sliding-window#two-pointers

Task

Дан бинарный массив 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.

C# solution

matched/original

public class Solution {
    public int MinSwaps(int[] data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        while (right < data.Length) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = Math.Max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSwaps(vector<int>& data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        while (right < data.size()) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MinSwaps(int[] data) {
        int ones = data.Sum();
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;
        while (right < data.length) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = Math.max(max_one, cnt_one);
        }
        return ones - max_one;
    }
}

JavaScript solution

matched/original

var minSwaps = function(data) {
    const ones = data.reduce((a, b) => a + b, 0);
    let cnt_one = 0, max_one = 0;
    let left = 0, right = 0;

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

Python solution

matched/original

class Solution:
    def minSwaps(self, data):
        ones = sum(data)
        cnt_one = max_one = 0
        left = right = 0

        while right < len(data):
            cnt_one += data[right]
            right += 1
            if right - left > ones:
                cnt_one -= data[left]
                left += 1
            max_one = max(max_one, cnt_one)
        return ones - max_one

Explanation

Algorithm

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

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

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

😎