283. Move Zeroes
DifficultyEasy
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:
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?
Solutions
Solution 1: Two Pointers
Thinking
Zeros must go to the end while nonzeros keep their order. Let \(k\) be the next slot for a nonzero.
Each nonzero is swapped with \(\textit{nums}[k]\) and \(k\) advances, so the prefix of length \(k\) is the original nonzero sequence.
We use a pointer \(k\) to record the current position to insert, initially \(k = 0\).
Then we iterate through the array \(\textit{nums}\), and each time we encounter a non-zero number, we swap it with \(\textit{nums}[k]\) and increment \(k\) by 1.
This way, we can ensure that the first \(k\) elements of \(\textit{nums}\) are non-zero, and their relative order is the same as in the original array.
The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 | |
1 2 3 4 5 6 7 8 9 10 | |