NeetCode #103LC-1769MediumArrays & Hashing
← Back to All Problems#103 · #1769 · Minimum Number of Operations to Move All Balls to Each Box(移动所有球到每个盒子所需的最小操作数)
📌 Problem Statement & Constraints
You have
n boxes given as a binary string boxes, where boxes[i] == '1' means box i contains a ball. In one operation you may move one ball to an adjacent box. Return an array where answer[i] is the minimum number of operations to move all balls to box i. Constraints: 1 <= boxes.length <= 2000.💡 Core Algorithmic Approaches
- The cost to gather all balls at position
idecomposes into contributions from the left and from the right. - Sweep left to right, maintaining the number of balls seen so far and the running cost of bringing them all to the current position.
- The recurrence is
ops += balls_seen, thenballs_seen += boxes[i]-- each additional step moves every ball seen so far one more box. - Repeat the sweep right to left and add the two contributions. This is the classic two-pass prefix technique.
💻 Benchmark Python3 Implementation
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
res = [0] * n
# left-to-right contribution
cnt = ops = 0
for i in range(n):
res[i] += ops # cost of bringing left balls here
cnt += int(boxes[i])
ops += cnt # next position costs one more per ball
# right-to-left contribution
cnt = ops = 0
for i in range(n - 1, -1, -1):
res[i] += ops
cnt += int(boxes[i])
ops += cnt
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two linear sweeps.
💾 Space Complexity
O(1) beyond the output array.
⚠️ Interview Pitfalls & Follow-ups
- Updating
opsbeforecnt: the order matters -- add the cost for the current position first, then absorb the current box's ball, so the next position accounts for it. - Recomputing the cost per index with a nested loop: O(n^2), which is 4 * 10^6 here and still passes, but the two-pass version is O(n).
- Using the raw character
boxes[i]as an integer:'0'is truthy as a string; convert withint()or compare to'1'. - Only doing one direction: both left and right contributions are needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.