Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]
Example 2:
Input: nums = [0] Output: [0]
Constraints:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1The goal of #283 Move Zeroes is to rearrange an array so that all 0 values are moved to the end while keeping the relative order of non-zero elements unchanged. Since the operation must be performed in-place, the challenge is to avoid using extra space while maintaining order.
A common and efficient strategy uses the two-pointer technique. One pointer tracks the position where the next non-zero element should be placed, while the other scans the array. Whenever a non-zero value is encountered, it is moved or swapped into the correct position and the placement pointer advances. This effectively compacts all non-zero elements at the beginning of the array while pushing zeros toward the end.
This approach ensures that every element is processed only once, resulting in O(n) time complexity with O(1) extra space. The key idea is to maintain the order of non-zero elements while minimizing unnecessary swaps.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (In-place shifting/swapping) | O(n) | O(1) |
| Extra Array (store non-zero elements) | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
<b>In-place</b> means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.
A <b>two-pointer</b> approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.
This approach uses two pointers: one to track the position for the next non-zero element and the other to iterate through the array. We move all non-zero elements to the beginning of the array using these two pointers and fill the remaining positions with zeroes.
Time Complexity: O(n), where n is the length of the array. We make a single pass through the array.
Space Complexity: O(1), as we perform the operation in place.
1def moveZeroes(nums):
2 lastNonZeroFoundAt = 0
3 for i in range(len(nums)):
4 if nums[i] != In Python, we iteratively move non-zero elements to the front using lastNonZeroFoundAt as a pointer and then fill the rest of the array with zeroes.
This method uses a two-pointer technique where we place one pointer at the beginning of the array and the other to iterate through the array. Whenever we encounter a non-zero element, we swap it with the first pointer's position, allowing us to effectively move zeroes to the end by swapping.
Time Complexity: O(n), single iteration with swaps.
Space Complexity: O(1), in-place swaps.
1varWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Move Zeroes is a common easy-level interview question often asked in coding interviews at large tech companies. It tests understanding of arrays, in-place operations, and the two-pointer pattern.
The optimal approach uses the two-pointer technique. One pointer scans the array while another tracks where the next non-zero element should be placed. This allows all non-zero elements to be compacted at the front while zeros naturally move to the end in O(n) time.
An array with the two-pointer technique is sufficient for this problem. Since the task requires in-place modification and maintaining order, no additional data structures are necessary for the optimal solution.
The two-pointer technique helps track both the scanning position and the correct placement position for non-zero elements. This ensures the array is rearranged efficiently without extra space and with minimal operations.
The JavaScript solution uses array destructuring to swap elements. As i iterates the list, non-zero elements take the place at index j which keeps track of the position for the next non-zero swap.