You are given an integer array, nums, and an integer k. nums comprises of only 0‘s and 1‘s. In one move, you can choose two adjacent indices and swap their values.
Return the minimum number of moves required so that nums has k consecutive 1‘s.
Example 1:
Input: nums = [1,0,0,1,0,1], k = 2 Output: 1 Explanation: In 1 move, nums could be [1,0,0,0,1,1] and have 2 consecutive 1's.
Example 2:
Input: nums = [1,0,0,0,0,0,1,1], k = 3 Output: 5 Explanation: In 5 moves, the leftmost 1 can be shifted right until nums = [0,0,0,0,0,1,1,1].
Example 3:
Input: nums = [1,1,0,1], k = 2 Output: 0 Explanation: nums already has 2 consecutive 1's.
Constraints:
1 <= nums.length <= 105nums[i]is0or1.1 <= k <= sum(nums)
Solution: Prefix Sum + Sliding Window
Time complexity: O(n)
Space complexity: O(n)
We only care positions of 1s, we can move one element from position x to y (assuming x + 1 ~ y are all zeros) in y – x steps. e.g. [0 0 1 0 0 0 1] => [0 0 0 0 0 1 1], move first 1 at position 2 to position 5, cost is 5 – 2 = 3.
Given a size k window of indices of ones, the optimal solution it to use the median number as center. We can compute the cost to form consecutive numbers:
e.g. [1 4 7 9 10] => [5 6 7 8 9] cost = (5 – 1) + (6 – 4) + (9 – 8) + (10 – 9) = 8
However, naive solution takes O(n*k) => TLE.
We can use prefix sum to compute the cost of a window in O(1) to reduce time complexity to O(n)
First, in order to use sliding window, we change the target of every number in the window to the median number.
e.g. [1 4 7 9 10] => [7 7 7 7 7] cost = (7 – 1) + (7 – 4) + (7 – 7) + (9 – 7) + (10 – 7) = (9 + 10) – (1 + 4) = right – left.
[5 6 7 8 9] => [7 7 7 7 7] takes extra 2 + 1 + 1 + 2 = 6 steps = (k / 2) * ((k + 1) / 2), these extra steps should be deducted from the final answer.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: int minMoves(vector<int>& nums, int k) { vector<long> s(1); for (int i = 0; i < nums.size(); ++i) if (nums[i]) s.push_back(s.back() + i); const int n = s.size(); long ans = 1e10; const int m1 = k / 2, m2 = (k + 1) / 2; for (int i = 0; i + k < n; ++i) { const long right = s[i + k] - s[i + m1]; const long left = s[i + m2] - s[i]; ans = min(ans, right - left); } return ans - m1 * m2; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def minMoves(self, nums: List[int], k: int) -> int: ans = 1e10 s = [0] for i, v in enumerate(nums): if v: s.append(s[-1] + i) n = len(s) m1 = k // 2 m2 = (k + 1) // 2 for i in range(n - k): right = s[i + k] - s[i + m1] left = s[i + m2] - s[i] ans = min(ans, right - left) return ans - m1 * m2 |