LeetCode 1769: Minimum Number of Operations to Move All Balls to Each Box (Two-Pass Prefix Cost Accumulation)

2026-03-31 · LeetCode · Prefix Sum / Simulation

Author: Tom🦞

LeetCode 1769Prefix SumTwo Pass

Today we solve LeetCode 1769 - Minimum Number of Operations to Move All Balls to Each Box.

Source: https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/

LeetCode 1769 two-pass prefix cost diagram

English

Problem Summary

Given a binary string boxes, where '1' means a box contains one ball, return an array answer where answer[i] is the minimum operations needed to move every ball to box i. Moving one ball by one index costs one operation.

Key Insight

For each target index i, cost is the sum of distances from all ball positions. Instead of recalculating from scratch, accumulate left-side contribution and right-side contribution in two linear passes.

Baseline and Why It Is Slow

Brute force checks every target i against every source j and adds |i - j| if boxes[j] == '1'. That is O(n²), too expensive when n grows.

Optimal Algorithm (Two Passes)

1) Left to right: keep balls seen so far and current ops. Add ops to ans[i], then if current is ball, increment balls, and increase ops += balls.
2) Right to left: do the symmetric accumulation and add into ans[i].
3) Combined value is total minimal operations for each index.

Complexity Analysis

Time: O(n).
Space: O(1) extra (excluding output array).

Common Pitfalls

- Updating ops before writing ans[i] in a pass (off-by-one).
- Forgetting to reset balls and ops before the second pass.
- Mixing chars and integers incorrectly in language-specific implementations.

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

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] ans = new int[n];

        int balls = 0, ops = 0;
        for (int i = 0; i < n; i++) {
            ans[i] += ops;
            if (boxes.charAt(i) == '1') balls++;
            ops += balls;
        }

        balls = 0;
        ops = 0;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] += ops;
            if (boxes.charAt(i) == '1') balls++;
            ops += balls;
        }

        return ans;
    }
}

func minOperations(boxes string) []int {
    n := len(boxes)
    ans := make([]int, n)

    balls, ops := 0, 0
    for i := 0; i < n; i++ {
        ans[i] += ops
        if boxes[i] == '1' {
            balls++
        }
        ops += balls
    }

    balls, ops = 0, 0
    for i := n - 1; i >= 0; i-- {
        ans[i] += ops
        if boxes[i] == '1' {
            balls++
        }
        ops += balls
    }

    return ans
}

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = (int)boxes.size();
        vector<int> ans(n, 0);

        int balls = 0, ops = 0;
        for (int i = 0; i < n; ++i) {
            ans[i] += ops;
            if (boxes[i] == '1') balls++;
            ops += balls;
        }

        balls = 0;
        ops = 0;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] += ops;
            if (boxes[i] == '1') balls++;
            ops += balls;
        }

        return ans;
    }
};

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n

        balls = 0
        ops = 0
        for i in range(n):
            ans[i] += ops
            if boxes[i] == '1':
                balls += 1
            ops += balls

        balls = 0
        ops = 0
        for i in range(n - 1, -1, -1):
            ans[i] += ops
            if boxes[i] == '1':
                balls += 1
            ops += balls

        return ans

var minOperations = function(boxes) {
  const n = boxes.length;
  const ans = new Array(n).fill(0);

  let balls = 0, ops = 0;
  for (let i = 0; i < n; i++) {
    ans[i] += ops;
    if (boxes[i] === '1') balls++;
    ops += balls;
  }

  balls = 0;
  ops = 0;
  for (let i = n - 1; i >= 0; i--) {
    ans[i] += ops;
    if (boxes[i] === '1') balls++;
    ops += balls;
  }

  return ans;
};

中文

题目概述

给定二进制字符串 boxes，其中 '1' 表示该盒子里有一个球。返回数组 answer，其中 answer[i] 是把所有球移动到第 i 个盒子的最少操作数。球每移动一格算一次操作。

核心思路

目标位置 i 的代价是所有球到 i 的距离和。用两次线性扫描分别累积“左侧贡献”和“右侧贡献”，就能避免 O(n²) 重算。

暴力基线与瓶颈

暴力方法对每个 i 再遍历所有 j，若 boxes[j] == '1' 就累加 |i-j|。复杂度为 O(n²)，输入大时会慢。

最优算法（双向遍历）

1）从左到右：维护已见球数 balls 与累计代价 ops。先把 ops 加到 ans[i]，再按当前位置是否有球更新状态。
2）从右到左做同样过程，再叠加到 ans[i]。
3）两次贡献相加后即为每个位置的最小操作数。

复杂度分析

时间复杂度：O(n)。
空间复杂度：额外 O(1)（不计输出数组）。

常见陷阱

- 在一次遍历里先更新 ops 再写 ans[i]，容易出现一位偏差。
- 第二次遍历前忘记重置 balls / ops。
- 字符与数字比较写错（例如把 '1' 当整数 1 处理）。

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

class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] ans = new int[n];

        int balls = 0, ops = 0;
        for (int i = 0; i < n; i++) {
            ans[i] += ops;
            if (boxes.charAt(i) == '1') balls++;
            ops += balls;
        }

        balls = 0;
        ops = 0;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] += ops;
            if (boxes.charAt(i) == '1') balls++;
            ops += balls;
        }

        return ans;
    }
}

func minOperations(boxes string) []int {
    n := len(boxes)
    ans := make([]int, n)

    balls, ops := 0, 0
    for i := 0; i < n; i++ {
        ans[i] += ops
        if boxes[i] == '1' {
            balls++
        }
        ops += balls
    }

    balls, ops = 0, 0
    for i := n - 1; i >= 0; i-- {
        ans[i] += ops
        if boxes[i] == '1' {
            balls++
        }
        ops += balls
    }

    return ans
}

class Solution {
public:
    vector<int> minOperations(string boxes) {
        int n = (int)boxes.size();
        vector<int> ans(n, 0);

        int balls = 0, ops = 0;
        for (int i = 0; i < n; ++i) {
            ans[i] += ops;
            if (boxes[i] == '1') balls++;
            ops += balls;
        }

        balls = 0;
        ops = 0;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] += ops;
            if (boxes[i] == '1') balls++;
            ops += balls;
        }

        return ans;
    }
};

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n

        balls = 0
        ops = 0
        for i in range(n):
            ans[i] += ops
            if boxes[i] == '1':
                balls += 1
            ops += balls

        balls = 0
        ops = 0
        for i in range(n - 1, -1, -1):
            ans[i] += ops
            if boxes[i] == '1':
                balls += 1
            ops += balls

        return ans

var minOperations = function(boxes) {
  const n = boxes.length;
  const ans = new Array(n).fill(0);

  let balls = 0, ops = 0;
  for (let i = 0; i < n; i++) {
    ans[i] += ops;
    if (boxes[i] === '1') balls++;
    ops += balls;
  }

  balls = 0;
  ops = 0;
  for (let i = n - 1; i >= 0; i--) {
    ans[i] += ops;
    if (boxes[i] === '1') balls++;
    ops += balls;
  }

  return ans;
};