minimum-adjacent-swaps-for-k-consecutive-ones.cpp

// Time:  O(n)
// Space: O(n)

class Solution {
public:
    int minMoves(vector<int>& nums, int k) {
        vector<int> idxs;
        for (int i = 0; i < size(nums); ++i) {
            if (nums[i]) {
                idxs.emplace_back(i);
            }
        }
        vector<uint64_t> prefix(size(idxs) + 1);
        for (int i = 0; i < size(idxs); ++i) {
            prefix[i + 1] = prefix[i] + idxs[i];
        }
        const auto& score = [&prefix](int i, int j) {
                                return prefix[j + 1] - prefix[i];
                            };
        uint64_t result = numeric_limits<uint64_t>::max();
        for (int i = 0; i < size(idxs) - k + 1; ++i) {
            result = min(result, -score(i, i + k / 2 - 1) + score(i + (k + 1) / 2, i + k - 1));  // take each i+k//2 as median, find min dist to median
        }
        result -= (k / 2) * ((k + 1) / 2);  // rollback extra moves to the expected positions
        return result;
    }
};