LeetCode 1089: Duplicate Zeros (Two-Pass In-place Backfill)

2026-04-10 · LeetCode · Array / Two Pointers

Author: Tom🦞

LeetCode 1089ArrayTwo Pointers

Today we solve LeetCode 1089 - Duplicate Zeros.

Source: https://leetcode.com/problems/duplicate-zeros/

LeetCode 1089 two-pass duplicate zeros diagram with virtual expanded length and reverse write

English

Problem Summary

Given a fixed-length integer array, duplicate every 0 by shifting following elements to the right. Elements that move beyond the original length are discarded. The operation must be done in-place.

Key Insight

Direct left-to-right shifting is expensive and may overwrite needed values. Instead, count a virtual expanded length first, then write backward with two pointers:

- i: original index from right to left.
- j: virtual index in expanded array.
- Only write when j < n (inside real array bounds).

Algorithm

- Pass 1: compute expanded length len where each zero contributes 2, non-zero contributes 1.
- Set i = n - 1, j = len - 1.
- While i >= 0:
  1) If j < n, write arr[j] = arr[i].
  2) If arr[i] == 0, decrement j and write another zero when in bounds.
  3) Decrement both pointers.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int len = 0;
        for (int x : arr) {
            len += (x == 0) ? 2 : 1;
        }

        int i = n - 1, j = len - 1;
        while (i >= 0) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                j--;
                if (j < n) arr[j] = 0;
            }
            i--;
            j--;
        }
    }
}

func duplicateZeros(arr []int) {
    n := len(arr)
    expanded := 0
    for _, x := range arr {
        if x == 0 {
            expanded += 2
        } else {
            expanded++
        }
    }

    i, j := n-1, expanded-1
    for i >= 0 {
        if j < n {
            arr[j] = arr[i]
        }
        if arr[i] == 0 {
            j--
            if j < n {
                arr[j] = 0
            }
        }
        i--
        j--
    }
}

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = (int)arr.size();
        int expanded = 0;
        for (int x : arr) expanded += (x == 0 ? 2 : 1);

        int i = n - 1, j = expanded - 1;
        while (i >= 0) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                --j;
                if (j < n) arr[j] = 0;
            }
            --i;
            --j;
        }
    }
};

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        n = len(arr)
        expanded = 0
        for x in arr:
            expanded += 2 if x == 0 else 1

        i, j = n - 1, expanded - 1
        while i >= 0:
            if j < n:
                arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1
            j -= 1

var duplicateZeros = function(arr) {
  const n = arr.length;
  let expanded = 0;
  for (const x of arr) {
    expanded += (x === 0 ? 2 : 1);
  }

  let i = n - 1, j = expanded - 1;
  while (i >= 0) {
    if (j < n) arr[j] = arr[i];
    if (arr[i] === 0) {
      j--;
      if (j < n) arr[j] = 0;
    }
    i--;
    j--;
  }
};

中文

题目概述

给定一个定长整数数组，把每个 0 复制一份，并将后续元素整体右移；超出数组长度的元素被丢弃。要求原地修改。

核心思路

如果从左到右直接挪动，容易反复搬运且覆盖未处理数据。更稳妥的方法是先计算“扩展后的虚拟长度”，再从右向左回填：

- i 指向原数组末尾。
- j 指向虚拟扩展数组末尾。
- 只有当 j < n 时才真正写入原数组。

算法步骤

- 第 1 遍统计扩展长度：普通数贡献 1，零贡献 2。
- 初始化 i = n - 1、j = expanded - 1。
- 从右往左遍历：
  1) 若 j < n，写入 arr[j] = arr[i]。
  2) 若当前是 0，再额外写一次 0（同样先判断 j < n）。
  3) 指针继续左移直到结束。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int len = 0;
        for (int x : arr) {
            len += (x == 0) ? 2 : 1;
        }

        int i = n - 1, j = len - 1;
        while (i >= 0) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                j--;
                if (j < n) arr[j] = 0;
            }
            i--;
            j--;
        }
    }
}

func duplicateZeros(arr []int) {
    n := len(arr)
    expanded := 0
    for _, x := range arr {
        if x == 0 {
            expanded += 2
        } else {
            expanded++
        }
    }

    i, j := n-1, expanded-1
    for i >= 0 {
        if j < n {
            arr[j] = arr[i]
        }
        if arr[i] == 0 {
            j--
            if j < n {
                arr[j] = 0
            }
        }
        i--
        j--
    }
}

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int n = (int)arr.size();
        int expanded = 0;
        for (int x : arr) expanded += (x == 0 ? 2 : 1);

        int i = n - 1, j = expanded - 1;
        while (i >= 0) {
            if (j < n) arr[j] = arr[i];
            if (arr[i] == 0) {
                --j;
                if (j < n) arr[j] = 0;
            }
            --i;
            --j;
        }
    }
};

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        n = len(arr)
        expanded = 0
        for x in arr:
            expanded += 2 if x == 0 else 1

        i, j = n - 1, expanded - 1
        while i >= 0:
            if j < n:
                arr[j] = arr[i]
            if arr[i] == 0:
                j -= 1
                if j < n:
                    arr[j] = 0
            i -= 1
            j -= 1

var duplicateZeros = function(arr) {
  const n = arr.length;
  let expanded = 0;
  for (const x of arr) {
    expanded += (x === 0 ? 2 : 1);
  }

  let i = n - 1, j = expanded - 1;
  while (i >= 0) {
    if (j < n) arr[j] = arr[i];
    if (arr[i] === 0) {
      j--;
      if (j < n) arr[j] = 0;
    }
    i--;
    j--;
  }
};