⚡Flashcard Drill➔
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

  1. The cost to gather all balls at position i decomposes into contributions from the left and from the right.
  2. Sweep left to right, maintaining the number of balls seen so far and the running cost of bringing them all to the current position.
  3. The recurrence is ops += balls_seen, then balls_seen += boxes[i] -- each additional step moves every ball seen so far one more box.
  4. 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 ops before cnt: 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 with int() 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems