Minimum Swaps to Move Zeros to End - Solution & Explanation

Problem Overview: Given an array of integers, move every 0 to the end using swaps and return the minimum number of swaps required. The relative order of non‑zero elements does not matter for counting swaps, but each swap represents moving a zero past a non‑zero element.

Approach 1: Brute Force Adjacent Swapping (O(n²) time, O(1) space)

The straightforward idea is to repeatedly scan the array and swap a 0 with the next element whenever it appears before a non‑zero value. This effectively “bubbles” zeros toward the end, similar to bubble sort behavior. Each pass pushes zeros one step right until all zeros reach the tail of the array. The approach is easy to reason about but inefficient because each zero may move across many elements one swap at a time. This results in worst‑case quadratic time when many zeros appear near the start.

Approach 2: Two Pointers Simulation (O(n) time, O(1) space)

Use a two‑pointer technique where one pointer scans the array while another tracks the position of the next non‑zero element. When the scan pointer sees a non‑zero value after a zero region, swap it forward and increment a swap counter. This physically performs the rearrangement while ensuring zeros gradually accumulate at the end. Each element is processed once, so the complexity drops to linear time. This pattern is closely related to problems under two pointers and array manipulation.

Approach 3: Counting Non‑Zero Elements to the Right (Optimal) (O(n) time, O(1) space)

The minimum swap count can be computed without performing actual swaps. Traverse the array from right to left and maintain a counter of how many non‑zero elements have been seen. When you encounter a zero, it must cross every non‑zero element to its right to reach the end. Each crossing represents one swap, so add the current non‑zero count to the answer. When you encounter a non‑zero value, simply increment the counter. This works because the optimal sequence moves each zero across all trailing non‑zeros exactly once. The algorithm uses a single pass and constant memory, which is typical of efficient greedy counting strategies.

Recommended for interviews: Start by explaining the brute force swap simulation to demonstrate understanding of how zeros move through the array. Then move to the counting approach. Interviewers usually expect the linear scan solution because it shows you recognized that each zero must cross every non‑zero element to its right. That observation converts a simulation problem into a simple counting problem with O(n) time and O(1) space.