LeetCode 3936 - Minimum Swaps to Move Zeros to End

The problem gives us an integer array nums containing values between 0 and 100. We may perform an operation where we choose any two distinct indices and swap their values. Our goal is to move all zeros to the end of the array while using the minimum possible number of swaps.

leetcodeeasy

LeetCode Problem 3936

Difficulty: 🟢 Easy
Topics: —

Solution

LeetCode 3936 - Minimum Swaps to Move Zeros to End

Problem Understanding

The problem gives us an integer array nums containing values between 0 and 100. We may perform an operation where we choose any two distinct indices and swap their values. Our goal is to move all zeros to the end of the array while using the minimum possible number of swaps.

An important detail is that the relative order of the non-zero elements does not matter. The problem only requires that every zero ends up in the suffix of the array. Any arrangement satisfying this condition is acceptable.

To understand the target configuration, suppose the array contains k zeros. Then the last k positions of the array must contain all zeros, and the first n - k positions must contain only non-zero values.

The constraints are very small, with n ≤ 100, but the challenge is not about handling large inputs. Instead, it is about finding the minimum number of swaps.

Several edge cases are worth noting:

  • Arrays with no zeros already satisfy the requirement, so the answer is 0.
  • Arrays consisting entirely of zeros also require 0 swaps.
  • Some zeros may already be located in their final positions.
  • A single swap can simultaneously place a misplaced zero into the suffix and a misplaced non-zero into the prefix, so we should count swaps carefully.
  • Since any two positions can be swapped, we are not restricted to adjacent swaps.

Approaches

Brute Force Approach

A brute force solution would attempt to explore all possible swap sequences until reaching a valid configuration. Since each operation can swap any pair of positions, the branching factor is extremely large.

One could model the problem as a graph where each array state is a node and each swap produces an edge. A breadth-first search would eventually find the minimum number of swaps because BFS explores states in order of increasing number of operations.

This approach is correct because BFS guarantees the shortest path to a valid state. However, it is completely impractical. Even for small arrays, the number of possible permutations grows factorially, making the state space enormous.

Key Observation

Let:

  • z be the number of zeros in the array.
  • The last z positions be the positions where zeros must eventually reside.

Consider the first n - z positions, which should contain only non-zero values in the final configuration.

Every zero currently located in this prefix is misplaced. Likewise, every non-zero currently located in the last z positions is misplaced.

Each swap can fix exactly one misplaced zero in the prefix by exchanging it with one misplaced non-zero in the suffix.

Therefore, the minimum number of swaps is simply:

  • Count how many zeros appear in the first n - z positions.

Each such zero requires one swap, and every swap can correct exactly one of them.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Explores swap states until reaching a valid arrangement
Optimal O(n) O(1) Counts misplaced zeros in the prefix that should contain only non-zero values

Algorithm Walkthrough

Optimal Algorithm

  1. Compute the total number of zeros in the array, call it zero_count.
  2. Determine the size of the prefix that should contain only non-zero values. This size is n - zero_count.
  3. Traverse the first n - zero_count positions.
  4. For every position in this prefix, check whether the value is 0.
  5. If a zero is found, increment the answer because that zero is misplaced and must eventually be swapped into the suffix.
  6. Return the total count.

Why it works

Let the number of zeros in the array be z. The final z positions must contain all zeros. Therefore, any zero appearing before those positions is misplaced.

Every misplaced zero in the prefix corresponds to a misplaced non-zero in the suffix because the total number of zeros is fixed. A single swap between those two misplaced elements fixes both positions simultaneously.

Thus, each misplaced zero requires exactly one swap, and every swap can eliminate exactly one misplaced zero. Therefore, the number of misplaced zeros in the prefix is precisely the minimum number of swaps required.

Python Solution

class Solution:
    def minimumSwaps(self, nums: list[int]) -> int:
        zero_count = nums.count(0)
        prefix_length = len(nums) - zero_count

        swaps = 0

        for i in range(prefix_length):
            if nums[i] == 0:
                swaps += 1

        return swaps

The implementation begins by counting the total number of zeros. This immediately tells us how many positions at the end of the array must ultimately contain zeros.

The variable prefix_length represents the portion of the array that should contain only non-zero values in the final arrangement.

We then scan only this prefix. Every zero found there is misplaced and contributes exactly one required swap. The variable swaps accumulates this count.

Finally, the accumulated count is returned as the answer.

Go Solution

func minimumSwaps(nums []int) int {
    zeroCount := 0
    for _, num := range nums {
        if num == 0 {
            zeroCount++
        }
    }

    prefixLength := len(nums) - zeroCount
    swaps := 0

    for i := 0; i < prefixLength; i++ {
        if nums[i] == 0 {
            swaps++
        }
    }

    return swaps
}

The Go implementation follows exactly the same logic as the Python version. First, it counts the zeros, then computes the size of the prefix that should contain only non-zero values, and finally counts how many zeros appear inside that prefix.

There are no special concerns regarding integer overflow because the array length is at most 100. Go slices are used directly, and no additional data structures are required.

Worked Examples

Example 1

Input

nums = [0,1,0,3,12]

Total zeros:

zero_count = 2

Required prefix length:

5 - 2 = 3

Inspect the first three positions:

Index Value Misplaced Zero? Swaps
0 0 Yes 1
1 1 No 1
2 0 Yes 2

Final answer:

2

Example 2

Input

nums = [0,1,0,2]

Total zeros:

zero_count = 2

Required prefix length:

4 - 2 = 2

Inspect the first two positions:

Index Value Misplaced Zero? Swaps
0 0 Yes 1
1 1 No 1

Final answer:

1

Example 3

Input

nums = [1,2,0]

Total zeros:

zero_count = 1

Required prefix length:

3 - 1 = 2

Inspect the first two positions:

Index Value Misplaced Zero? Swaps
0 1 No 0
1 2 No 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to count zeros and one pass over the prefix
Space O(1) Only a few integer variables are used

The algorithm performs a constant number of linear scans through the array. No auxiliary data structures proportional to the input size are allocated, so the space usage remains constant.

Test Cases

sol = Solution()

assert sol.minimumSwaps([0, 1, 0, 3, 12]) == 2  # Example 1
assert sol.minimumSwaps([0, 1, 0, 2]) == 1      # Example 2
assert sol.minimumSwaps([1, 2, 0]) == 0         # Example 3

assert sol.minimumSwaps([0]) == 0               # Single zero
assert sol.minimumSwaps([5]) == 0               # Single non-zero

assert sol.minimumSwaps([0, 0, 0]) == 0         # All zeros
assert sol.minimumSwaps([1, 2, 3]) == 0         # No zeros

assert sol.minimumSwaps([0, 1]) == 1            # One swap needed
assert sol.minimumSwaps([1, 0]) == 0            # Already valid

assert sol.minimumSwaps([0, 0, 1, 2]) == 2      # Two misplaced zeros
assert sol.minimumSwaps([1, 2, 0, 0]) == 0      # Zeros already at end

assert sol.minimumSwaps([0, 1, 2, 0, 3, 4]) == 1  # One misplaced zero
assert sol.minimumSwaps([0, 1, 0, 2, 0, 3]) == 2  # Multiple misplaced zeros

assert sol.minimumSwaps([0, 0, 1, 0, 2, 3]) == 2  # Mixed placement
assert sol.minimumSwaps([4, 0, 5, 0, 6, 0]) == 1  # Only one misplaced zero

Test Summary

Test Why
[0,1,0,3,12] Official example with multiple swaps
[0,1,0,2] Official example with one swap
[1,2,0] Official example already valid
[0] Smallest array containing zero
[5] Smallest array containing non-zero
[0,0,0] All elements are zero
[1,2,3] No zeros present
[0,1] Minimal non-trivial swap case
[1,0] Zero already in correct position
[0,0,1,2] Multiple misplaced zeros
[1,2,0,0] All zeros already at end
[0,1,2,0,3,4] Exactly one misplaced zero
[0,1,0,2,0,3] Several misplaced zeros
[0,0,1,0,2,3] Mixed distribution
[4,0,5,0,6,0] Tests counting logic carefully

Edge Cases

All Elements Are Zero

Consider an array such as [0,0,0,0]. Every position already belongs to the final zero suffix because the entire array consists of zeros. A buggy implementation might incorrectly count these zeros as misplaced.

The algorithm handles this correctly because prefix_length = n - zero_count = 0, so the prefix scan examines no elements and returns 0.

No Zeros Exist

For an array like [1,2,3,4], there is nothing to move. The array already satisfies the condition.

The algorithm computes zero_count = 0, making the prefix equal to the entire array. Since there are no zeros in that prefix, the answer remains 0.

Zeros Already at the End

Consider [5,7,0,0]. Although zeros exist, they are already located in the required suffix positions.

The algorithm counts the zeros and inspects only the prefix [5,7]. Since no zeros appear there, the answer is correctly reported as 0.

Alternating Zeros and Non-Zeros

Arrays such as [0,1,0,2,0,3] can be deceptive because zeros are scattered throughout the array.

The algorithm does not simulate swaps. Instead, it directly counts misplaced zeros in the portion that should contain only non-zero values. This guarantees the minimum number of swaps without needing to construct the final arrangement explicitly.