Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1703.html
1703. Minimum Adjacent Swaps for K Consecutive Ones
Level
Hard
Description
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 <= 10^5nums[i]is0or1.1 <= k <= sum(nums)
Solution
If k == 1, then no swap is needed, so return 0.
Loop over nums and obtain all the indices of ones, and calculate the differences between indices of each pair of adjacent ones. Calculate the prefix sums and the postfix sums of the differences.
Obviously, to obtain the minimum swap for k consecutive ones, the ones should be swapped to the middle. For the first k consecutive ones, use the first k - 1 differences to calculate the number of swaps. For the remaining groups of k consecutive ones, use the prefix sums and the postfix sums to update the number of swaps. Maintain the minimum number of swaps in the process. Finally, return the minimum number of swaps.
-
class Solution { public int minMoves(int[] nums, int k) { if (k == 1) return 0; List<Integer> indices = new ArrayList<Integer>(); int length = nums.length; for (int i = 0; i < length; i++) { if (nums[i] == 1) indices.add(i); } int ones = indices.size(); int differencesCount = ones - 1; int[] differences = new int[differencesCount]; for (int i = 1; i < ones; i++) differences[i - 1] = indices.get(i) - indices.get(i - 1) - 1; int[] prefixSums = new int[differencesCount]; prefixSums[0] = differences[0]; for (int i = 1; i < differencesCount; i++) prefixSums[i] = prefixSums[i - 1] + differences[i]; int[] postfixSums = new int[differencesCount]; postfixSums[differencesCount - 1] = differences[differencesCount - 1]; for (int i = differencesCount - 2; i >= 0; i--) postfixSums[i] = postfixSums[i + 1] + differences[i]; int moves = getSum(differences, k); int minMoves = moves; int intervals = k - 1; for (int i = intervals; i < differencesCount; i++) { moves -= getPrefixSum(prefixSums, i - intervals, i - intervals + k / 2 - 1); moves += getPostfixSum(postfixSums, i - k / 2 + 1, i); minMoves = Math.min(minMoves, moves); } return minMoves; } public int getSum(int[] differences, int k) { int sum = 0; int left = 0, right = k - 2; while (left < right) { sum += (differences[left] + differences[right]) * (left + 1); left++; right--; } if (left == right) sum += differences[left] * (left + 1); return sum; } public int getPrefixSum(int[] prefixSums, int start, int end) { if (start == 0) return prefixSums[end]; else return prefixSums[end] - prefixSums[start - 1]; } public int getPostfixSum(int[] postfixSums, int start, int end) { if (end == postfixSums.length - 1) return postfixSums[start]; else return postfixSums[start] - postfixSums[end + 1]; } } ############ class Solution { public int minMoves(int[] nums, int k) { List<Integer> arr = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n; ++i) { if (nums[i] != 0) { arr.add(i); } } int m = arr.size(); int[] s = new int[m + 1]; for (int i = 0; i < m; ++i) { s[i + 1] = s[i] + arr.get(i); } long ans = 1 << 60; int x = (k + 1) / 2; int y = k - x; for (int i = x - 1; i < m - y; ++i) { int j = arr.get(i); int ls = s[i + 1] - s[i + 1 - x]; int rs = s[i + 1 + y] - s[i + 1]; long a = (j + j - x + 1L) * x / 2 - ls; long b = rs - (j + 1L + j + y) * y / 2; ans = Math.min(ans, a + b); } return (int) ans; } } -
class Solution: def minMoves(self, nums: List[int], k: int) -> int: arr = [i for i, x in enumerate(nums) if x] s = list(accumulate(arr, initial=0)) ans = inf x = (k + 1) // 2 y = k - x for i in range(x - 1, len(arr) - y): j = arr[i] ls = s[i + 1] - s[i + 1 - x] rs = s[i + 1 + y] - s[i + 1] a = (j + j - x + 1) * x // 2 - ls b = rs - (j + 1 + j + y) * y // 2 ans = min(ans, a + b) return ans ############ # 1703. Minimum Adjacent Swaps for K Consecutive Ones # https://leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/ class Solution: def minMoves(self, nums: List[int], k: int) -> int: ones = [i for i,x in enumerate(nums) if x] n = len(ones) prefix = [0] for p in ones: prefix.append(prefix[-1] + p) res = float('inf') # k is odd if k & 1: radius = (k-1) // 2 for i in range(radius, n - radius): left = prefix[i] - prefix[i-radius] right = prefix[i+radius+1] - prefix[i+1] res = min(res, right - left) return res - (radius+1)*radius # k is even else: radius = (k-2) // 2 for i in range(radius, n - radius - 1): left = prefix[i] - prefix[i-radius] right = prefix[i+radius+2] - prefix[i+1] res = min(res, right - left - ones[i]) return res - (radius+1)*radius - (radius+1) def minMoves(self, nums: List[int], k: int) -> int: ones = [i for i,x in enumerate(nums) if x] n = len(ones) prefix = [0] for p in ones: prefix.append(prefix[-1] + p) res = float('inf') for i in range(n - k + 1): right = prefix[i+k] - prefix[k//2 + i] left = prefix[(k+1)//2 + i] - prefix[i] res = min(res, right - left) res -= (k//2)*((k+1)//2) return res -
class Solution { public: int minMoves(vector<int>& nums, int k) { vector<int> arr; for (int i = 0; i < nums.size(); ++i) { if (nums[i]) { arr.push_back(i); } } int m = arr.size(); long s[m + 1]; s[0] = 1; for (int i = 0; i < m; ++i) { s[i + 1] = s[i] + arr[i]; } long ans = 1L << 60; int x = (k + 1) / 2; int y = k - x; for (int i = x - 1; i < m - y; ++i) { int j = arr[i]; int ls = s[i + 1] - s[i + 1 - x]; int rs = s[i + 1 + y] - s[i + 1]; long a = (j + j - x + 1L) * x / 2 - ls; long b = rs - (j + 1L + j + y) * y / 2; ans = min(ans, a + b); } return ans; } }; -
func minMoves(nums []int, k int) int { arr := []int{} for i, x := range nums { if x != 0 { arr = append(arr, i) } } s := make([]int, len(arr)+1) for i, x := range arr { s[i+1] = s[i] + x } ans := 1 << 60 x := (k + 1) / 2 y := k - x for i := x - 1; i < len(arr)-y; i++ { j := arr[i] ls := s[i+1] - s[i+1-x] rs := s[i+1+y] - s[i+1] a := (j+j-x+1)*x/2 - ls b := rs - (j+1+j+y)*y/2 ans = min(ans, a+b) } return ans } func min(a, b int) int { if a < b { return a } return b }