<p>You are given an integer array, <code>nums</code>, and an integer <code>k</code>. <code>nums</code> comprises of only <code>0</code>&#39;s and <code>1</code>&#39;s. In one move, you can choose two <strong>adjacent</strong> indices and swap their values.</p>

<p>Return <em>the <strong>minimum</strong> number of moves required so that </em><code>nums</code><em> has </em><code>k</code><em> <strong>consecutive</strong> </em><code>1</code><em>&#39;s</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,1,0,1], k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> In 1 move, nums could be [1,0,0,0,<u>1</u>,<u>1</u>] and have 2 consecutive 1&#39;s.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,0,0,0,0,0,1,1], k = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,<u>1</u>,<u>1</u>,<u>1</u>].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,0,1], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> nums already has 2 consecutive 1&#39;s.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums[i]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>1 &lt;= k &lt;= sum(nums)</code></li>
</ul>

class Solution_brute_force {
public:
    int minMoves(vector<int>& nums, int k)
    {
        std::vector<int> idxAllOnes;
        for(int idx = 0; idx < nums.size(); ++idx)
        {            
            if (nums[idx] == 1)
            {
                idxAllOnes.push_back(idx);
            }
        }

        const int totalOnes = static_cast<int>(idxAllOnes.size());
        assert(k <= totalOnes && k >= 1);

        /// sliding windows
        int idxWinLeft = 0;
        int idxWinRight = idxWinLeft + k - 1;
        int minSteps = INT_MAX;
        while(idxWinRight < totalOnes)
        {
            int idxPivot = (idxWinLeft + idxWinRight) / 2;
            int steps = 0;
            for(int idx = idxWinLeft; idx <= idxWinRight; ++idx)
            {
                int idxOneExpected = idxAllOnes[idxPivot] - (idxPivot - idx);
                steps += std::abs(idxOneExpected - idxAllOnes[idx]);
            }
            if (steps < minSteps)
            {
                minSteps = steps;
            }
            ++idxWinLeft;
            ++idxWinRight;
        }
        return minSteps;
    }
};

/// https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/987607/O(n)-explanation-with-picture/

//// https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/solutions/2725658/c-solution-with-explanation-reference-o-n-sliding-window-prefix-sum/

class Solution {
public:
    int minMoves(vector<int>& nums, int k)
    {
        using ll = long long;

        int i, n = nums.size(), l, r;
        vector<ll> a;   // Indexes array
        a.push_back(0); // Make indexes array the same size as prefix array
        for(i=0; i<n; i++)
            if(nums[i])
                a.push_back(i);
        n = a.size();
        vector<ll> pref(n, 0);  // Prefix array
        for(i=1; i<n; i++)     // prefix[i] = sum of all elements from a[0] to a[i - 1]
            pref[i] = a[i] + pref[i - 1];
        
        ll ret = 1e18;
        
        // Rolling window [l...r] of length k
        for(l=1,r=k; r<n; ++l, ++r) {
            int mid = (l + r) / 2;  // Mid-point - current element
            int radius = mid - l;   // How many elements on each side
            ll right = pref[r] - pref[mid];     // Prefix of radius elements to the right of mid
            ll left = pref[mid - 1] - pref[l - 1];  // Prefix of radius elements to the left of mid
            ll subtract = static_cast<int64_t>(radius) * (radius + 1);  // Once all elements are equal, make it a sequence
            if(k % 2 == 0) {        // Special case if k is even
                left += a[mid];     // Deduct current element
                subtract += (radius + 1);   // Deduct the cost of the furthest right element
            }
            ret = min(ret, right - left - subtract);
        }
        return ret;


        // Solution_brute_force sol_brute;
        // return sol_brute.minMoves(nums, k);
    }
};
147300