Move Zeroes To End
Given an unsorted array of integers, you have to move the array elements in a way such that all the zeroes are transferred to the end, and all the non-zero elements are moved to the front. The non-zero elements must be ordered in their order of appearance.

For example, if the input array is: [0, 1, -2, 3, 4, 0, 5, -27, 9, 0], then the output array must be:

[1, -2, 3, 4, 5, -27, 9, 0, 0, 0].

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, ‘n’ is the size of the array.

Input format :

The first line of input contains a single integer ‘T’ representing the number of test cases. The first line of each test case contains a single integer ‘N’ representing the size of the array. The second line of each test case contains ‘N’ integers representing the elements of the array.

Output Format :

For each test case, modify the input array and print the output in a new line

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Move Zeroes To End

Given an unsorted array of integers, you have to move the array elements in a way such that all the zeroes are transferred to the end, and all the non-zero elements are moved to the front. The non-zero elements must be ordered in their order of appearance.

For example, if the input array is: [0, 1, -2, 3, 4, 0, 5, -27, 9, 0], then the output array must be:

[1, -2, 3, 4, 5, -27, 9, 0, 0, 0].

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, ‘n’ is the size of the array.

Input format :

The first line of input contains a single integer ‘T’ representing the number of test cases.      

The first line of each test case contains a single integer ‘N’ representing the size of the array. The second line of each test case contains ‘N’ integers representing the elements of the array.

Output Format :

For each test case, modify the input array and print the output in a new line

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50 
1 <= N <= 10^6
-10000 <= A[i] <= 10000

Where ‘T’ is the number of test cases, ‘N’ is the size of the array, A[i] is the value of the element present at the ith index.
Time Limit:1sec

Accepted Answer

Naive method

We can create a new array of integers. As soon as we find a non-zero element, we can directly insert it into our new array. After that, we can insert all the left zero’s.

We can easily calculate the number of left zeroes as :

Size of original array = size of new array + number of zero’s (since we only took non-zero elements.

Algorithm :

Initialise a non-zero pointer with 0 value.
Start traversing the array until we reach the end,
- If a non-zero element is found, insert it in new array. Else,
- If a zero element is found, just continue.
After we reach the end, total number of zero’s will be original array size - new array size.
Insert these many zeros into new array.

Space Complexity: O(1)Explanation:

O(N)

Since we are creating a new array.

Time Complexity: O(n)Explanation:

O(N)

Since we are maintaining two pointers, and as soon as a non-zero pointer reaches the end, we stop. So the maximum numbers we are visiting is ‘N’ therefore complexity is O(N)

C++ (g++ 5.4)

/*
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is size of the given array.
*/

void pushZerosAtEnd(std::vector &arr) {
    int zptr = -1;
    int nzptr = -1;
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            zptr = i;
            break;
        }
    }

    if (zptr == -1) {
        return;
    }

    for (int i = zptr + 1; i < n; i++) {
        if (arr[i] != 0) {
            nzptr = i;
            break;
        }
    }

    if (nzptr == -1) {
        return;
    }

    while (nzptr < n) {
        // Swapping.
        int tmp = arr[zptr];
        arr[zptr] = arr[nzptr];
        arr[nzptr] = tmp;

        zptr++;
        while (nzptr < n && arr[nzptr] == 0) {
            nzptr++;
        }
    }
}

Python (3.5)

"""
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is size of the given array.
"""

def pushZerosAtEnd(arr) :
    zptr = -1
    nzptr = -1
    n = len(arr)
    for i in range(n):
        if (arr[i] == 0):
            zptr = i
            break
       
   

    if (zptr == -1):
        return
   

    for i in range(zptr+1,n):
        if (arr[i] != 0):
            nzptr = i
            break
       
   

    if (nzptr == -1):
        return
   

    while (nzptr < n):
        # Swapping.
        tmp = arr[zptr]
        arr[zptr] = arr[nzptr]
        arr[nzptr] = tmp

        zptr+=1
        while (nzptr < n and arr[nzptr] == 0):
            nzptr+=1

Java (SE 1.8)

/*
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is size of the given array.
*/

import java.util.*;

public class Solution {
    public static void pushZerosAtEnd(ArrayList < Integer > arr) {
        int zptr = -1;
        int nzptr = -1;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            if (arr.get(i) == 0) {
                zptr = i;
                break;
            }
        }

        if (zptr == -1) {
            return;
        }

        for (int i = zptr + 1; i < n; i++) {
            if (arr.get(i) != 0) {
                nzptr = i;
                break;
            }
        }

        if (nzptr == -1) {
            return;
        }

        while (nzptr < n) {
            Collections.swap(arr, zptr, nzptr);
            zptr++;
            while (nzptr < n && arr.get(nzptr) == 0) {
                nzptr++;
            }
        }
    }
}

Accepted Answer

Optimized Approach

We will use two pointers :

zero element pointer → points to the first zero encountered.
Non - zero element pointer → points to the first non-zero number encountered.

Our job is to only push zero’s towards the end, so all the non-zero numbers before any occurrence of zero’s will stay as it is. Hence our Non-zero pointer will point only when we encounter a non-zero element after zero element pointer.

When both of our pointers are set, we can swap the elements present at these places within the same array. Move the zero-pointers ahead. We will also move the non-zero pointer until we find a non zero element.

As soon as the non-zero pointer reaches the end, we will stop.

Edge cases :

If initially, we couldn’t find our zero pointer, which means there are no elements that are zero in the array, then we will return as it is.
If we found a zero pointer, but we could not find a non-zero pointer, then it means there are only zero’s in the array. In this case, also we will simply return.

Space Complexity: O(1)Explanation:

O(1)

Since we are doing changes in the same array, there is no need for additional space.

Time Complexity: O(n)Explanation:

O(N)

Since we are maintaining two pointers, and as soon as a non-zero pointer reaches the end, we stop. So the maximum numbers we are visiting is ‘N’ therefore complexity is O(N)

C++ (g++ 5.4)

/*
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is size of the given array.
*/

void pushZerosAtEnd(std::vector &arr) {
    int zptr = -1;
    int nzptr = -1;
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) {
            zptr = i;
            break;
        }
    }

    if (zptr == -1) {
        return;
    }

    for (int i = zptr + 1; i < n; i++) {
        if (arr[i] != 0) {
            nzptr = i;
            break;
        }
    }

    if (nzptr == -1) {
        return;
    }

    while (nzptr < n) {
        // Swapping.
        int tmp = arr[zptr];
        arr[zptr] = arr[nzptr];
        arr[nzptr] = tmp;

        zptr++;
        while (nzptr < n && arr[nzptr] == 0) {
            nzptr++;
        }
    }
}

Python (3.5)

'''
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is size of the given array.
'''

from typing import List

def pushZerosAtEnd(arr: List[int]):
    
    zptr = -1
    nzptr = -1
    n = len(arr)
    for i in range(n):
        if arr[i] == 0:
            zptr = i
            break

    if zptr == -1:
        return

    for i in range(zptr + 1, n):
        if arr[i] != 0:
            nzptr = i
            break

    if nzptr == -1:
        return

    while nzptr < n:
        # Swapping.
        tmp = arr[zptr]
        arr[zptr] = arr[nzptr]
        arr[nzptr] = tmp

        zptr += 1
        while nzptr < n and arr[nzptr] == 0:
            nzptr += 1

Java (SE 1.8)

/*
	Time Complexity: O(N)
	Space Complexity: O(N)

	where 'N' is size of the given array.
*/

import java.util.*;

public class Solution {
    public static void pushZerosAtEnd(ArrayList < Integer > arr) {
        int zptr = -1;
        int nzptr = -1;
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            if (arr.get(i) == 0) {
                zptr = i;
                break;
            }
        }

        if (zptr == -1) {
            return;
        }

        for (int i = zptr + 1; i < n; i++) {
            if (arr.get(i) != 0) {
                nzptr = i;
                break;
            }
        }

        if (nzptr == -1) {
            return;
        }

        while (nzptr < n) {
            Collections.swap(arr, zptr, nzptr);
            zptr++;
            while (nzptr < n && arr.get(nzptr) == 0) {
                nzptr++;
            }
        }
    }
}

Given an unsorted array of integers, you have to move the array elements in a way such that all the zeroes are transferred to the end, and all the non-zero elements are moved to the front. The non-zero elements must be ordered in their order of appearance.

For example, if the input array is: [0, 1, -2, 3, 4, 0, 5, -27, 9, 0], then the output array must be:

[1, -2, 3, 4, 5, -27, 9, 0, 0, 0].

Expected Complexity: Try doing it in O(n) time complexity and O(1) space complexity. Here, ‘n’ is the size of the array.

Input format :

Output Format :

Note :

Constraints :

Top Borderfree Mern Stack Developer interview questions & answers

Popular interview questions of Mern Stack Developer