Solution For Move Zeroes

Problem Statement:

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:
Input: [0,1,0,3,12] Output: [1,3,12,0,0]

Approach:

In this problem, we need to move all zeroes to the end of the array while maintaining the order of non-zero elements. We are not allowed to use extra space to solve this problem.

One approach is to use two pointers. We can initialize two pointers, i and j, both starting at index 0. We will iterate through the array with i pointer and keep j pointer pointing to the first 0 we encounter.

As we move through the array with i pointer, we check if the element at i is non-zero. If it is non-zero, we swap the elements at i and j and increment both i and j pointers to check the next element.

If we find a zero element, we simply continue to move i forward without swapping.

This approach helps us maintain the relative order of non-zero numbers while moving zeros to the end of the array.

Once we have completed traversing the array, all the zeroes will be shifted to the end of the array and all the non-zero elements will be in their original order.

Solution:

Here is the Python implementation of the above approach:

class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i, j = 0, 0
while i < n:
if nums[i] != 0:
nums[i], nums[j] = nums[j], nums[i] j += 1
i += 1

The time complexity of this approach is O(n) as we are only traversing the array once. The space complexity is O(1) as we are not using any extra space to solve this problem.

Step by Step Implementation For Move Zeroes

public class Solution {
    public void moveZeroes(int[] nums) {
        // keep track of the position of "0"
        int pos = 0; 
        for(int i = 0; i < nums.length; i++) {
            // if the current element is not "0", swap it with the element at position "pos"
            if(nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[pos];
                nums[pos] = temp;
                // increment the position of "0"
                pos++;
            }
        }
    }
}

def moveZeroes(nums):
    
    # We define two pointer variables, one at the beginning
    # of the list and one at the end.
    
    # We move the end pointer towards the front of the list
    # until it reaches a non-zero element.
    
    # We then swap the element at the end pointer with the
    # element at the front pointer.
    
    # We move the front pointer forward by one and repeat
    # the process until the front pointer reaches the end
    # of the list.
    
    front = 0
    end = len(nums) - 1
    
    while front <= end:
        while nums[end] == 0 and end > front:
            end -= 1
        if nums[end] != 0:
            nums[front], nums[end] = nums[end], nums[front]
            front += 1
            end -= 1
        else:
            front += 1

var moveZeroes = function(nums) {
    // create a variable to keep track of the number of zeroes
    let numZeroes = 0;
    
    // loop through the array
    for (let i = 0; i < nums.length; i++) {
        // if the current element is a zero, increment the numZeroes variable
        if (nums[i] === 0) {
            numZeroes++;
        } 
        // if the current element is not a zero
        else {
            // swap the current element with the element at index i - numZeroes
            // this puts the non-zero element in the position of the first zero we encountered
            let temp = nums[i];
            nums[i] = nums[i - numZeroes];
            nums[i - numZeroes] = temp;
        }
    }
    
    return nums;
};

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

class Solution {
public:
    void moveZeroes(vector& nums) {
        int lastNonZeroFoundAt = 0;
        // If the current element is not 0, then we need to
        // append it just in front of last non 0 element we found. 
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != 0) {
                nums[lastNonZeroFoundAt++] = nums[i];
            }
        }
        // After we have finished processing new elements,
        // all the non-zero elements are already at beginning of array.
        // We just need to fill remaining array with 0's.
        for (int i = lastNonZeroFoundAt; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

public class Solution {
    public void MoveZeroes(int[] nums) {
        // We will keep two pointers i and j. 
        // i will point to the current element in the array 
        // j will point to the next non-zero element in the array 
        // If the current element is non-zero, we will swap it with the next non-zero element 
        // and increment both the pointers i and j. 
        // If the current element is zero, we will just increment the pointer j 
        // to point to the next element.
        
        int i = 0, j = 0; 
        while (j < nums.Length) { 
            if (nums[j] != 0) { 
                int temp = nums[i]; 
                nums[i] = nums[j]; 
                nums[j] = temp; 
                i++; 
            } 
            j++; 
        } 
    }
}