1769. Minimum Number of Operations to Move All Balls to Each Box - Explanation

Problem Link

1. Brute Force

Intuition

For each box position, we want to know the total number of moves needed to bring all balls to that position. A move shifts a ball one position left or right. The cost to move a ball from position i to position pos is simply the absolute difference |pos - i|.

We can compute this directly by iterating through all boxes for each target position and summing up the distances from each ball.

Algorithm

1. Create a res array of size n.
2. For each target position pos:
   • Iterate through all boxes.
   • If box i contains a ball (value is '1'), add |pos - i| to res.
3. Return the res array.

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

        for pos in range(n):
            for i in range(n):
                if boxes[i] == '1':
                    res[pos] += abs(pos - i)

        return res

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity:
  • $O(1)$ extra space.
  • $O(n)$ space for the output list.

---

2. Prefix Sum

Intuition

We can split the total cost for each position into contributions from the left and the right. For balls on the left, the cost is i * count_left - sum_of_indices_left. For balls on the right, the cost is sum_of_indices_right - i * count_right. Using prefix sums for both the count of balls and the sum of their indices, we can compute both parts efficiently.

Algorithm

1. Build two prefix arrays:
   • prefix_count[i] = number of balls in boxes 0 to i-1.
   • index_sum[i] = sum of indices of balls in boxes 0 to i-1.
2. For each position i:
   • Left contribution: i * left_count - left_sum.
   • Right contribution: right_sum - i * right_count.
   • Add both to get the res for position i.
3. Return the res array.

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

        prefix_count = [0] * (n + 1)
        index_sum = [0] * (n + 1)
        for i in range(n):
            prefix_count[i + 1] = prefix_count[i] + (boxes[i] == '1')
            index_sum[i + 1] = index_sum[i] + (i if boxes[i] == '1' else 0)

        for i in range(n):
            left = prefix_count[i]
            left_sum = index_sum[i]

            right = prefix_count[n] - prefix_count[i + 1]
            right_sum = index_sum[n] - index_sum[i + 1]

            res[i] = (i * left - left_sum) + (right_sum - i * right)

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Prefix Sum (Optimal)

Intuition

Instead of storing prefix arrays, we can compute the contribution incrementally using two passes. In the left-to-right pass, we track how many balls are to the left and accumulate the moves needed to shift them one position right. In the right-to-left pass, we do the same for balls on the right. The sum of both passes gives the final answer.

Algorithm

1. Left-to-right pass:
   • Track balls (count of balls seen) and moves (cumulative operations).
   • For each position, res[i] = balls + moves, then update moves += balls and add current ball if present.
2. Right-to-left pass:
   • Reset balls and moves.
   • For each position from right to left, add balls + moves to res[i], then update similarly.
3. Return the res array.

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

        balls = moves = 0
        for i in range(n):
            res[i] = balls + moves
            moves += balls
            balls += int(boxes[i])

        balls = moves = 0
        for i in range(n - 1, -1, -1):
            res[i] += balls + moves
            moves += balls
            balls += int(boxes[i])

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity:
  • $O(1)$ extra space.
  • $O(n)$ space for the output list.

---

Common Pitfalls

Character vs Integer Comparison

The input is a string where boxes contain '0' or '1' as characters, not integers. Comparing boxes[i] == 1 instead of boxes[i] == '1' will always evaluate to false in most languages, causing the algorithm to miss all balls.

Incorrect Order of Operations in Two-Pass

In the optimal prefix sum approach, the order of updating balls, moves, and res[i] matters. Adding the current ball before calculating the result will cause off-by-one errors where the ball at position i incorrectly contributes to its own cost.

Off-by-One in Left/Right Contribution Formula

When using the formula i * leftCount - leftSum for left contribution, using i + 1 or indexing errors in prefix arrays can shift all calculations. Carefully verify that prefix arrays are 0-indexed or 1-indexed and adjust formulas accordingly.