Duplicate Zeros

ArraySimulationTwo Pointers

Given a fixed-length integer array arr, duplicate each occurrence of zero, shifting the remaining elements to the right. The elements beyond the length of the original array should be discarded. Modify the array in place without using extra space for another array. You may assume that the array has enough space to accommodate the elements including the duplicates.

Example 1

Input

Output

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

Explanation. The zeros at positions 1 and 4 are duplicated, and the elements after these positions are correctly shifted right and truncated after the original length.

Example 2

Input

Output

[1,2,3]

Explanation. There are no zeros to duplicate. The array remains unchanged.

Example 3

Input

Output

[0,0,0,0,0,0,0]

Explanation. Every zero is duplicated, but only the first few fit within the original length, others are discarded.

Example 4

Input

Output

[8,4,5,0,0,0,0,0]

Explanation. The initial zeros start shifting all elements right, and the original last elements are discarded to fit the array size.

Follow-up: Can you achieve this with a single pass through the array and without using any additional data structures?

Constraints:

1. `1 <= arr.length <= 10000` 2. `0 <= arr[i] <= 9` 3. The array `arr` is passed by reference and will be modified in place.

Views: 2