Move the zeroes to the end

Easy

2000 ms limit256 MB memoryTwo pointers Arrays

Stuck?

Show a hint

Keep a second index for where the next non-zero value should be written. Then fill whatever is left with zeroes.

The ideas behind this problem

Arrays and lists in everyday code Where your data actually lives Two pointers: replacing a nested loop with a single pass Arrays: what is cheap and what is not Arrays, and allocating memory Vectors and the standard algorithms Arrays and ArrayList Lists and tuples

Next in this lesson

Building Pascal's triangle row by row

Move every zero to the end of the list, keeping the other numbers in their original order.

Worked example#

For [0, 1, 0, 3, 12], walk through with a second pointer marking where the next non-zero belongs:

looking at	is it zero?	action	list so far
0	yes	skip it
1	no	write at position 0	1
0	yes	skip it	1
3	no	write at position 1	1, 3
12	no	write at position 2	1, 3, 12

Three numbers were written, so positions 3 and 4 are filled with zeroes: [1, 3, 12, 0, 0].

The order of the non-zero numbers is preserved because they are written in the order they were found. This two-pointer idea, one reading and one writing, comes up whenever you need to filter a list in place.

Constraints#

1 <= n <= 100000
-1000 <= nums[i] <= 1000

Input

nums is a count then that many integers.

Output

The rearranged list, separated by spaces.

Examples

Input

5
0 1 0 3 12

Output

1 3 12 0 0

The non-zero numbers keep their order, and the two zeroes go to the end.

Input

1
0

Output

A single zero is already where it belongs.

Input

3
1 2 3

Output

1 2 3

With no zeroes, nothing moves.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.