Move Zeroes
Problem link: https://leetcode.com/problems/move-zeroes/
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.
Input
An integer array nums.
Output
Void (Modify the input array in-place).
Example
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]
Explanation
Non-zero elements (1, 3, 12) are shifted to the front while preserving their order, and zeroes are filled in the remaining spots at the end.
Brute Force
Intuition
Create a temporary array. Copy all non-zero elements into it first, then fill the rest with zeroes. Finally, copy the temp array back to the original.
Approach
- Create a new array of the same size.
- Iterate through the original array and add non-zero elements to the new array.
- Fill the remaining positions in the new array with 0.
- Copy elements back to the original array.
Dry Run
nums = [0,1,0,3] Temp = [1,3,0,0] Copy back to nums.
Code (Java)
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
int[] temp = new int[n];
int j = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != 0) {
temp[j++] = nums[i];
}
}
for (int i = 0; i < n; i++) {
nums[i] = temp[i];
}
}
}
Complexity Analysis
We use an additional array of size N to store the elements.
Optimal Solution
Intuition
Use a 'read' pointer and a 'write' pointer. The write pointer only moves when we find a non-zero element. This allows us to overwrite the array from the beginning without needing extra space.
Approach
- Initialize
insertPos = 0. - Iterate through the array using index
i. - Whenever
nums[i]is non-zero, swapnums[i]withnums[insertPos]and incrementinsertPos. - Swapping ensures that zeroes are naturally pushed to the back while order is preserved.
Dry Run
nums = [0,1,0,3,12]
- i=0: 0, insertPos=0
- i=1: 1, swap(0,1) -> [1,0,0,3,12], insertPos=1
- i=2: 0, continue
- i=3: 3, swap(1,3) -> [1,3,0,0,12], insertPos=2
- i=4: 12, swap(2,4) -> [1,3,12,0,0], insertPos=3
Code (Java)
class Solution {
public void moveZeroes(int[] nums) {
int insertPos = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
// Swap current non-zero element with the element at insertPos
int temp = nums[insertPos];
nums[insertPos] = nums[i];
nums[i] = temp;
insertPos++;
}
}
}
}
Complexity Analysis
We only use a single loop and a few variables; no extra data structures are used.
Quick Revision (Brute Force)
- Use a temp array
- Copy non-zeroes first
- Fill rest with zeroes
- O(N) space
Quick Revision (Optimal)
- Two Pointers (read and write)
- Swap non-zeroes with insertPos
- In-place modification
- Preserves relative order
- O(1) space