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.

Description Hints 4 Solution Video 7:52

1089. Duplicate Zeros

Easy54.1% acceptance4 companies

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 <= 10⁴
0 <= arr[i] <= 9

Asked at 4 companies

Google Amazon Microsoft Bloomberg

Topics

Array Two Pointers

Hints open one at a time

Hint 1

This is a great introductory problem for understanding and working with the concept of in-place operations. The problem statement clearly states that we are to modify the array in-place. That does not mean we cannot use another array. We just don't have to return anything.

Hint 2

A better way to solve this would be without using additional space. The only reason the problem statement allows you to make modifications in place is that it hints at avoiding any additional memory.

Hint 3

The main problem with not using additional memory is that we might override elements due to the zero duplication requirement of the problem statement. How do we get around that?

Hint 4

If we had enough space available, we would be able to accommodate all the elements properly. The new length would be the original length of the array plus the number of zeros. Can we use this information somehow to solve the problem?

7:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def duplicateZeros(self, arr: List[int]) -> None:
      """
      Do not return anything, modify arr in-place instead.
      """
      

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

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

Input

[1,2,3]

Your code is saved on this device.Solution