Move Zero's to End

Easy
0/40
Average time to solve is 15m
profile
Contributed by
311 upvotes

Problem statement

Given an array 'arr' of 'n' non-negative integers, your task is to move all the zeros to the end of the array while keeping the non-zero elements at the start of the array in their original order. Return the modified array.


Example : 
Input: ‘n’ = 5, ‘arr’ = [1, 2, 0, 0, 2, 3]
Output: [1, 2, 2, 3, 0, 0]

Explanation: Moved all the 0’s to the end of an array, and the rest of the elements retain the order at the start.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘n’, the number of elements in the array ‘arr’.
The next line contains the 'n' space-separated integers of the array 'arr'.
Output Format: 
The output contains the elements of the modified array separated by space.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function.
Sample input 1:
4
0 0 0 1
Sample output 1:
1 0 0 0
Explanation of sample input 1:
Output: [1, 0, 0, 0]

We move all the 0’s to the end of an array, and the rest of the elements retained the order at the start.
Sample input 2:
5
4 0 3 2 5
Sample output 2:
4 3 2 5 0
Explanation of sample input 2:
Output: [4, 3, 2, 5, 0]

we move all the 0’s to the end of an array, and the rest of the elements retained the order at the start.
Expected time complexity:
 The expected time complexity is O(n).
Constraints:
1 ≤ n ≤ 10^6
0 ≤ arr[i] ≤ 10^9

Time limit: 1 sec
Hint

Can you think of using two-pointers here?

Approaches (1)
Naive Two-Pointer Approach

Approach: 

 

We will maintain two-pointers first. Suppose we find a zero (say its index is 2) while traversing. In that case, this place should be occupied by the immediate following non-zero elements (so that order will be maintained for non-zero elements), so we will place a pointer here (at 2). We will try to find the next non-negative integer using another pointer; once it is found, zero places (2nd index) have to be occupied by this non-negative number, and the non-negative number will be occupied by zero.
 

Algorithm: 
 

  • Initialize an integer ‘j = 0’
  • Iterate from 0 to ‘n’ with iterator ‘i’
    • If ‘a[i] != 0’ then update ‘a[j++] = a[i]’
  • Iterate till ‘j < n’
    • Set ‘a[j] = 0’
  • Return ‘a’
Time Complexity

O(n), Where ‘n’ is the size of the array ‘a’.

 

We are simply iterating over the array ‘a’.

 

Hence, the time complexity is O(n).

Space Complexity

O(1).

 

We are using constant extra space.

 

Hence, the space complexity is O(1).

Code Solution
(100% EXP penalty)
Move Zero's to End
Full screen
Console