0283. Move Zeroes¶
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?
Analysis¶
All the questions regarding displacing from one to the other can be solved by using two pointers. For this question, we need to track the current zero position (j) and current processing position (i). We don't need to care about the sequence of zeros, but we need to take care of the sequence of non-zeros. Thus, we should loop from the processing position from the begining to the end. If we see any zero while processing, we should move the next element that is non-zero (i) to the current zero position (j). We should also increase j by 1 since the next zero position to mark current j has been swapped with non-zero. Now, the new j can either be zero or non-zero, but what can be sure is that for the next swap the current j will be non-zero and the sequence is always correct.
- Time: O(n)
- Space: O(1)
Code¶
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for (int i = 0, j = 0; i < nums.size(); ++i) {
if (nums[i]) { // j will only record the non-zero position
swap(nums[j++], nums[i]);
}
}
}
};