#1561Time: O(N + m*k), where `N` is the length of `nums`, `m` is the number of ones, and `k` is the target number of consecutive ones. O(N) is for finding the indices of all ones. The main logic involves a sliding window that runs `m-k+1` times, and inside each window, we perform O(k) work to calculate the cost. In the worst case, this becomes O(N^2).Space: O(m), where `m` is the number of ones in the input array. This is for storing the indices of the ones and the transformed `g` array. In the worst case, `m` can be up to `N`, so the space complexity is O(N).1 company
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 kconsecutive1'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)
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first identifies the indices of all 1s in the input array. Then, it considers every possible consecutive block of k ones from this list of indices. For each block, it calculates the minimum swaps required to make them physically adjacent in the original array. The minimum of these costs over all blocks is the answer. This is done by iterating through all possible sliding windows of size k over the list of 1's indices and, for each window, calculating the cost by summing up the moves required for each 1.
Algorithm
First, iterate through the input array nums to find all indices where the value is 1. Store these indices in a list, let's call it ones_indices.
The core of the problem is to select k ones from ones_indices that can be made consecutive with the minimum number of swaps. Since the relative order of the 1s cannot be changed by adjacent swaps, we must select a contiguous sub-array of k indices from ones_indices.
We can use a sliding window of size k to iterate through all possible contiguous groups of k ones. Let the window start at index i and end at i+k-1 of the ones_indices list.
For each window, we need to calculate the minimum swaps to make these k ones adjacent. This is a classic problem where the cost is minimized by gathering all elements around their median. The total number of swaps is the sum of absolute differences of each element's final position from its original position.
A key insight simplifies the cost calculation. The cost to move a group of 1s at original indices p_0, p_1, ..., p_{k-1} to a consecutive block is sum(|(p_j - j) - (p_median - median_idx)|). Let's define a new array g where g[x] = ones_indices[x] - x. The cost for a window starting at i is sum_{j=i}^{i+k-1} |g[j] - g[median_idx]|, where median_idx = i + k/2.
For each window, we iterate from j = i to i+k-1, calculate this sum, and keep track of the minimum sum found across all windows.
The final minimum sum is the answer.
Walkthrough
The fundamental principle is that adjacent swaps preserve the relative order of elements. This means if we decide to group a certain set of k ones, the first 1 in that group (in the original array) must remain the first 1 in the final consecutive block. This restricts our choices to contiguous subarrays of size k from the list of all 1's indices.
For a chosen group of k ones, the problem reduces to finding the minimum number of moves to make them adjacent. This is a well-known result: the total moves are minimized when the elements are gathered around their median. The total cost can be expressed as the sum of moves for each 1 to its target position in the final consecutive block.
A crucial transformation simplifies the cost calculation. If the original indices of the k ones are p_0, p_1, ..., p_{k-1}, the cost is sum(|(p_j - j) - C|) where C is a constant chosen to be the median of the values (p_j - j). This transformed value p_j - j essentially represents the number of 0s before the j-th 1.
The naive approach iterates through each possible window of k ones, and for each window, it explicitly calculates this sum by iterating through all k elements, leading to a nested loop structure.
1class Solution {2 public int minMoves(int[] nums, int k) {3 java.util.List<Integer> ones = new java.util.ArrayList<>();4 for (int i = 0; i < nums.length; i++) {5 if (nums[i] == 1) {6 ones.add(i);7 }8 }910 int m = ones.size();11 java.util.List<Long> g = new java.util.ArrayList<>();12 for (int i = 0; i < m; i++) {13 g.add((long)ones.get(i) - i);14 }1516 long minSwaps = Long.MAX_VALUE;1718 // Sliding window over the 'g' array19 for (int i = 0; i <= m - k; i++) {20 long currentSwaps = 0;21 int medianIndex = i + k / 2;22 long medianGValue = g.get(medianIndex);2324 // Calculate cost for the current window25 for (int j = i; j < i + k; j++) {26 currentSwaps += Math.abs(g.get(j) - medianGValue);27 }28 minSwaps = Math.min(minSwaps, currentSwaps);29 }3031 return (int) minSwaps;32 }33}
Complexity
Time
O(N + m*k), where `N` is the length of `nums`, `m` is the number of ones, and `k` is the target number of consecutive ones. O(N) is for finding the indices of all ones. The main logic involves a sliding window that runs `m-k+1` times, and inside each window, we perform O(k) work to calculate the cost. In the worst case, this becomes O(N^2).
Space
O(m), where `m` is the number of ones in the input array. This is for storing the indices of the ones and the transformed `g` array. In the worst case, `m` can be up to `N`, so the space complexity is O(N).
Trade-offs
Pros
Relatively straightforward to understand and implement once the median-based cost formula is known.
It correctly models the problem by preserving the relative order of the ones.
Cons
The time complexity of O(N + m*k) can be too slow if the number of ones (m) and k are large, potentially leading to a 'Time Limit Exceeded' error on competitive programming platforms.
This approach builds upon the sliding window concept but optimizes the cost calculation for each window. Instead of re-calculating the sum of absolute differences from scratch for every window (which takes O(k) time), it uses a prefix sum array to compute this cost in O(1) time. This significantly improves the overall time complexity from quadratic to linear.
Algorithm
As in the previous approach, first generate a list of indices of all 1s, ones_indices. Let its size be m.
Create a helper array g of size m, where g[i] = ones_indices[i] - i. This transformation is key.
To optimize the cost calculation, create a prefix sum array P for g. P will have size m+1, where P[i+1] = P[i] + g[i]. This allows for O(1) calculation of the sum of any subarray of g.
The cost for a window i...i+k-1 is sum_{j=i}^{i+k-1} |g[j] - g[median_idx]|. Since g is non-decreasing, this sum can be split at the median:
1(sum of (g[median_idx] - g[j]) for j < median_idx) + (sum of (g[j] - g[median_idx]) for j > median_idx)
.
This can be rewritten using prefix sums. For a window starting at i, let median_idx = i + k/2. The cost is (cost_left) + (cost_right).
cost_left = (g[median_idx] * count_left) - (sum of g[j] from i to median_idx-1)
cost_right = (sum of g[j] from median_idx+1 to i+k-1) - (g[median_idx] * count_right)
Both sum_left and sum_right can be found in O(1) using the prefix sum array P.
Iterate a sliding window from i = 0 to m-k. In each iteration, calculate the cost for the current window in O(1) using the pre-computed prefix sums. Keep track of the minimum cost found.
Walkthrough
The core logic remains the same: we find the indices of 1s, transform them, and then use a sliding window. The innovation lies in how we calculate the cost for each window.
The cost for a window i...i+k-1 is Cost(i) = sum_{j=i}^{i+k-1} |g[j] - g[median_idx]|, where g[j] = ones_indices[j] - j and median_idx = i + k/2.
Because g is a non-decreasing array, we can split the absolute value sum into two parts: one for elements to the left of the median and one for elements to the right.
The term sum_{j=i}^{median_idx-1} g[j] is a range sum. By pre-calculating a prefix sum array for g, we can compute any such range sum in O(1) time. This allows the entire cost for a window to be calculated in O(1) time.
The algorithm first takes O(N) time to build the list of 1s indices and the prefix sum array. Then, it slides the window m-k times, with each step taking O(1) time. This results in a highly efficient linear time solution.
1class Solution {2 public int minMoves(int[] nums, int k) {3 java.util.List<Integer> ones = new java.util.ArrayList<>();4 for (int i = 0; i < nums.length; i++) {5 if (nums[i] == 1) {6 ones.add(i);7 }8 }910 int m = ones.size();11 long[] g = new long[m];12 for (int i = 0; i < m; i++) {13 g[i] = (long)ones.get(i) - i;14 }1516 long[] prefixSum = new long[m + 1];17 for (int i = 0; i < m; i++) {18 prefixSum[i + 1] = prefixSum[i] + g[i];19 }2021 long minSwaps = Long.MAX_VALUE;22 int midInWindow = k / 2;2324 for (int i = 0; i <= m - k; i++) {25 int medianIndex = i + midInWindow;26 long medianValue = g[medianIndex];2728 // Cost for elements to the left of the median29 long leftSum = prefixSum[medianIndex] - prefixSum[i];30 long costLeft = medianValue * (long)(medianIndex - i) - leftSum;3132 // Cost for elements to the right of the median33 long rightSum = prefixSum[i + k] - prefixSum[medianIndex + 1];34 long costRight = rightSum - medianValue * (long)(i + k - 1 - medianIndex);3536 long currentSwaps = costLeft + costRight;37 minSwaps = Math.min(minSwaps, currentSwaps);38 }3940 return (int) minSwaps;41 }42}
Complexity
Time
O(N), where `N` is the length of the input array `nums`. Finding the indices of `1`s takes O(N). Building the `g` array and its prefix sum array takes O(m), where `m` is the number of ones. The sliding window loop runs `m-k+1` times, and each step is O(1). The total complexity is O(N + m), which simplifies to O(N) since `m <= N`.
Space
O(m), where `m` is the number of ones. This space is used for the `ones_indices` list, the `g` array, and the `prefixSum` array. In the worst case, this is O(N).
Trade-offs
Pros
Optimal time complexity of O(N), making it very efficient for large inputs.
Scales well with the size of the input array and k.
Cons
The derivation of the cost formula and its optimization using prefix sums is more complex than the naive approach.
Requires extra space for the prefix sum array.
Solutions
Solution
1class 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 ; } }
1class 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 ; } };
1class Solution:2 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
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
