Move Zeroes
Problem Description
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:
Example 2:
Constraints:
- 1 <= nums.length <= 104
- -231 <= nums[i] <= 231 - 1
Follow up: Could you minimize the total number of operations done?
Solve it on LeetCode
Approaches
1. Brute Force: Move and Shift
Intuition:
The simplest way to solve this problem is:
- Create a new array of the same size.
- Make a first pass over the original array:
- Whenever you see a non-zero element, copy it into the next available position in the new array.
- After you’ve copied all non-zero elements, the front part of the new array will contain all non-zero numbers in their original order.
- Make a second pass on the new array (or just continue from where you stopped) and fill the remaining positions with 0.
- Finally, copy the new array back into the original one.
Code:
- Time Complexity: O(n), where n is the length of the array.
- Space Complexity: O(n), due to the use of additional array.
Example Walkthrough:
Input:
After the first pass (collect non-zeroes into result):
The second pass fills the remaining positions with zero (they may already be zero, but that’s fine):
Finally, we copy result back into nums:
2. Two-Pointers: Two Pass
Intuition:
A more efficient approach to solve this problem is using the two-pointer technique.
Use two indices:
- writePos points to the next position to place a non-zero.
- i scans the array.
First pass: copy every non-zero to nums[writePos] and advance writePos.
Second pass: fill the remaining positions with zeros.
This preserves the relative order of non-zeros.
Code:
- Time Complexity: O(n), where n is the length of the array.
- Space Complexity: O(1), since we are modifying the array in place without using additional storage.
Example Walkthrough:
Input:
After first pass:
After second pass:
3. Two-Pointers: One-Pass
Intuition:
We can fine-tune our previous two-pointer approach by swapping in place.
Maintain two indices:
- writePos points to the next position where a non-zero should live.
- readPos scans the array left to right.
Whenever nums[readPos] is non-zero, swap it with nums[writePos] (only if readPos != writePos) and advance writePos. This compacts non-zeros in a single pass and leaves zeros behind naturally.
Code:
- Time Complexity: O(n), as the array is traversed once.
- Space Complexity: O(1), no additional data structures are used.