Move Zeroes - Solution & Explanation
Problem Statement
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 - 1
Follow up: Could you minimize the total number of operations done?
Approach Overview
Problem Overview: You are given an integer array nums. The task is to move all 0 values to the end of the array while keeping the relative order of non-zero elements unchanged. The operation must be done in-place without creating a new array.
Approach 1: Two-Pointer Approach (O(n) time, O(1) space)
This approach uses two indices to reorganize the array in a single pass. One pointer insertPos tracks where the next non-zero element should be written, while the other pointer scans the array from left to right. Each time you encounter a non-zero value, place it at insertPos and increment the pointer. After the scan completes, fill the remaining positions with zeroes. The key insight is separating the discovery of non-zero values from their final placement, which preserves order naturally. This technique is a classic application of the two pointers pattern on an array. Time complexity is O(n) because each element is visited once, and space complexity is O(1) since all operations happen in-place.
Approach 2: Swap with Two-Pointer Technique (O(n) time, O(1) space)
This variation keeps two pointers: left for the position where the next non-zero element should go, and right for scanning the array. When nums[right] is non-zero, swap it with nums[left], then move both pointers forward. If the current element is zero, only advance right. The swap guarantees that non-zero values gradually shift toward the front while zeroes drift toward the end. Because each element participates in at most one swap, the algorithm still runs in O(n) time with O(1) extra space. This method is often preferred when you want a direct in-place transformation without a second pass to fill zeroes.
Recommended for interviews: Interviewers typically expect the linear O(n) in-place solution using the two-pointer technique. A brute-force approach that repeatedly shifts elements would degrade to O(n^2), which signals inefficient array manipulation. Demonstrating the optimal pointer-based strategy shows you understand how to process arrays with minimal movement and constant space, a common pattern in interview problems.
Approach 1: Two-Pointer Approach
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.
The code defines a function moveZeroes that takes an array nums and its size numsSize. The function maintains a pointer lastNonZeroFoundAt to keep track of the position to place the next non-zero element. As we iterate through nums, we shift non-zero elements to the front and then fill the remaining elements with zeroes.
Complexity
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.
Approach 2: Swap with Two-Pointer Technique
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.
This C function moves zeroes to the end by swapping elements within the array. A pointer j is used to track the location for swapping non-zero elements found during iteration.
Complexity
Time Complexity: O(n), single iteration with swaps.
Space Complexity: O(1), in-place swaps.
Approach 3: Two Pointers
We use a pointer k to record the current position to insert, initially k = 0.
Then we iterate through the array nums, and each time we encounter a non-zero number, we swap it with nums[k] and increment k by 1.
This way, we can ensure that the first k elements of nums are non-zero, and their relative order is the same as in the original array.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | Time Complexity: O(n), where n is the length of the array. We make a single pass through the array. |
| Swap with Two-Pointer Technique | Time Complexity: O(n), single iteration with swaps. |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer (Overwrite Non-Zero Elements) | O(n) | O(1) | General case when you want stable ordering and minimal swaps |
| Swap with Two-Pointer Technique | O(n) | O(1) | When an in-place transformation using swaps is simpler to implement |
Video Solution
Move Zeroes - Leetcode 283 - Python • NeetCode • 141,855 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Move Zeroes easy or hard?
Move Zeroes Python/Java solution
How to solve Move Zeroes in O(n)?
What is the best approach for Move Zeroes?
Is Move Zeroes asked at Google/Amazon/Meta?
What data structure is used in Move Zeroes?
What is the time complexity of Move Zeroes?
Ready to solve this problem?
Practice Move Zeroes with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor