This post is completed by 1 user

  • 1
 Add to List
Beginner

555. Move All Zeroes to the End of the Array

Problem Statement:

Given an array of random numbers, move all the zeros to the end of the array while maintaining the relative order of the non-zero elements.

Example 1:

Input: {0, 1, 0, 3, 12}
Output: {1, 3, 12, 0, 0}

Example 2:

Input: {1, 2, 0, 0, 3, 4}
Output: {1, 2, 3, 4, 0, 0}

Example 3:

Input: {0, 0, 0, 0}
Output: {0, 0, 0, 0}

Naive Solution:

  • Create a new result array of the same length as the input array.
  • Iterate through the input array and place each non-zero element in the result array.
  • Leave the zeroes at the end by default, as the uninitialized values in the result array are zeroes.

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

 

Output

[0, 1, 0, 3, 12] 
[1, 3, 12, 0, 0]

Better Solution:

  • Use a pointer (or counter) to track the position of non-zero elements.
  • Iterate through the array and shift all non-zero elements to the front.
  • Fill the remaining spaces with zeroes.

Time Complexity: O(N), Space Complexity: O(1)

 

Output

Input: [1, 2, 0, 0, 3, 4]
Output: [1, 2, 3, 4, 0, 0]

Related Problems: