This is an easy problem with the description being:
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
Here as the name of the problem says is about moving zeroes around the array, maintaining the order.
To get this sorted out you need to move and stack the amount of zeros as you iterate the list, like a snowball effect.
Every time you encounter an zero you increase the counter, if is not a zero then you add value on a temporary variable and replace the value with zero and use the counter to get the right index for that temporary value new index position to be set.
The image bellow illustrates the idea. The green represents the index, the blue box the numbers that will swap, the red is the zero count.
Basically you use the zero count with the index position to determine where the swap will occur.
class Solution {
public void moveZeroes(int[] nums) {
int zerosCount = 0;
for(int i=0 ; i<nums.length ; i++) {
if(nums[i] == 0) { // don't need to swap, just update counter
zerosCount++;
} else if(zerosCount > 0) { // if zero counts is 0 there is no need of array update
final int temp = nums[i];
nums[i] = 0;
nums[i - zerosCount] = temp;
}
}
}
}
Runtime: 2 ms, faster than 61.61% of Java online submissions for Move Zeroes.
Memory Usage: 45.2 MB, less than 44.67% of Java online submissions for Move Zeroes.
This technique is called two pointers because you use two identifiable pointers to determine how to arrange the order and get the result (first one being i and the second zerosCount variable).
That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.
Until next post! :)