 # Duplicate Zeros

Given a fixed-length integer array `arr`, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

## Problem Statement

The problem statement is to implement a function that takes in a fixed-length integer array `arr`, duplicates each occurrence of zero in the array, and shifts the remaining elements to the right. The modification should be done in place, meaning the function should not create a new array or return anything. Any elements beyond the length of the original array should not be modified.

## Examples

```Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
```

Example 2:

```Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]```

## Clarifying Questions

1. Can you please clarify what is meant by "fixed-length integer array"? Is it an array with a fixed number of elements, or is the size of the array fixed and cannot be changed once it is created?
2. Could you provide an example of what the modified array should look like after duplicating each occurrence of zero and shifting the remaining elements to the right?
3. Can we assume that the input array only contains integers, or should we handle cases where the input array contains non-integer values?
4. Can we assume that the input array is not empty, or should we handle cases where the input array is empty?
5. Should we only duplicate zeros that occur in the original array, or should we also duplicate zeros that are created as a result of shifting elements to the right?

## Solutions

There are different approaches to solving this problem. Some of them include:

1. Iteration
2. Two-pointers
3. Array copying
4. Stack

The optimal approach would depend on the constraints of the problem and the trade-offs between time and space complexity.

### Iteration:

This approach involves iterating through the array and checking each element. When a zero is encountered, it duplicates the zero by shifting the remaining elements to the right and inserting a new zero in its place. This approach has a time complexity of O(n^2) since for each zero, it shifts all the elements to the right.

#### Algorithm:

1. Iterate through the array from left to right
2. If the current element is 0:
• Shift all elements to the right by one position
• Insert a 0 in the current position
• Move to the next position
3. If the current element is not 0, move to the next position
4. Stop iterating when you reach the end of the original array.

Time complexity: In the worst-case scenario where every element of the array is 0, we would have to shift every element to the right, resulting in O(n^2) time complexity.

Space complexity: The space complexity is O(1) since we are modifying the input array in place and not using any extra data structures.

### Two-pointers:

This approach involves using two pointers, one at the end of the original array and the other at the end of the modified array. It then iterates through the array from right to left, duplicating zeros and shifting the elements to the right. This approach has a time complexity of O(n) since it only iterates through the array once.

#### Algorithm:

1. Initialize two pointers, one at the end of the original array and the other at the end of the modified array.
2. Iterate through the array from right to left
3. If the current element is 0:
• Duplicate the 0 by inserting another 0 at the current position in the modified array.
• Decrement the modified array pointer by 1.
4. If the current element is not 0:
• Copy the current element to the current position in the modified array.
• Decrement both pointers by 1.
5. Stop iterating when you reach the beginning of the original array.

Time complexity: The time complexity of this approach is O(n) since we only need to iterate over the array once.

Space complexity: The space complexity is O(1) since we are modifying the input array in place and not using any extra data structures.

### Array copying:

This approach involves creating a new array and copying elements from the original array to the new array while duplicating zeros and shifting the remaining elements to the right. This approach has a time complexity of O(n) since it only iterates through the array once, but it requires extra space to store the new array.

#### Algorithm:

1. Create a new array of the same size as the original array.
2. Initialize a counter variable to keep track of the current position in the new array.
3. Iterate through the array from left to right.
4. If the current element is 0:
• Copy the current element to the current position in the new array.
• Increment the counter variable.
• Insert a 0 in the next position in the new array.
• Increment the counter variable again.
5. If the current element is not 0:
• Copy the current element to the current position in the new array.
• Increment the counter variable.
6. Stop iterating when you reach the end of the original array.
7. Copy the new array back to the original array.
Note: The algorithm for array copying involves creating a new array or vector of the same size as the original array, iterating over the elements of the original array and copying them to the new array, while duplicating zeros as necessary. Finally, the new array is copied back to the original array using either the Copy method in C# or the arraycopy method in Java or by assigning the new vector to the original vector in C++.

Time complexity: The time complexity of this approach is O(n).

Space complexity: This approach requires creating a new array of the same size as the input array, resulting in a space complexity of O(n).

### Stack:

This approach involves using a stack data structure to store the elements of the array. It then iterates through the stack, duplicating zeros and shifting the remaining elements to the right, and stores the modified elements back in the stack. This approach has a time complexity of O(n) but requires extra space to store the stack.

#### Algorithm:

1. Create an empty stack.
2. Iterate through the array from left to right.
3. If the current element is 0:
• Push a 0 onto the stack.
• Push another 0 onto the stack.
4. If the current element is not 0:
• Push the current element onto the stack.
5. Stop iterating when you reach the end of the original array.
6. Pop elements from the stack and store them back in the original array starting from the end of the array.
Note: The algorithm for using a stack or queue involves iterating over the elements of the original array, adding each element to the stack or queue, and duplicating zeros as necessary. Then, for each element in the original array, we pop or dequeue an element from the stack or queue, assign it to the original array, and continue to the next element. If we have processed all the elements we need to, we can exit the loop early.

Time complexity: The time complexity of this approach is O(n).

Space complexity: This approach requires using a stack or queue to store the elements of the array, resulting in a space complexity of O(n).

In terms of time complexity, the most efficient approach is the Two-pointers approach since it has a time complexity of O(n) and does not require any additional space. However, in terms of space complexity, the Two-pointers approach and the Interation (Naive) approach are the best since they both have a space complexity of O(1), meaning they do not require any additional memory. The Array copying and Stack approaches have a space complexity of O(n), making them less desirable in terms of space usage.
Share: 