Duplicate Zeros

ArraySimulationTwo Pointers

Given an array of integers, you should modify the array by duplicating any zeroes found, shifting the remaining elements to the right. Note that elements that are pushed beyond the last position of the array are not written. Modify the array in place without using extra space for another array.

Example 1

Input

Output

[1, 0, 0, 2, 3, 0, 0, 4]

Explanation. Here, zeros are duplicated as they are found, shifting subsequent elements right. Note the last zero is not duplicated as there's no space.

Example 2

Input

Output

[0, 0, 1, 2]

Explanation. The initial zero is duplicated, shifting the rest to the right. 3 is not included as it exceeds the array size.

Example 3

Input

Output

[1, 2, 3]

Explanation. There are no zeros in this array, so it remains unchanged.

Example 4

Input

Output

[0, 0, 0]

Explanation. Each zero is duplicated, but since the array has limited size, only partial duplicates are inserted.

Follow-up: Can you solve the problem in O(n) time complexity?

Constraints:

1. The array contains between 1 and 10,000 elements. 2. Each element in the array is in the range from 0 to 9.

Views: 3