Is Minimum Adjacent Swaps for K Consecutive Ones easy or hard?

The problem is categorized as Hard on LeetCode because it requires recognizing the median-distance property and combining it with sliding window and prefix sum optimization. Without this insight, brute-force approaches become too slow for large inputs.

Minimum Adjacent Swaps for K Consecutive Ones Python/Java solution

Typical implementations in Python or Java first collect the indices of all 1s, build a prefix sum array of those indices, and then slide a window of size k. For each window the cost is computed using the median index and prefix sums, achieving O(n) time complexity.

How to solve Minimum Adjacent Swaps for K Consecutive Ones in O(n)?

Store positions of every 1 in the array. Slide a window of size k across these positions and treat the middle element as the median target. Use prefix sums to compute how far elements on the left and right must move toward the median in constant time per window. This reduces the total complexity to linear time.

What is the best approach for Minimum Adjacent Swaps for K Consecutive Ones?

The most efficient approach uses sliding window over the indices of all 1s combined with prefix sums. For every window of size k, the algorithm aligns elements around the median index to minimize total movement. Prefix sums allow distance calculations in constant time, giving an overall O(n) time complexity.

Is Minimum Adjacent Swaps for K Consecutive Ones asked at Google/Amazon/Meta?

This problem type frequently appears in interviews at companies like Google, Amazon, and Meta because it tests understanding of prefix sums, sliding window optimization, and median-based greedy reasoning. Variants of grouping elements with minimum swaps are common interview questions.

What data structure is used in Minimum Adjacent Swaps for K Consecutive Ones?

The solution mainly uses arrays or lists to store indices of ones, along with a prefix sum array to compute range sums efficiently. These structures allow constant-time distance calculations while sliding the window.

What is the time complexity of Minimum Adjacent Swaps for K Consecutive Ones?

The optimal solution runs in O(n) time where n is the length of the array. First collect indices of all ones, then slide a window of size k across them while computing costs using prefix sums. Space complexity is O(n) for storing indices and prefix sums.

Description Hints 3 Solution Video 23:11

1703. Minimum Adjacent Swaps for K Consecutive Ones

Hard42.8% acceptance4 companies

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

Asked at 4 companies

Turing Amazon Microsoft

Google

Topics

Hints open one at a time

Hint 1

Choose k 1s and determine how many steps are required to move them into 1 group.

Hint 2

Maintain a sliding window of k 1s, and maintain the steps required to group them.

Hint 3

When you slide the window across, should you move the group to the right? Once you move the group to the right, it will never need to slide to the left again.

23:11

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution