283. Move Zeroes

Description

Given an array nums, write a function that moves all 0s to the end of it while maintaining the relative order of the non-zero elements. The function should do this in-place without making a copy of the array.

Intuition

The problem can be solved efficiently by using two pointers. The idea is to iterate through the array, and whenever a 0 is found, move it to the end while keeping the relative order of the non-zero elements intact. The key here is to do this in-place without using extra space.

Approach

1. Two Pointers Technique: Use two pointers, l and r, where l starts at the beginning and r at the end of the array. - Traverse the array with pointer l. When a 0 is found, shift all elements to the left from l to r and place 0 at the r-th position. - Decrement the r pointer, and update l accordingly. - Continue this process until l surpasses r.
2. Optimization: Instead of continuously moving elements, consider maintaining a count of zeros and placing them at the end after traversing the entire array.

Complexity

Time Complexity:

O(n^2) in the worst case because for every 0 found, the remaining elements are shifted, leading to a quadratic time complexity.

Space Complexity:

O(1) since the operation is performed in-place without using any extra space.

Code

C++

class Solution {
public:
    void moveZeroes(vector& nums) {
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r) {
            if (nums[l] == 0) {
                int oldVal = l;
                while (l < r) {
                    nums[l] = nums[l + 1];
                    l++;
                }
                nums[r] = 0;
                r--;

                nums[oldVal] == 0 ? l = oldVal : l = oldVal + 1;
            } else {
                l++;
            }
        }
    }
};

Python

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        l = 0
        r = len(nums) - 1
        while l <= r:
            if nums[l] == 0:
                oldVal = l
                while l < r:
                    nums[l] = nums[l + 1]
                    l += 1
                nums[r] = 0
                r -= 1

                if nums[oldVal] == 0:
                    l = oldVal
                else:
                    l = oldVal + 1
            else:
                l += 1

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            if (nums[l] == 0) {
                int oldVal = l;
                while (l < r) {
                    nums[l] = nums[l + 1];
                    l++;
                }
                nums[r] = 0;
                r--;

                if (nums[oldVal] == 0) {
                    l = oldVal;
                } else {
                    l = oldVal + 1;
                }
            } else {
                l++;
            }
        }
    }
}

JavaScript

var moveZeroes = function (nums) {
    let l = 0;
    let r = nums.length - 1;
    while (l <= r) {
        if (nums[l] === 0) {
            var oldVal = l;
            while (l < r) {
                nums[l] = nums[l + 1];
                l++;
            }
            nums[r] = 0;
            r--;

            nums[oldVal] === 0 ? l = oldVal : l = oldVal + 1;
        } else {
            l++;
        }
    }
    return nums;
};