LeetCode 1703. Minimum Adjacent Swaps for K Consecutive Ones Solution in Java, C++, Python & Go | Explanation + Code

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 <= 105
• nums[i] is 0 or 1.
• 1 <= k <= sum(nums)

Solutions

Solution 1: Prefix Sum + Median Enumeration

We can store the indices of 1s in the array nums into an array arr. Next, we preprocess the prefix sum array s of the array arr, where s[i] represents the sum of the first i elements in the array arr.

For a subarray of length k, the number of elements on the left (including the median) is x=^k+1⁄₂, and the number of elements on the right is y=k-x.

We enumerate the index i of the median, where x-1≤ i≤ len(arr)-y. The prefix sum of the left array is ls=s[i+1]-s[i+1-x], and the prefix sum of the right array is rs=s[i+1+y]-s[i+1]. The current median index in nums is j=arr[i]. The number of operations required to move the left x elements to [j-x+1,..j] is a=(j+j-x+1)×^x⁄₂-ls, and the number of operations required to move the right y elements to [j+1,..j+y] is b=rs-(j+1+j+y)×^y⁄₂. The total number of operations is a+b, and we take the minimum of all total operation counts.

The time complexity is O(n), and the space complexity is O(m). Here, n and m are the length of the array nums and the number of 1s in the array nums, respectively.

PythonJavaC++Go

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)