3936. Minimum Swaps to Move Zeros to End

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

In one operation, you can choose any two distinct indices i and j and swap nums[i] and nums[j].

Your task is to move all the 0s in the array to the end. After performing the operations, every 0 should appear after all the non-zero elements, while the relative order of the elements does not need to be preserved.

Return an integer denoting the minimum number of operations required to move all 0s to the end of the array.

For example, if nums = [1, 0, 2, 0, 3], the zeros are located at indices 1 and 3. By swapping these zeros with non-zero elements that appear after them, you can gather all the non-zero numbers at the front and push the zeros to the end. The answer is the smallest count of such swaps needed.

The key observation is that a single swap can fix two misplaced elements at once: a 0 that sits before a non-zero element can be swapped with that non-zero element, correcting both positions simultaneously. Therefore, the minimum number of operations equals the number of 0s that have at least one non-zero element appearing after them in the array.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Two pointers?

This problem maps to Two pointers through a short path in the full flowchart.

Two pointers process the array without extra space.

Open in Flowchart

Intuition

The goal is to push all 0s to the end of the array using the fewest swaps. Let's think about what a single swap can accomplish.

The most efficient swap is one that fixes two problems at the same time: we take a 0 that is currently sitting in the "front" part of the array (where non-zero numbers should be) and swap it with a non-zero number that is sitting in the "back" part of the array (where zeros should be). After this one swap, both elements land in their correct regions.

This naturally suggests a two pointers strategy. We place one pointer i at the beginning of the array and another pointer j at the end. The pointer i scans rightward looking for a 0 (a value that is out of place at the front), and the pointer j scans leftward looking for a non-zero number (a value that is out of place at the back).

Whenever i finds a misplaced 0 and j finds a misplaced non-zero number, and as long as i < j, these two are a perfect pair to swap. We count this swap, then move both pointers inward and continue searching.

We keep repeating this until the two pointers meet or cross (i >= j), which means every 0 is now positioned after all non-zero numbers. The total number of swaps we counted along the way is the minimum required, because each swap we made resolved two out-of-place elements at once — there is no way to do better than fixing two issues per operation.

Pattern Learn more about Two Pointers patterns.

Solution Approach

Solution 1: Two Pointers

We use two pointers i and j, where i points to the beginning of the array and j points to the end. We also keep a counter ans initialized to 0 to record the number of swaps, and let n be the length of nums.

The main loop runs while i < j:

Move i to find a misplaced 0. We advance i to the right with the condition while i < n and nums[i] != 0: i += 1. This skips over all the non-zero numbers at the front (which are already in their correct region) and stops when i lands on a 0.
Move j to find a misplaced non-zero number. We move j to the left with the condition while j and nums[j] == 0: j -= 1. This skips over all the trailing zeros (which are already correctly placed at the back) and stops when j lands on a non-zero value.
Check whether a valid pair exists. If after the two scans we have i >= j, it means the pointers have crossed or met, so there is no remaining 0 in the front region that has a non-zero number after it. We break out of the loop.
Count the swap and shrink the window. Otherwise, i is pointing to a 0 and j is pointing to a non-zero number with i < j. Conceptually swapping them fixes both positions, so we increment ans += 1. We then move both pointers inward with i += 1 and j -= 1 and continue searching.

When the loop ends, ans holds the minimum number of operations, which we return.

Notice that the code does not actually perform the swaps on the array — it only counts how many such swaps are needed. This is enough because we only care about the count of operations, not the final arrangement.

Time Complexity: O(n), where n is the length of nums. Each pointer traverses the array at most once, so the total work is linear.
Space Complexity: O(1), since we only use a constant number of extra variables (ans, i, j, and n).

Example Walkthrough

Let's trace through the Two Pointers approach with the array nums = [1, 0, 2, 0, 3], where n = 5.

We initialize i = 0 (start), j = 4 (end), and ans = 0.

Iteration 1 (i = 0, j = 4, check i < j → 0 < 4 ✓):

Move i to find a misplaced 0. At i = 0, nums[0] = 1 (non-zero), so we advance: i becomes 1. At i = 1, nums[1] = 0, so we stop. Now i = 1.
Move j to find a misplaced non-zero number. At j = 4, nums[4] = 3 (non-zero), so we stop immediately. Now j = 4.
Check the pair. Is i >= j? 1 >= 4 is false, so we have a valid pair: nums[1] = 0 and nums[4] = 3 with i < j.
Count the swap. Conceptually swapping fixes both: the 0 moves to the back, the 3 moves to the front. We set ans = 1, then shrink: i becomes 2, j becomes 3.

State after iteration 1: i = 2, j = 3, ans = 1. (Imagined array: [1, 3, 2, 0, 0].)

Iteration 2 (i = 2, j = 3, check i < j → 2 < 3 ✓):

Move i. At i = 2, nums[2] = 2 (non-zero), advance: i becomes 3. At i = 3, nums[3] = 0, stop. Now i = 3.
Move j. At j = 3, nums[3] = 0 (a zero), so we move left: j becomes 2. At j = 2, nums[2] = 2 (non-zero), stop. Now j = 2.
Check the pair. Is i >= j? 3 >= 2 is true — the pointers have crossed. We break.

The loop ends with ans = 1.

Result: The minimum number of operations is 1. This matches intuition: a single swap of the 0 at index 1 with the 3 at index 4 corrects two misplaced elements at once, leaving all zeros at the end.

Solution Implementation

1class Solution:
2    def minimumSwaps(self, nums: list[int]) -> int:
3        # Count of swaps performed
4        swap_count = 0
5        n = len(nums)
6
7        # Two pointers: 'left' scans forward, 'right' scans backward
8        left, right = 0, n - 1
9
10        while left < right:
11            # Advance 'left' until it points to a zero
12            # (skip over all non-zero values from the front)
13            while left < n and nums[left] != 0:
14                left += 1
15
16            # Move 'right' backward until it points to a non-zero
17            # (skip over all zero values from the back)
18            while right and nums[right] == 0:
19                right -= 1
20
21            # If the pointers have crossed, no more valid pairs remain
22            if left >= right:
23                break
24
25            # A misplaced pair is found: count one swap
26            swap_count += 1
27
28            # Move both pointers inward to continue scanning
29            left += 1
30            right -= 1
31
32        return swap_count
33

1class Solution {
2    public int minimumSwaps(int[] nums) {
3        int swapCount = 0;
4        int length = nums.length;
5
6        // Use two pointers converging from both ends.
7        // left moves rightward, right moves leftward.
8        for (int left = 0, right = length - 1; left < right; ++left, --right) {
9            // Advance left until it points to a 0 (a value that belongs on the left side).
10            while (left < length && nums[left] != 0) {
11                ++left;
12            }
13
14            // Retreat right until it points to a non-zero (a value that belongs on the right side).
15            while (right > 0 && nums[right] == 0) {
16                --right;
17            }
18
19            // If the pointers have crossed, no more mismatched pairs remain.
20            if (left >= right) {
21                break;
22            }
23
24            // A mismatched pair was found; one swap is needed to fix it.
25            ++swapCount;
26        }
27
28        return swapCount;
29    }
30}
31

1class Solution {
2public:
3    int minimumSwaps(vector<int>& nums) {
4        int ans = 0;
5        int n = nums.size();
6
7        // Two pointers: 'left' scans from the start, 'right' scans from the end.
8        // We advance them together each outer iteration, counting a swap whenever
9        // the element that needs to move has not yet reached its target boundary.
10        for (int left = 0, right = n - 1; left < right; ++left, --right) {
11            // Move 'left' forward past every element that is already a 0
12            // (i.e., already in place at the front region).
13            while (left < n && nums[left] != 0) {
14                ++left;
15            }
16
17            // Move 'right' backward past every element that is a 0
18            // (a 0 at the back must be relocated, so skip non-target ones).
19            while (right > 0 && nums[right] == 0) {
20                --right;
21            }
22
23            // If the pointers crossed, no further swaps are needed.
24            if (left >= right) {
25                break;
26            }
27
28            // Otherwise this pair requires one swap to reach their boundaries.
29            ++ans;
30        }
31
32        return ans;
33    }
34};
35

1/**
2 * Calculates the minimum number of swaps required to segregate
3 * the array's elements (treating it as a binary 0/1 array), so that
4 * all 1s end up on the left side and all 0s on the right side.
5 *
6 * Strategy (two-pointer):
7 *   - Advance the left pointer past every value that is already in place (non-zero).
8 *   - Advance the right pointer past every value that is already in place (zero).
9 *   - Whenever a misplaced 0 on the left sits before a misplaced 1 on the right,
10 *     one swap resolves both, so count it and move both pointers inward.
11 *
12 * @param nums - The input array of numbers (interpreted as binary values).
13 * @returns The minimum number of swaps needed.
14 */
15function minimumSwaps(nums: number[]): number {
16    // Total number of swaps performed.
17    let answer = 0;
18    const n = nums.length;
19
20    // Left pointer scans forward; right pointer scans backward.
21    let left = 0;
22    let right = n - 1;
23
24    while (left < right) {
25        // Move the left pointer to the first misplaced element (a 0 that should be on the right).
26        while (left < n && nums[left] !== 0) {
27            ++left;
28        }
29
30        // Move the right pointer to the first misplaced element (a 1 that should be on the left).
31        while (right > 0 && nums[right] === 0) {
32            --right;
33        }
34
35        // If the pointers have crossed, no more swaps are needed.
36        if (left >= right) {
37            break;
38        }
39
40        // A misplaced 0 (left) and a misplaced 1 (right) can be fixed with one swap.
41        ++answer;
42        ++left;
43        --right;
44    }
45
46    return answer;
47}
48

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

In the code, two pointers i and j start from the two ends of the array and move toward each other. The pointer i only ever increases (it advances when nums[i] != 0 in the inner loop, and once more after a swap is counted), while the pointer j only ever decreases. Although there is an outer while i < j loop containing two inner while loops, no element is visited more than once across all iterations because i and j never backtrack. Therefore, the total number of operations is bounded by the combined traversal of i from the front and j from the back, giving O(n).

Space Complexity: O(1).

The algorithm only uses a constant number of extra variables (ans, n, i, and j) regardless of the input size. No additional data structures that scale with the input are allocated, so the extra space used is constant.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Problem and Actually Sorting/Swapping the Array

A frequent mistake is interpreting the task as "rearrange the array so all zeros are at the end" and then trying to count the number of actual swaps a sorting-style algorithm would perform. This often leads to overcomplicated solutions where developers mutate nums in place and tally every individual move.

Why it's wrong: The problem only asks for the count of minimum operations, not the final arrangement. Because a single swap can fix two misplaced elements simultaneously (a leading 0 and a trailing non-zero), the answer is simply the number of zeros that have at least one non-zero element after them. There is no need to physically move any element.

Solution: Recognize that the answer is purely a counting problem. You can even solve it with a simpler one-pass count:

class Solution:
    def minimumSwaps(self, nums: list[int]) -> int:
        # The number of non-zero elements determines the "front region".
        # Count how many zeros land inside that front region.
        non_zero = sum(1 for x in nums if x != 0)
        # Zeros located in the first `non_zero` positions are misplaced.
        return sum(1 for x in nums[:non_zero] if x == 0)

Each misplaced zero in the front region must be swapped with exactly one non-zero element from the back region, so this count equals the minimum swaps.

Pitfall 2: Incorrect Loop Boundary Causing Index Errors or Infinite Loops

When implementing the two-pointer scan, it is easy to write the inner conditions incorrectly. Two common variants cause bugs:

Using while left < n but forgetting the analogous lower bound on right, or writing while right >= 0 and nums[right] == 0 instead of while right and .... Both can lead to right going out of range or the outer left < right check behaving unexpectedly.
Forgetting the outer if left >= right: break guard. Without it, after the inner scans the pointers may have crossed, yet the code still increments swap_count and shrinks the window — overcounting swaps.

Why it's wrong: Once the pointers cross, any "pair" found is invalid because the 0 at left actually sits after the non-zero at right, meaning it is already in a legal position relative to that element. Counting it inflates the result.

Solution: Always re-check left < right (or left >= right) after both inner scans complete and before counting a swap:

while left < right:
    while left < n and nums[left] != 0:
        left += 1
    while right and nums[right] == 0:
        right -= 1
    if left >= right:   # critical guard — verify pointers haven't crossed
        break
    swap_count += 1
    left += 1
    right -= 1

Pitfall 3: Failing to Advance Pointers After a Counted Swap

Some implementations correctly find a misplaced pair and increment the counter but forget to move both pointers inward (left += 1 and right -= 1). Advancing only one pointer—or neither—causes the same position to be re-examined, leading to an infinite loop or a wrong count.

Why it's wrong: After conceptually swapping the 0 at left with the non-zero at right, both positions are now correct. They must be excluded from further scanning by shrinking the window from both ends.

Solution: Ensure both pointers move inward immediately after counting a swap, as shown in the corrected snippet above. This guarantees the window strictly shrinks each iteration, ensuring termination in O(n) time.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Is the following code DFS or BFS?

void search(Node root) {
  if (!root) return;
  visit(root);
  root.visited = true;
  for (Node node in root.adjacent) {
    if (!node.visited) {
      search(node);
    }
  }
}

Depth First Search

Breadth First Search

I don't know