Description
https://leetcode.com/problems/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?
Explanation
Two pointers. One faster, one slower. The slower pointer points to the first zero position. When the faster one finds a non-zero number, swap with the first zero.
Python Solution
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = 0
j = 0
while j < len(nums):
if nums[j] != 0:
temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
i += 1
j += 1- Time complexity: O(N).
- Space complexity: O(1).
class Solution {
public void moveZeroes(int[] nums) {
if(nums.length == 0 || nums == null) return;
int idx = 0;
for(int i =0; i< nums.length;i++){
if(nums[i] != 0){
nums[idx++] = nums[i];
}
}
while(idx < nums.length){
nums[idx++] = 0;
}
return;
}
}