Minimum Number of Operations to Move All Balls to Each Box

How it works

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.

Steps

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.

Complexity

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

Things to watch for

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.

from typing import List

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

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

        int balls = 0, moves = 0;
        for (int i = 0; i < n; i++) {
            res[i] = balls + moves;
            moves += balls;
            balls += boxes[i] - '0';
        }

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

        return res;
    }
};