Move Zeroes LeetCode Solution

Problem Statement

The problem, Move Zeroes LeetCode Solution states that you are given an array containing zero and non-zero elements and you need to move all the zeroes to the end of the array, maintaining the relative order of non-zero elements in the array. You also need to implement an in-place algorithm for the same.

Examples:

Test Case 1 –

Input – [0, 1, 0, 3, 12]

Output – [1, 3, 12, 0, 0]

Test Case 2 –

Input – [0]

Output – [0]

Test Case 3 –

Input – [10, 11, 0, 1, 2, 5]

Output – [10, 11, 1, 2, 5, 0]

What is an in-place solution?

In-place means we should not be allocating any space for an extra array.

Anyways, the solution is still very easy to crack as we are allowed to modify the existing array.

One of the most common examples of an in-place algorithm is the Heap Sort algorithm.

Approach

Idea

The problem can be solved using two pointer technique. We will take two pointers, pointing to the start of the array. Whenever we encounter a zero, we increment one of the pointers keeping the other at the same location.  When we encounter a non-zero element, we swap the values present at the location of the pointers and increment both of them.

Code for Move Zeroes LeetCode Solution

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 0;
        while(j<n){
            if(nums[j]==0) j++;
            else{
                swap(nums[i], nums[j]);
                i++;
                j++;
            }
        }
    }
};

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int i = 0, j = 0;
        while(j<n){
            if(nums[j]==0){
                j++;
            }
            else{
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                i++;
                j++;
            }
        }
    }
}

class Solution(object):
    def moveZeroes(self, nums):
        n = len(nums)
        i = 0
        j = 0
        while j<n:
            if nums[j] == 0:
                j = j+1
            else:
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                i = i+1
                j = j+1

Complexity Analysis for Move Zeroes LeetCode Solution

Time Complexity

Since we are traversing the array only once, the time complexity for the algorithm is O(n).

Space Complexity

Since we are not using any auxiliary space, the space complexity for the algorithm is O(1).

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique