What is the minimum number of operations to move all balls to each box?

The minimum number of operations is determined by how far each ball needs to move to reach a specific box. A prefix sum approach helps calculate the most efficient movements.

What pattern does the "Minimum Number of Operations to Move All Balls to Each Box" problem follow?

This problem follows a pattern of using arrays and prefix sums to efficiently compute the minimum operations, making it a typical example of array manipulation and optimization.

How do I use a two-pass approach to solve this problem?

First, calculate the moves for each box from left to right. Then, iterate from right to left to adjust the results, accounting for balls coming from the right side.

Why is the time complexity O(n) for this problem?

The time complexity is O(n) because you only need to make two passes through the array: once left to right and once right to left, which is linear in relation to the size of the input.

How can I avoid common pitfalls when solving this problem?

Ensure you correctly implement the two-pass approach and account for all ball movements, considering both left-to-right and right-to-left operations to avoid suboptimal solutions.

#1769

Medium

auto_awesome数组·string

LeetCode 题解工作台

移动所有球到每个盒子所需的最小操作数

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是空的，而 boxes[i] 的值为 '1' 表示盒子里有一个小球。在一步操作中，你可以将一个小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个…

数组字符串前缀和

题目描述

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是空的，而 boxes[i] 的值为 '1' 表示盒子里有一个小球。

在一步操作中，你可以将一个小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的最小操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

示例 1：

输入：boxes = "110"
输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入：boxes = "001011"
输出：[11,8,5,4,3,4]

提示：

n == boxes.length
1 <= n <= 2000
boxes[i] 为 '0' 或 '1'

lightbulb

解题思路

方法一：预处理 + 枚举

我们可以预处理出每个位置 $i$ 左边的小球移动到 $i$ 的操作数，记为 $left[i]$ ；每个位置 $i$ 右边的小球移动到 $i$ 的操作数，记为 $right[i]$ 。那么答案数组的第 $i$ 个元素就是 $left[i] + right[i]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 boxes 的长度。

我们还可以进一步优化空间复杂度，只用一个答案数组 $ans$ 以及若干个变量即可。

时间复杂度 $O(n)$ ，忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。其中 $n$ 为 boxes 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        left = [0] * n
        right = [0] * n
        cnt = 0
        for i in range(1, n):
            if boxes[i - 1] == '1':
                cnt += 1
            left[i] = left[i - 1] + cnt
        cnt = 0
        for i in range(n - 2, -1, -1):
            if boxes[i + 1] == '1':
                cnt += 1
            right[i] = right[i + 1] + cnt
        return [a + b for a, b in zip(left, right)]

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate efficiently applies a two-pass approach.
question_mark
Candidate correctly implements prefix sum for optimization.
question_mark
Candidate demonstrates a clear understanding of minimizing operations with array manipulation.

warning

常见陷阱

外企场景

error
Misunderstanding the movement of balls across boxes, leading to incorrect calculation of the number of moves.
error
Not utilizing the prefix sum technique, resulting in a suboptimal solution.
error
Forgetting to account for both directions (left-to-right and right-to-left) when calculating the minimum moves for each box.

swap_horiz

进阶变体

外企场景

arrow_right_alt
If the number of boxes is fixed, optimize for fewer operations with precomputed results.
arrow_right_alt
Alter the problem to involve moving balls only in one direction, either left or right.
arrow_right_alt
Extend the problem to handle more complex movement rules, like moving multiple balls in one operation.

help

常见问题

外企场景

继续练习

#2055 蜡烛之间的盘子 #1177 构建回文串检测 #2381 字母移位 II