Minimum Operations to Move All Balls: Prefix Sum Pattern

LeetCode 1769, Minimum Number of Operations to Move All Balls to Each Box, is a medium problem that looks simple on the surface but hides a clean optimization. The brute force is obvious. The real question is whether you can spot the pattern that drops you from O(n^2) to O(n).

The problem

You are given a binary string boxes where boxes[i] is '0' or '1'. A '1' means there is a ball in box i, and a '0' means that box is empty. Return an array answer where answer[i] is the minimum number of operations needed to move all the balls to box i. Each operation moves a ball one position to the left or right.

For example, given boxes = "110010", the balls sit at positions 0, 1, and 4. To move everything to position 5, you need 5 + 4 + 1 = 10 operations.

Why this problem matters

This problem is a gateway to the prefix sum family. It teaches you to recognize when you are recomputing nearly identical sums at neighboring positions and shows how to carry forward the work from the previous position instead. That same idea powers dozens of harder problems.

Interviewers like it because the brute force is easy to write, so the conversation quickly moves to optimization, which is where the interesting thinking happens.

The key insight

The brute force computes answer[i] independently for every position. For each box, you loop through every ball and sum up the distances. That is O(n) per position and O(n^2) overall.

But notice what happens when you shift your attention from position i to position i + 1. Every ball to your left is now one step further away, so each of those balls adds one extra move. That means the total cost from the left increases by exactly the number of balls you have already passed.

You can capture this with two passes:

1. Left-to-right pass: maintain a running count of balls seen so far and a running cost. At each position, add the running cost to answer[i]. Then update: balls += boxes[i] and moves += balls. When you step right, every ball behind you costs one more, so moves goes up by balls.

2. Right-to-left pass: do the same thing in reverse. This picks up the contribution of balls to the right of each position.

After both passes, answer[i] holds the total cost from all balls, left and right.

The solution

def min_operations(boxes: str) -> list[int]:
    n = len(boxes)
    answer = [0] * n

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

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

    return answer

Each pass walks through the array once, doing constant work per element. The two passes are independent and additive: the left-to-right pass fills in the cost of gathering balls from the left, and the right-to-left pass adds the cost of gathering balls from the right.

The trick is the order inside each loop. You add moves to answer[i] before updating balls and moves. That way, the ball at position i itself does not contribute to its own cost (it is already at i, so it costs nothing). If you updated balls first, you would overcount.

Visual walkthrough

Let's trace through boxes = "110010" step by step.

Complexity analysis

Time: O(n). Two passes, each doing O(1) work per element.

Space: O(1) extra. Only two variables (balls and moves) beyond the output array. The output itself does not count as extra space.

The building blocks

This problem is built on two fundamental bricks that show up across many LeetCode problems.

Two-pass forward-backward

The core technique: make one pass accumulating state from the left, then another from the right. At each position the combination of both passes gives the full picture. You see this same structure in:

• Product of Array Except Self (prefix and suffix products)
• Trapping Rain Water (prefix and suffix maximums)
• Candy (left-to-right and right-to-left neighbor comparisons)

The reason it works is that some problems need information from both directions, but you can separate the two directions into independent passes.

Incremental cost update

Instead of recomputing the cost at each position from scratch, you derive the next answer from the previous one. Moving one step to the right increases the distance from every ball on the left by 1, so the cost goes up by the count of those balls. This is the same idea behind prefix sums: store a running total and update it in O(1) instead of recalculating in O(n).

Edge cases

• All zeros: no balls at all. Every entry in answer is 0. Both passes contribute nothing.
• All ones: every box has a ball. The algorithm handles it naturally without special logic.
• Single element: boxes = "1" or boxes = "0". The answer is [0] either way.
• Ball at one end: boxes = "10000". The left pass alone captures the entire cost. The right pass adds zeros.

From understanding to recall

You have seen the two-pass trick, and it makes sense. But in an interview two weeks from now, would you remember the exact loop structure? The detail that matters is: add moves to answer[i] before updating balls and moves. That ordering is easy to forget if you only read it once.

The forward-backward two-pass is one of roughly 60 reusable building blocks that appear across hundreds of LeetCode problems. If you drill the brick itself, not just one problem that uses it, you build permanent recall. Then when you see a new problem that asks for "the cost at every position," you do not start from zero. You reach for the brick.

Related posts

• Product of Array Except Self - The same two-pass forward-backward pattern, applied to prefix and suffix products instead of sums
• Trapping Rain Water - Forward-backward passes tracking running maximums to compute water at each position
• Maximum Subarray - Another problem where carrying forward a running value (Kadane's algorithm) replaces brute-force recomputation

CodeBricks breaks problems like this into reusable building blocks and drills them with spaced repetition, so you remember the pattern when it counts. If you want to move past "I understood it once" and into "I can write it cold," give it a try.