Problem 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.
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
Move Zeroes – LeetCode
Solution(s):
To move all zeros to the end of an integer array while maintaining the relative order of the non-zero elements, you can follow two approaches.
Approach 1: Using Extra Space
- Create a new array to store temporary result.
- Iterate through the input array and add all non-zero elements to the result array.
- Append zeros to the end of the temporary array.
- Finally, copy temporary array into original array.
Java Code:
public void moveZeroes(int[] nums) {
int len=nums.length;
int temp[]=new int[len];
int j=0;
//Copy non-zero elements to output array
for(int i=0;i<len;i++) {
if(nums[i]!=0) {
temp[j++]=nums[i];
}
}
//Append zeros to the end of the temporary array
for(int i=j;i<len;i++) {
temp[i]=0;
}
//copy temporary array into original array
for(int i=0;i<len;i++) {
nums[i]=temp[i];
}
}Complexity:
- Time-Complexity: O(n)
- Space-COmplexity: O(n)
Approach 2:In-Place
- Iterate through the array, move non-zero elements to the beginning.
- Fill the remaining positions with zeros
Java Code:
public static void moveZeroes(int[] nums) {
int nonZeroIndex = 0;
int len=nums.length;
// Iterate through the array, move non-zero elements to the beginning
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
nums[nonZeroIndex++] = nums[i];
}
}
// Fill the remaining positions with zeros
while (nonZeroIndex < len) {
nums[nonZeroIndex++] = 0;
}
}Complexity:
- Time-Complexity : O(n)
- Space-Complexity : O(1)
Approach 3 : In-place using single loop
public static void moveZeroes(int[] nums) {
int j= 0;
int len=nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
swap(nums[j],nums[i]);
j++;
}
}
}Complexity:
- Time-Complexity: O(n)
- Space-Complexity: O(1)