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
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?
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?
Can we assume that the input array only contains integers, or should we handle cases where the input array contains non-integer values?
Can we assume that the input array is not empty, or should we handle cases where the input array is empty?
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:
Iteration
Two-pointers
Array copying
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:
Iterate through the array from left to right
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
If the current element is not 0, move to the next position
Stop iterating when you reach the end of the original array.
public void DuplicateZeros(int[] arr) {
int n = arr.Length;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
// Shift all elements to the right
for (int j = n - 1; j > i; j--) {
arr[j] = arr[j - 1];
}
// Insert a 0 at the current position
arr[i + 1] = 0;
// Move to the next position
i++;
}
}
}
def duplicate_zeros(arr):
n = len(arr)
i = 0
while i < n:
if arr[i] == 0:
# Shift all elements to the right
for j in range(n - 1, i, -1):
arr[j] = arr[j - 1]
# Insert a 0 at the current position
arr[i + 1] = 0
# Move to the next position
i += 2
else:
# Move to the next position
i += 1
public void duplicateZeros(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
// Shift all elements to the right
for (int j = n - 1; j > i; j--) {
arr[j] = arr[j - 1];
}
// Insert a 0 at the current position
arr[i + 1] = 0;
// Move to the next position
i++;
}
}
}
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
// Shift all elements to the right
for (int j = n - 1; j > i; j--) {
arr[j] = arr[j - 1];
}
// Insert a 0 at the current position
arr[i + 1] = 0;
// Move to the next position
i++;
}
}
}
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:
Initialize two pointers, one at the end of the original array and the other at the end of the modified array.
Iterate through the array from right to left
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.
If the current element is not 0:
Copy the current element to the current position in the modified array.
Decrement both pointers by 1.
Stop iterating when you reach the beginning of the original array.
// This method duplicates each zero in the input array without using an additional array.
public void DuplicateZeros(int[] arr) {
// Get the length of the input array.
int n = arr.Length;
// Initialize two pointers i and j to 0.
int i = 0, j = 0;
// Find the end of the modified array.
while (j < n) {
// If the current element is 0, increment j to count the extra space for the duplicated zero.
if (arr[i] == 0) {
j++;
}
// Increment both i and j to move forward in the array.
i++;
j++;
}
// Shift elements and duplicate zeros.
// Decrement i and j to the last index of the original array and the end of the modified array, respectively.
i--;
j--;
// Iterate through the array from right to left.
while (i >= 0 && j >= 0) {
// If the current element is 0, duplicate it and decrement j.
if (arr[i] == 0) {
arr[j] = 0;
j--;
}
// Copy the current element to the modified array and decrement both i and j.
arr[j] = arr[i];
i--;
j--;
}
}
def duplicate_zeros(arr):
n = len(arr)
i, j = 0, 0
# Find the end of the modified array
while j < n:
if arr[i] == 0:
j += 1
i += 1
j += 1
# Shift elements and duplicate zeros
i -= 1
j -= 1
while i >= 0 and j >= 0:
if arr[i] == 0:
arr[j] = 0
j -= 1
arr[j] = arr[i]
i -= 1
j -= 1
public void duplicateZeros(int[] arr) {
int n = arr.length;
int i = 0, j = 0;
// Find the end of the modified array
while (j < n) {
if (arr[i] == 0) {
j++;
}
i++;
j++;
}
// Shift elements and duplicate zeros
i--;
j--;
while (i >= 0 && j >= 0) {
if (arr[i] == 0) {
arr[j] = 0;
j--;
}
arr[j] = arr[i];
i--;
j--;
}
}
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
int i = 0, j = 0;
// Find the end of the modified array
while (j < n) {
if (arr[i] == 0) {
j++;
}
i++;
j++;
}
// Shift elements and duplicate zeros
i--;
j--;
while (i >= 0 && j >= 0) {
if (arr[i] == 0) {
arr[j] = 0;
j--;
}
arr[j] = arr[i];
i--;
j--;
}
}
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:
Create a new array of the same size as the original array.
Initialize a counter variable to keep track of the current position in the new array.
Iterate through the array from left to right.
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.
If the current element is not 0:
Copy the current element to the current position in the new array.
Increment the counter variable.
Stop iterating when you reach the end of the original array.
Copy the new array back to the original array.
// This method duplicates each zero in the input array by creating a copy of the array.
public void DuplicateZeros(int[] arr) {
// Get the length of the input array.
int n = arr.Length;
// Create a new array with the same length as the input array to hold the modified array.
int[] copy = new int[n];
// Initialize a pointer j to 0 to keep track of the current position in the modified array.
int j = 0;
// Iterate through the input array.
for (int i = 0; i < n && j < n; i++) {
// If the current element is 0 and there is enough space for a duplicated zero, add two zeros to the modified array.
if (arr[i] == 0 && j < n - 1) {
copy[j++] = 0;
copy[j++] = 0;
} else {
// Otherwise, copy the current element to the modified array.
copy[j++] = arr[i];
}
}
// Copy the modified array back to the input array.
Array.Copy(copy, arr, n);
}
def duplicateZeros(arr):
n = len(arr)
copy = [0] * n
j = 0
for i in range(n):
if arr[i] == 0 and j < n - 1:
copy[j] = 0
copy[j+1] = 0
j += 2
else:
copy[j] = arr[i]
j += 1
arr[:] = copy
public void duplicateZeros(int[] arr) {
int n = arr.length;
int[] copy = new int[n];
int j = 0;
for (int i = 0; i < n && j < n; i++) {
if (arr[i] == 0 && j < n - 1) {
copy[j++] = 0;
copy[j++] = 0;
} else {
copy[j++] = arr[i];
}
}
System.arraycopy(copy, 0, arr, 0, n);
}
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
vector<int> copy(n, 0);
int j = 0;
for (int i = 0; i < n && j < n; i++) {
if (arr[i] == 0 && j < n - 1) {
copy[j++] = 0;
copy[j++] = 0;
} else {
copy[j++] = arr[i];
}
}
arr = copy;
}
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:
Create an empty stack.
Iterate through the array from left to right.
If the current element is 0:
Push a 0 onto the stack.
Push another 0 onto the stack.
If the current element is not 0:
Push the current element onto the stack.
Stop iterating when you reach the end of the original array.
Pop elements from the stack and store them back in the original array starting from the end of the array.
// This method duplicates each zero in the input array using a Queue data structure.
public void DuplicateZeros(int[] arr) {
// Get the length of the input array.
int n = arr.Length;
// Create a new queue to hold the elements of the input array.
Queue<int> q = new Queue<int>();
// Iterate through the input array.
for (int i = 0; i < n; i++) {
// Add the current element to the queue.
q.Enqueue(arr[i]);
// If the current element is 0, add another 0 to the queue.
if (arr[i] == 0) {
q.Enqueue(0);
}
// Overwrite the current element with the first element from the queue.
arr[i] = q.Dequeue();
// If we just removed the last element from the queue,
// it means that we have processed all the elements we need to
// and we can exit the loop early
if (q.Count == 0) {
break;
}
}
}
def duplicateZeros(arr):
n = len(arr)
stack = []
for i in range(n):
stack.append(arr[i])
if arr[i] == 0:
stack.append(0)
arr[i] = stack.pop(0)
# If we just removed the last element from the stack,
# it means that we have processed all the elements we need to
# and we can exit the loop early
if not stack:
break
public void duplicateZeros(int[] arr) {
int n = arr.length;
Deque<Integer> stack = new LinkedList<>();
for (int i = 0; i < n; i++) {
stack.addLast(arr[i]);
if (arr[i] == 0) {
stack.addLast(0);
}
arr[i] = stack.pollFirst();
// If we just removed the last element from the stack,
// it means that we have processed all the elements we need to
// and we can exit the loop early
if (stack.isEmpty()) {
break;
}
}
}
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
queue<int> q;
for (int i = 0; i < n; i++) {
q.push(arr[i]);
if (arr[i] == 0) {
q.push(0);
}
arr[i] = q.front();
q.pop();
// If we just removed the last element from the queue,
// it means that we have processed all the elements we need to
// and we can exit the loop early
if (q.empty()) {
break;
}
}
}
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.
