Duplicate Zeros solution and explanation
Google
9 more videos on this problem
1089. Duplicate Zeros - LeetCode SolutionGame of Coders · 7:52 · 29K views
[Java] Leetcode 1089. Duplicate Zeros [Array #5]Eric Programming · 9:07 · 11K views
Duplicate Zeros | Leetcode | Data Structures and AlgorithmsSoftware Journal · 8:43 · 4K views
1089. Duplicate Zeros (Leetcode Easy)Programming Live with Larry · 20:51 · 4K views
Duplicate Zeros - Two Pointers - Leetcode 1089 - Python and JavaCSTutor Center · 16:44 · 2K views
Leetcode 1089. Duplicate Zeros Python SolutionTechZoo · 2:00 · 2K views
LeetCode - 1089. Duplicate Zeros | Arrays CardAditya Mahajan · 9:13 · 2K views
LeetCode 1089. Duplicate Zeros Solution Explained - JavaAlgorithms and Data Structures Course · 12:03 · 1K views
LeetCode 1089 : Duplicate Zeros || EASY || JAVA || Detailed SolutionCodeGPT · 7:17 · 1K views
LeetCode Problem 1089. Duplicate Zeros || Java Solution WalkthroughUnknown Koder · 11:55 · 970 views
The problem
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.
Example 1:
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]
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 9
Approach overview
Problem Overview: You are given a fixed-length integer array. Every time a 0 appears, duplicate it and shift the remaining elements to the right. Elements that move past the array boundary are discarded. The modification must happen in-place without returning a new array.
The main challenge is handling shifts without overwriting values you still need to process. Since the array size cannot change, you must carefully manage how elements move while staying within bounds. This makes the problem a good exercise in array manipulation and careful pointer movement.
Approach 1: Two-Pointer Method (O(n) time, O(1) space)
This is the optimal solution. First scan the array and count how many zeros will be duplicated. This tells you how far elements will effectively shift. Then use two pointers: one starting from the original array end and another from the "virtual" end after duplication. Move backward so values are written safely without overwriting unprocessed elements. When the left pointer hits a zero, write two zeros while adjusting bounds if the virtual index exceeds the array size.
The key insight is processing from right to left. Writing from the back guarantees that elements not yet processed remain untouched. This turns what looks like repeated shifting into a single linear pass. The algorithm runs in O(n) time with O(1) extra space and is a classic two pointers technique.
Approach 2: Simulate In-Place Shift (O(n^2) time, O(1) space)
This straightforward method scans the array from left to right. Whenever you encounter a zero, shift every element to its right one position forward, starting from the end of the array. After the shift, place another zero in the next position and skip over the duplicated pair. Because the array length is fixed, the last element is dropped during the shift.
This approach mirrors exactly how you might perform the operation manually. However, each zero triggers a full right shift, which costs O(n). In the worst case, many zeros cause repeated shifts, resulting in O(n^2) time complexity. Space usage remains O(1) since the operation modifies the array directly.
Recommended for interviews: The two-pointer solution is what most interviewers expect. It demonstrates strong control over in-place array operations and avoids unnecessary shifting. Showing the shift-based approach first can demonstrate understanding of the mechanics, but the O(n) two-pointer optimization shows algorithmic maturity and efficiency.
Approach 1: Approach 1: Two-Pointer Method
The two-pointer technique allows us to shift elements efficiently. We use two pointers, one for the original array and one for the new modified version. The first pointer, 'i', traverses the array to count the potential size if zeros were duplicated (up to the length of the array). The second pointer, 'j', keeps track of the position for the final result.
We use these pointers to replicate zeros and copy other elements backward from the end.
def duplicateZeros(arr):
possibleDups = 0
length = len(arr) - 1
for left in range(length + 1):
if left > length - possibleDups:
break
if arr[left] == 0:
if left == length - possibleDups:
arr[length] = 0
length -= 1
break
possibleDups += 1
last = length - possibleDups
for i in range(last, -1, -1):
if arr[i] == 0:
arr[i + possibleDups] = 0
possibleDups -= 1
arr[i + possibleDups] = 0
else:
arr[i + possibleDups] = arr[i]
arr = [1, 0, 2, 3, 0, 4, 5, 0]
duplicateZeros(arr)
print(arr)class Solution {
public void duplicateZeros(int[] arr) {
int possibleDups = 0;
int length = arr.length - 1;
for (int left = 0; left <= length - possibleDups; ++left) {
if (arr[left] == 0) {
if (left == length - possibleDups) {
arr[length] = 0;
length -= 1;
break;
}
possibleDups++;
}
}
int last = length - possibleDups;
for (int i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
sol.duplicateZeros(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}#include <vector>
#include <iostream>
void duplicateZeros(std::vector<int>& arr) {
int possibleDups = 0;
int length = arr.size() - 1;
for (int left = 0; left <= length - possibleDups; ++left) {
if (arr[left] == 0) {
if (left == length - possibleDups) {
arr[length] = 0;
length -= 1;
break;
}
possibleDups++;
}
}
int last = length - possibleDups;
for (int i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
int main() {
std::vector<int> arr = {1, 0, 2, 3, 0, 4, 5, 0};
duplicateZeros(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}function duplicateZeros(arr) {
let possibleDups = 0;
let length = arr.length - 1;
for (let left = 0; left <= length - possibleDups; ++left) {
if (arr[left] == 0) {
if (left == length - possibleDups) {
arr[length] = 0;
length -= 1;
break;
}
possibleDups++;
}
}
let last = length - possibleDups;
for (let i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
let arr = [1, 0, 2, 3, 0, 4, 5, 0];
duplicateZeros(arr);
console.log(arr);#include <stdio.h>
void duplicateZeros(int* arr, int arrSize){
int i, possibleDups = 0, length = arrSize - 1;
for (i = 0; i <= length - possibleDups; i++) {
if (arr[i] == 0) {
if (i == length - possibleDups) {
arr[length] = 0;
length -= 1;
break;
}
possibleDups++;
}
}
int last = length - possibleDups;
for (i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
int main() {
int arr[] = {1, 0, 2, 3, 0, 4, 5, 0};
int arrSize = sizeof(arr) / sizeof(arr[0]);
duplicateZeros(arr, arrSize);
for (int i = 0; i < arrSize; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
class Solution {
public void DuplicateZeros(int[] arr) {
int possibleDups = 0;
int length = arr.Length - 1;
for (int left = 0; left <= length - possibleDups; ++left) {
if (arr[left] == 0) {
if (left == length - possibleDups) {
arr[length] = 0;
length -= 1;
break;
}
possibleDups++;
}
}
int last = length - possibleDups;
for (int i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
static void Main(string[] args) {
int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
Solution sol = new Solution();
sol.DuplicateZeros(arr);
Console.WriteLine(string.Join(" ", arr));
}
}The Python solution uses a very clear syntax to handle the in-place shifting of elements, maintaining efficiency by avoiding out-of-bound movements with the calculated stops on potentially exceeding the array length.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: Approach 2: Simulate In-Place Shift
This approach processes the array by creating temporary space for duplicated zeros and then shifting elements accordingly. It uses a separate count to track effective elements and carefully adjusts them in-memory to avoid exceeding the bounds.
def duplicateZeros(arr):
idx = 0
n = len(arr)
while idx < n:
if arr[idx] == 0:
for j in range(n - 1, idx, -1):
arr[j] = arr[j - 1]
idx += 1
idx += 1
arr = [1, 0, 2, 3, 0, 4, 5, 0]
duplicateZeros(arr)
print(arr)class Solution {
public void duplicateZeros(int[] arr) {
int idx = 0;
int n = arr.length;
while (idx < n) {
if (arr[idx] == 0) {
for (int j = n - 1; j > idx; j--) {
arr[j] = arr[j - 1];
}
idx++;
}
idx++;
}
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
sol.duplicateZeros(arr);
for (int num : arr) {
System.out.print(num + " ");
}
}
}#include <vector>
#include <iostream>
void duplicateZeros(std::vector<int>& arr) {
int idx = 0;
int n = arr.size();
while (idx < n) {
if (arr[idx] == 0) {
for (int j = n - 1; j > idx; --j) {
arr[j] = arr[j - 1];
}
idx++;
}
idx++;
}
}
int main() {
std::vector<int> arr = {1, 0, 2, 3, 0, 4, 5, 0};
duplicateZeros(arr);
for (int num : arr) {
std::cout << num << " ";
}
return 0;
}function duplicateZeros(arr) {
let idx = 0;
let n = arr.length;
while (idx < n) {
if (arr[idx] === 0) {
for (let j = n - 1; j > idx; --j) {
arr[j] = arr[j - 1];
}
idx++;
}
idx++;
}
}
let arr = [1, 0, 2, 3, 0, 4, 5, 0];
duplicateZeros(arr);
console.log(arr.toString());#include <stdio.h>
void duplicateZeros(int* arr, int arrSize) {
int idx = 0;
while (idx < arrSize) {
if (arr[idx] == 0) {
for (int j = arrSize - 1; j > idx; j--) {
arr[j] = arr[j - 1];
}
idx++;
}
idx++;
}
}
int main() {
int arr[] = {1, 0, 2, 3, 0, 4, 5, 0};
int arrSize = sizeof(arr) / sizeof(arr[0]);
duplicateZeros(arr, arrSize);
for (int i = 0; i < arrSize; i++) {
printf("%d ", arr[i]);
}
return 0;
}using System;
class Solution {
public void DuplicateZeros(int[] arr) {
int idx = 0;
int n = arr.Length;
while (idx < n) {
if (arr[idx] == 0) {
for (int j = n - 1; j > idx; j--) {
arr[j] = arr[j - 1];
}
idx++;
}
idx++;
}
}
static void Main(string[] args) {
int[] arr = {1, 0, 2, 3, 0, 4, 5, 0};
Solution sol = new Solution();
sol.DuplicateZeros(arr);
Console.WriteLine(string.Join(" ", arr));
}
}The approach in Python mimics the manual shifting of elements that ensure correct duplication of zero in place. However, it becomes a costly strategy as elements are moved one by one.
Time Complexity: O(n^2).
Space Complexity: O(1).
Approach 3: Default Approach
func duplicateZeros(arr []int) {
n := len(arr)
i, k := -1, 0
for k < n {
i, k = i+1, k+1
if arr[i] == 0 {
k++
}
}
j := n - 1
if k == n+1 {
arr[j] = 0
i, j = i-1, j-1
}
for j >= 0 {
arr[j] = arr[i]
if arr[i] == 0 {
j--
arr[j] = arr[i]
}
i, j = i-1, j-1
}
}impl Solution {
pub fn duplicate_zeros(arr: &mut Vec<i32>) {
let n = arr.len();
let mut i = 0;
let mut j = 0;
while j < n {
if arr[i] == 0 {
j += 1;
}
j += 1;
i += 1;
}
while i > 0 {
if arr[i - 1] == 0 {
if j <= n {
arr[j - 1] = arr[i - 1];
}
j -= 1;
}
arr[j - 1] = arr[i - 1];
i -= 1;
j -= 1;
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Method | Time Complexity: O(n). |
| Approach 2: Simulate In-Place Shift | Time Complexity: O(n^2). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Method | O(n) | O(1) | Best general solution. Efficient when modifying arrays in-place without repeated shifts. |
| Simulate In-Place Shift | O(n^2) | O(1) | Useful for understanding the mechanics of the problem or for very small arrays. |
Frequently asked questions
Is Duplicate Zeros easy or hard?
Duplicate Zeros is classified as an Easy problem on LeetCode, but many developers initially struggle with in-place shifting without overwriting data. Once the backward two-pointer technique is understood, the implementation becomes straightforward.
Duplicate Zeros Python/Java solution
Most implementations follow the same two-pointer logic regardless of language. Python, Java, C++, and JavaScript solutions count zeros first, then fill the array from the back while duplicating zeros when encountered.
How to solve Duplicate Zeros in O(n)?
First count how many zeros appear in the array. Treat the array as if it were extended by that many extra slots. Use two pointers starting from the end of the original array and the end of the virtual array, copying elements backward and writing two zeros whenever a zero is encountered.
What is the best approach for Duplicate Zeros?
The two-pointer approach is the most efficient method. It processes the array from right to left using a virtual expanded length based on the number of zeros. This avoids repeated shifting and achieves O(n) time complexity with O(1) extra space.
Is Duplicate Zeros asked at Google/Amazon/Meta?
Duplicate Zeros is commonly seen in coding interview preparation lists for companies like Amazon and Google because it tests in-place array manipulation and pointer control. The problem focuses on careful index handling rather than advanced data structures.
What data structure is used in Duplicate Zeros?
The problem uses a simple integer array. The main technique involves pointer manipulation within the array, often implemented using the two-pointer pattern to control reads and writes from the end of the array.
What is the time complexity of Duplicate Zeros?
The optimal two-pointer solution runs in O(n) time because each element is processed at most once when filling from the back of the array. A naive shift-based simulation may take O(n^2) time since every zero can trigger a full right shift of remaining elements.