283. Move Zeroes - Detailed Explanation

Problem statement

Given an integer array nums, move all 0's to the end of the array while maintaining the relative order of the non-zero elements. Importantly, this operation must be done in-place, meaning you should not create a new array to accomplish it.

Example 1:
Input: nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Explanation: The zeroes in the input have been moved to the end, and the order of the non-zero elements [1,3,12] is preserved.
Example 2:
Input: nums = [0]
Output: [0]
Explanation: The array contains only one element (which is zero), so it remains unchanged.

Constraints:

1 <= nums.length <= 10^4 (the array can have up to 10,000 elements)
-2^31 <= nums[i] <= 2^31 - 1 (array elements can be any integer, including negative, zero, or positive)

The problem guarantees a mutable array, so you can rewrite it in place. The goal is minimal time complexity, ideally linear time, with no extra array space.

This question is an instance of the two pointers pattern. Two pointers means you traverse the array with two indices that advance at different rates, and each index carries a distinct meaning. Here one index reads and the other writes. The same technique solves a long list of array questions, which is why it appears in every survey of the recurring coding interview patterns. Design Gurus teaches this exact problem in the Move Zeroes lesson.

Hints

Think simple first: A direct way to solve this is to use an additional array or list. You could collect all the non-zero elements first, then append the appropriate number of zeroes. The problem expects an in-place solution with no extra array, so treat this as a thought exercise or a brute-force idea rather than the final answer.
Counting or two-pass idea: You might consider counting the zeroes. Count how many 0's the array holds, then fill the array with the non-zero elements followed by that many zeroes. This meets the requirements when you implement it carefully, and it beats moving one element at a time.
Two-pointer technique: A very efficient approach uses the two-pointer pattern. One pointer iterates through the array. The other pointer marks the position where the next non-zero element should be placed. You can then rearrange elements in a single pass with no extra space. Think about how you would move non-zero values forward and what happens to the zeroes they displace.

Sketch one of these approaches on a small example array before you read the solution. The two-pointer hint is the key to an optimal solution.

Approach 1: brute force (naive method)

Idea: One brute-force approach repeatedly relocates each zero as you encounter it. For each element in the array, if the value is zero, you can remove that zero and then append a zero at the end of the array. The zero has then reached the end. Do this for every zero in the array and all of them collect at the back.

Explanation: You iterate through the array from start to end. Whenever you find a 0:
1. Remove that 0 from its current position, which shifts all elements to the right one step left.
2. Append a 0 at the end of the array.
3. Do not advance the index in this step. After the removal, the next element now occupies the current index, and the following iteration still has to check it. Stop the scan once the index reaches the original length minus the number of zeroes you have already relocated, because everything past that point is a zero you placed yourself. Without that bound the scan would relocate a trailing zero forever.

When this process ends, all original zeroes have reached the end in their original order. Order among the zeroes does not actually matter. All non-zeroes have shifted left, and they preserve their original order relative to each other.

Example (brute force): Suppose nums = [0, 5, 0, 7].
- Start at index 0: nums[0] is 0, remove it and append a 0. The array becomes [5, 0, 7, 0]. Index 0 now holds the value 5, which came from index 1.
- Stay at index 0 and do not increment, since a new element landed there. Now nums[0] is 5, a non-zero, so move to the next index.
- Index 1: nums[1] is 0, remove it and append a 0. The array becomes [5, 7, 0, 0].
- Stay at index 1: now nums[1] is 7, which is non-zero. Continue.
- Index 2 equals the original length of 4 minus the 2 zeroes already relocated, so the scan stops here. The array is [5, 7, 0, 0], with both zeroes at the end and 5 still before 7.

Python code

Python3

. . . .

This brute-force approach does the job, but it is not very efficient. Removing an element from the middle of an array or list is costly, because it shifts all subsequent elements left by one. In the worst case, such as an array full of zeroes, you remove and append once per element. Each removal can cost up to O(n) time because of the shifting. Doing that n times leads to O(n²) time complexity. The space complexity is O(1), in place, since you only modify the array itself.

Complexity analysis (brute force): For an array of length n, the time complexity is O(n²) in the worst case. That case arises when the array holds many zeroes and each zero causes a shift of a large portion of the array. The space complexity is O(1), because every operation happens in the original array with no extra storage. Calls like pop and append modify the array in place.

This approach is easy to understand, but large inputs need a more efficient solution. Recall that n can reach 10,000. Next comes an optimized approach that handles the task in linear time.

Approach 2: optimized approach (two-pointer technique)

Idea: The optimal solution applies the two-pointer technique and rearranges the array in one linear pass. One pointer, often called k or lastNonZeroIndex, marks the position where the next non-zero element should be placed. A second pointer, i, scans through the array looking for non-zero elements. As you find non-zero values, you swap them toward the front, and the displaced zeroes accumulate at the end of the array.

Explanation:
Initialize an insert position pointer k = 0. This k tracks the index where the next non-zero element goes. Then iterate i through each index of the array:
1. If nums[i] is non-zero, that value should appear as early in the array as possible, with relative order preserved. So swap nums[i] with nums[k]. This moves the non-zero value into position k, and whatever sat at nums[k], which might be 0, moves to position i.
2. After swapping, increment k by 1 to point at the next position for the following non-zero value. In other words, k always points at the first index in the front part of the array that is currently occupied by a zero.
3. If nums[i] is 0, do nothing and just continue. k will not change, so it still points at this index, which is a candidate for the next non-zero swap.

By the end of the pass, all non-zero elements have moved to the front [0...k-1] in their original order, and k holds the index of the first 0. All remaining positions from k to the end of the array hold 0. This satisfies the problem requirements, and one pass does all of it.

Why it works: This method swaps each non-zero element at most once, and it examines each element exactly once. It maintains the order of the non-zero elements, because a swap only ever exchanges a non-zero with a zero, and zeroes have no relative order to maintain among themselves. The pointer k advances only when a non-zero element is placed, which guarantees that positions before k are finalized as non-zero and in the correct order.
Example (two pointers): Consider nums = [0, 1, 0, 3, 12]. We trace the algorithm step by step:
- Start: nums = [0, 1, 0, 3, 12], k = 0, the position for the next non-zero value.
- i = 0: nums[0] is 0, so do nothing. k remains 0 and the array is unchanged.
- i = 1: nums[1] is 1, a non-zero. Swap nums[1] with nums[k], which is nums[0]. After the swap, the array becomes [1, 0, 0, 3, 12]. Increment k to 1.
- i = 2: nums[2] is 0, so do nothing. k is still 1 and the array is still [1, 0, 0, 3, 12].
- i = 3: nums[3] is 3, a non-zero. Swap nums[3] with nums[k], which is nums[1]. The array becomes [1, 3, 0, 0, 12]. Increment k to 2.
- i = 4: nums[4] is 12, a non-zero. Swap nums[4] with nums[k], which is nums[2]. The array becomes [1, 3, 12, 0, 0]. Increment k to 3.
- End of loop. All non-zeroes [1,3,12] now sit at the front in order, and all zeroes sit at the end.

We can illustrate this process in a table:

Iteration (i)	`k` (next non-zero index)	Current `nums[i]`	Action	Array state after iteration
i = 0	k = 0	0	0 found, do nothing	[0, 1, 0, 3, 12]
i = 1	k = 0	1	non-zero found, swap with index 0 (swap 1 and 0)	[1, 0, 0, 3, 12]
i = 2	k = 1	0	0 found, do nothing	[1, 0, 0, 3, 12]
i = 3	k = 1	3	non-zero found, swap with index 1 (swap 3 and 0)	[1, 3, 0, 0, 12]
i = 4	k = 2	12	non-zero found, swap with index 2 (swap 12 and 0)	[1, 3, 12, 0, 0]
End	k = 3	none	none	[1, 3, 12, 0, 0] (all zeroes moved to end)

After this single pass, the array is [1,3,12,0,0], which is exactly the expected result. Notice that k advanced only when the scan met a non-zero value. At the end k = 3, which is the index of the first trailing zero.

Two-pointer implementation in Python

Python3

. . . .

This code modifies the input list nums so that all zeroes end up at the end, and it uses a single loop through the array. Each element is visited once, and each non-zero value is swapped at most one time. No extra arrays or data structures appear.

Complexity analysis (optimized): This two-pointer approach makes a single pass through the array, so the time complexity is O(n), linear in the number of elements. Each element is processed once, and swaps are constant-time operations. The space complexity is O(1), since the swaps happen in place and the code keeps only a couple of integer variables, whatever the input size. This meets the optimal requirements of the problem: linear time and an in-place transformation.

Note: This approach has slight variations. Instead of swapping, you can shift all non-zero values forward by overwriting positions, then fill the remainder of the array with zeroes. That variant also takes O(n) time and O(1) space. The swapping method stays here because it is more concise.

Step-by-step walkthrough of the optimal solution

Let's walk through the optimal two-pointer approach with a clear example and break down each step in detail. A table shows how the array changes over the iterations.

Example: nums = [0, 2, 0, 4, 5], an array with some zeroes interspersed among non-zero numbers.

Initial state:
nums = [0, 2, 0, 4, 5]
k = 0 (we use k to mark the position of the next non-zero insertion)

Now we iterate through the array with index i:

Step (i)	`k` (next non-zero index)	`nums[i]` value	Operation & Outcome	Array state after step
i = 0	0	0	`nums[i]` is 0, so no swap. (`k` remains 0)	[0, 2, 0, 4, 5]
i = 1	0	2	`nums[i]` is non-zero. Swap `nums[1]` with `nums[0]`.	After swap, array = [2, 0, 0, 4, 5]; increment `k` to 1.
i = 2	1	0	`nums[i]` is 0, so no swap. (`k` remains 1)	[2, 0, 0, 4, 5]
i = 3	1	4	`nums[i]` is non-zero. Swap `nums[3]` with `nums[1]`.	After swap, array = [2, 4, 0, 0, 5]; increment `k` to 2.
i = 4	2	5	`nums[i]` is non-zero. Swap `nums[4]` with `nums[2]`.	After swap, array = [2, 4, 5, 0, 0]; increment `k` to 3.

End of loop: We have nums = [2, 4, 5, 0, 0]. All non-zero elements, 2, 4, 5, have moved to the front in their original order. All zeroes now sit at the end. The pointer k = 3 reports that the first 3 positions hold non-zero numbers, and that index 3 onward holds zeroes.

In the above walkthrough, each step corresponds to one iteration of the loop:

When we encounter a 0, nothing happens except that i moves on.
When we encounter a non-zero value, we swap it with the element at index k, the earliest index where a 0 resides and is ready to be replaced. This pushes the non-zero value into the front part of the array. We then advance k.

This step-by-step process confirms how the two-pointer approach moves all zeroes to the end. No element is lost and no non-zero values trade places. The loop effectively partitions the array into two parts in one pass, non-zeroes at the front and zeroes at the back. For more practice on this pattern, Container With Most Water runs two pointers inward from both ends, and Is Subsequence runs them across two different strings.

Implementation in Python

Python3

. . . .

In the code above, the move_zeroes function implements the two-pointer approach. We then test it with the example array. The result shows the zeroes moved to the end as expected. The function operates in place, so the original list arr is modified and printed to verify the outcome.

Implementation in Java

Java

. . . .

Here, the moveZeroes method uses the same two-pointer strategy. We print the array before and after calling moveZeroes to verify that the zeroes have moved correctly. Arrays.toString renders the array in a readable format. Just like the Python version, this Java implementation runs in place and in linear time.

Complexity analysis

Let's summarize the time and space complexity for each approach discussed:

Brute force approach: Time complexity is O(n²) in the worst case. This quadratic time arises because each zero element potentially shifts a large portion of the array. Space complexity is O(1), in place. This approach is acceptable for small arrays but becomes inefficient as n grows large.
Optimized two-pointer approach: Time complexity is O(n). We make one pass through the array of length n, doing constant work for each element. Space complexity is O(1), since we only use a few extra variables. This approach stays efficient at the maximum array length of 10,000 or more, and it is the recommended solution.

For example, take n = 10^4, the upper constraint. The optimized approach performs roughly 10,000 operations. The brute force could perform on the order of 50 million operations in the worst distribution of zeroes. That is a significant difference.

Common mistakes

Beginners run into several pitfalls with this problem. Here are a few common mistakes and misconceptions:

Modifying the array during iteration incorrectly: If you remove or insert elements inside a standard for loop, as the brute-force approach does, you might skip elements or read past the end. Code such as for i in range(len(nums)): if nums[i] == 0: nums.pop(i) shortens the list while the loop runs, so you miss the next element or hit an index error. When removing elements in a loop, use a while loop, iterate backwards, or better, apply the two-pointer method to avoid this complexity.
Not preserving the order of non-zero elements: A solution that simply sorts the array, or partitions without care, can clump the numbers together without preserving their original order. You might think to sort the array so that all 0's come last. Sorting would destroy the relative order of the non-zero elements, and it also costs more than O(n) in most cases. The problem specifically requires the original order of the non-zero elements, so any approach that drops it is incorrect.
Using extra space when not allowed: It is easy to solve the problem by creating a new array, for example filtering out the zeroes and then adding them at the end. The problem explicitly asks for an in-place solution. A common mistake is to return a new array or to keep an additional list of results. In an interview or on LeetCode, that would not meet the requirements. The LeetCode function returns void, so a new array never replaces the original. Make sure your final solution operates on the input array itself.
Off-by-one errors in shifting or filling: When implementing manually, without high-level operations, people sometimes get the indices wrong while shifting elements or filling in zeroes. They forget to update the effective length of the array during a brute-force removal, or they place the first zero in the wrong position. Tracing a simple example, as we did in the walkthrough, or writing tests for edge cases helps catch these issues.
Inefficient swapping or unnecessary operations: In the two-pointer approach, some implementations swap even when i and k are the same index, which is harmless but unnecessary. The output stays correct, so this is not exactly a bug, only an inefficiency. Checking if (i != k) before the swap removes the pointless self-swaps. It does not change the big-O complexity, so treat it as a micro-optimization.

Understanding the logic behind the two-pointer method and handling the indices carefully will help you avoid these mistakes. Always test your solution on a variety of inputs, including the edge cases below.

Edge cases

When solving Move Zeroes, check the following edge cases against your solution:

All elements are zero, for example nums = [0, 0, 0]. The output should be the same as the input, all zeroes. The algorithm should not crash or misplace elements in this scenario. The two-pointer method simply leaves every element as 0, with k never moving from 0.
No zeroes in the array, for example nums = [1, 2, 3]. The output should be identical to the input, since there is no zero to move. An in-place algorithm should ideally recognize that no change is needed. In the two-pointer approach, k increments every time and ends up equal to n, and the array remains unchanged.
An array of length 1, for example nums = [0] or nums = [5]. Single-element arrays should remain the same after the operation, either a zero that is already at the end or a lone non-zero that is trivially at the front. Confirm that your loops handle length 1 without issues, which they generally will.
Zeroes already at the end, for example nums = [4, 1, 0, 0]. The output should be the same as the input in this case, since the zeroes already sit in the correct position. A correct algorithm will not disturb the order. The two-pointer approach, for example, swaps the non-zeroes with themselves here and leaves the array as it is.
Alternating zero and non-zero, for example nums = [0, 7, 0, 7, 0, 7]. This is a pattern where every non-zero value is separated by zeroes. After moving the zeroes, all the 7's should come first and all the 0's last: [7, 7, 7, 0, 0, 0]. This input tests that your method truly gathers all non-zeroes at the front and all zeroes at the back without mixing the sequence.
Negative numbers and other values, for example nums = [0, -1, 0, -2, 0, -3]. The actual values, positive or negative, do not matter to the algorithm, which should keep any non-zero. Still, make sure your code does not inadvertently treat negative or other values as special. The expected output is [-1, -2, -3, 0, 0, 0] in this example.

By testing these edge cases, you can be confident that your solution works for all valid inputs and respects the problem constraints.

Alternative variations

Move Zeroes is a specific instance of a more general class of problems where you partition or rearrange elements based on some condition. Some variations and related scenarios include the following.

Moving a different target value: Instead of zero, the task might move all occurrences of a particular value, say all -1 or all "#", to the end or the beginning. The approach would be very similar. You would use a condition such as if nums[i] != target, or the opposite, to decide when to swap. The two-pointer technique generalizes to any question that separates one group of values from the rest.
Moving zeroes to the front: A twist on the problem could send all zeroes to the start of the array, while the non-zero values keep their order. This would involve a similar approach, perhaps scanning from the end or running two pointers from opposite ends. You could also keep it to one pass by iterating from the end and moving non-zeroes toward the end, or by using a backwards pointer for zero placement.
Stable partitioning by other properties: Examples include moving all even numbers to the front and the odds to the back, or moving all negative numbers to the front. If the relative order needs to be preserved, the approach is again analogous, either two pointers or a two-pass gather-and-fill method. If relative order does not need to be preserved, more efficient partitioning methods exist, such as the Lomuto partition scheme from quicksort.
A two-pass approach with counting: A simple variant counts the number of zeroes, then fills the array with all the non-zero elements in their original order, and finally fills the remaining slots with zeroes. This is effectively what the non-swapping variant of the two-pointer method does, but conceptually it frames the task differently. It is straightforward and involves two passes through the array, still O(n) time. It is worth noting as an alternative, especially where simplicity matters more than the absolute optimal number of operations.
Using built-in functions in high-level languages: In Python, for instance, you could write nonzeros = [x for x in nums if x != 0] and then nums[:] = nonzeros + [0]*zero_count. This achieves the result very concisely, and it violates the in-place constraint, because the comprehension allocates new lists and uses extra space. It is still a variation you might think of. Similarly, you could sort with a custom key that treats 0 as greater than any non-zero, but that preserves relative order only when the sort is stable and the key is chosen carefully.

In interviews and in practice, solve the problem under the intended constraints, in place and in O(n). Knowing these variations and alternative approaches still improves your understanding and your adaptability on other problems.

Move Zeroes is conceptually related to several other problems that involve array manipulation and two-pointer techniques. If you want to practice further, here are some related problems:

Remove Element (LeetCode 27): Remove all occurrences of a given value from an array in place and return the new length. The structure is very similar, essentially moving all copies of one value out. You do not need to maintain the order of the removed elements, but you do maintain the order of the rest. The two-pointer approach is commonly used here as well.
Remove Duplicates from Sorted Array (LeetCode 26): Another in-place array operation using two pointers. You need to remove duplicate values from a sorted array so that each element appears only once. The context is different, but the idea of using one pointer to build the result in place is analogous.
Sort Array by Parity (LeetCode 905): Move all even numbers to the front of the array and the odd numbers to the back. The order within each group does not necessarily need to be preserved here unless the question states it. This can be solved with an approach similar to Move Zeroes, treating even as non-zero and odd as zero in terms of the partitioning logic.
Duplicate Zeros (LeetCode 1089): Another array manipulation problem, where you duplicate each occurrence of zero in the array and shift the remaining elements to the right. The outcome is different, and it also involves careful in-place operations and element shifting. Mastering Move Zeroes helps you understand how to approach this one, and the reverse is also true.
Sort Colors (LeetCode 75): Also known as the Dutch National Flag problem, where you sort an array of 0s, 1s, and 2s in place, grouping all the 0s, then the 1s, then the 2s. This is a classic problem that uses a two-pointer, or three-pointer, technique to partition the array. It is a bit more complex, but the idea of moving certain values to the end and others to the beginning in one pass is related.