The Duplicate Zeros problem is a common coding interview problem that can be solved using various approaches. It’s a problem that tests your understanding of array manipulation and your ability to come up with a performant solution. In this article, we’ll dive deep into the problem, understand its requirements, explore multiple ways to solve it, and analyze the time and space complexities of each solution.
Here’s the problem statement from LeetCode:
Given a fixed-length array
arr of integers, 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, do not return anything from your function.
Input: [1,0,2,3,0,4,5,0] Output: null (In-place operation. Array becomes [1,0,0,2,3,0,0,4])
One straightforward way to solve this problem is by iterating through the array and duplicating zeros while shifting elements to the right. We can achieve this using nested loops. Let’s take a look at this approach in Python:
def duplicateZeros(arr): i = 0 n = len(arr) while i < n: if arr[i] == 0: for j in range(n-1, i, -1): arr[j] = arr[j-1] i += 2 else: i += 1
The time complexity for this solution is O(n^2) because we are iterating through the array and shifting elements every time we encounter a zero.
The space complexity for this solution is O(1) as we are manipulating the array in-place without using extra memory.
Optimized Approach Using Two-Pass
We can improve the above solution by using two passes through the array. In the first pass, we can count the number of zeros that need to be duplicated. With that information, we can then start from the end of the array and copy elements to their new positions.
Here’s how we can implement this approach in Python:
def duplicateZeros(arr): count_zeros = arr.count(0) n = len(arr) i = n - 1 while count_zeros > 0: if arr[i] == 0: if i + count_zeros < n: arr[i + count_zeros] = 0 count_zeros -= 1 if i + count_zeros < n: arr[i + count_zeros] = arr[i] i -= 1
The time complexity is O(n) for counting zeros and O(n) for the second pass, making the overall time complexity O(n).
The space complexity remains O(1) as we are doing all operations in-place.
Optimized Approach Using Queue
Another way to approach this problem is by using a queue data structure to keep track of the elements that should be moved.
from collections import deque def duplicateZeros(arr): n = len(arr) queue = deque() for i in range(n): queue.append(arr[i]) if len(queue) > 1: arr[i] = queue.popleft() if arr[i] == 0 and i < n - 1: queue.append(0) i += 1 if len(queue) > 1: arr[i] = queue.popleft()
The time complexity is O(n) for iterating through the array.
The space complexity is O(n) for storing the queue.
The Duplicate Zeros problem provides a good test for understanding array manipulations and in-place operations. While the brute-force approach has a time complexity of O(n^2), we can optimize it to O(n) time complexity with two-pass or queue methods.
Choosing the right approach depends on various factors like the constraints of the problem and the allowable space complexity. If you can’t use additional space, the two-pass method is preferable due to its O(1) space complexity. Otherwise, you may opt for the queue-based solution for its easier implementation.