Move Zeroes

easyFREEArrays & StringsMeta DSA

Given an integer array nums, move all 0's to the end while maintaining the relative order of the non-zero elements.

You must do this in-place without making a copy of the array.

The function returns nothing. The tests print nums after the call as space-separated integers, so the array you were given must hold the result.

Example

Input

0,1,0,3,12

Output

1 3 12 0 0

Reasoning

Input: nums is the list 0,1,0,3,12, so $n = 5$ . It holds $z = 2$ zeros (positions 0 and 2) and the non-zero values 1, 3, 12, in that order.
What stays fixed: the result is the same 5 values rearranged. Nothing is added or removed.
Front of the result: non-zero values keep their original relative order, so positions 0 to 2 become 1, 3, 12. This is not sorting: for the list 0, 5, 0, 2 the answer would start 5, 2.
Where each value lands: a non-zero value moves left by the number of zeros before it. 1 had one zero ahead (position 1 to 0); 3 and 12 each had two (positions 3 to 1 and 4 to 2).
Back of the result: the $z = 2$ zeros fill positions $n - z = 3$ through 4, giving 1 3 12 0 0.
Notice: a list with no zeros, such as 1, 2, 3, comes back unchanged, and a lone 0 stays put.

Constraints

1 <= len(nums) <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

Learn this in

Two Pointers & Sliding WindowDSA Study Plan

More from Meta DSA

Valid Palindrome IIeasy Dot Product of Two Sparse Vectorseasy Random Pick with Weightmedium Copy List with Random Pointermedium Remove Nth Node From Endmedium

Concept primer

Background Knowledge

The "Move Zeroes" problem involves manipulating an array in-place, meaning we cannot create a new array to store the result. This requires understanding of array operations and how to modify an array without using extra space. The problem also involves maintaining the relative order of non-zero elements, which means we need to preserve the original order of these elements while moving the zeroes to the end.

In order to solve this problem, we need to have a good grasp of array indexing and how to iterate through an array. We should also be familiar with conditional statements and looping constructs, such as for loops or while loops, to control the flow of our program. Additionally, understanding the concept of two pointers can be helpful in solving this type of problem, as it allows us to keep track of multiple positions in the array simultaneously.

The "Move Zeroes" problem is a classic example of an array manipulation problem, which is a common topic in coding interviews. Solving this problem requires a combination of logical thinking, problem-solving skills, and attention to detail. By understanding the underlying concepts and developing a clear approach, we can write an efficient and effective solution to this problem.

Algorithm/Approach

The general approach to solving the "Move Zeroes" problem involves using a two-pointer technique. This technique allows us to keep track of two positions in the array: one for the next non-zero element and one for the current element being processed. By iterating through the array and swapping elements as needed, we can maintain the relative order of the non-zero elements while moving the zeroes to the end.

Step-by-Step Strategy

To solve the "Move Zeroes" problem, we can follow these steps:

Initialize two pointers, one at the beginning of the array and one at the beginning of the array.
Iterate through the array, checking each element to see if it is zero or non-zero.
If the current element is non-zero, swap it with the element at the next non-zero position.
Move the next non-zero position pointer forward.
Repeat the process until the end of the array is reached.

Common Pitfalls

Some common pitfalls to watch out for when implementing the solution include:

Forgetting to check for the end of the array, which can cause an index out of bounds error.
Swapping elements incorrectly, which can result in the loss of data or incorrect ordering.
Not handling the case where the input array is empty or contains only zeroes.

Time & Space Complexity

The expected time complexity for the "Move Zeroes" problem is $O(n)$ , where $n$ is the length of the input array. This is because we need to iterate through the array once to move all the zeroes to the end. The expected space complexity is $O(1)$ , which means the space required does not change with the size of the input array, making it very efficient.

solution.py

Python 3.13

Test results