1 <= nums.length <= 10^5
nums[i] is 0 or 1.
1 <= k <= sum(nums)

Solution

Method 1 – Greedy + Prefix Sum + Sliding Window

Intuition

To minimize the number of adjacent swaps needed to group k ones together, we can focus on the positions of the ones. The optimal group of k ones will be consecutive in the positions array, and the minimum swaps is the sum of distances to the median position in that group, minus the natural offsets.

Approach

Collect the indices of all ones in the array.
For each window of k consecutive ones, calculate the total moves needed to bring them together using prefix sums and the median.
Use a sliding window to efficiently compute the minimum swaps for all possible groups.
Return the minimum swaps found.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int minMoves(vector<int>& nums, int k) {\n        vector<int> pos;\n        for (int i = 0; i < nums.size(); ++i) if (nums[i] == 1) pos.push_back(i);\n        vector<long long> pre(pos.size()+1);\n        for (int i = 0; i < pos.size(); ++i) pre[i+1] = pre[i] + pos[i];\n        long long ans = LLONG_MAX;\n        for (int i = 0; i + k <= pos.size(); ++i) {\n            int mid = i + k/2;\n            long long left = pre[mid] - pre[i];\n            long long right = pre[i+k] - pre[mid+1];\n            long long moves = right - left;\n            if (k % 2 == 0) moves += pos[mid];\n            ans = min(ans, moves);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minMoves</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><s

Related Tags

Continue Practicing