Minimum Number of Operations to Move All Balls to Each Box

medium prefix sum two passes

Problem

There are n boxes in a row, described by a binary string boxes: boxes[i] is '1' if box i starts with exactly one ball and '0' if it is empty. One operation moves a single ball from its box into an adjacent box (one step left or right).

For every index i, compute the minimum number of operations needed to bring all the balls into box i, with each computation restarting from the original configuration. Return the n results as an array.

Inputboxes = "110"

Output[1, 1, 3]

Gathering both balls into box 0 takes 1 move (the ball in box 1 steps left); box 1 likewise takes 1; box 2 needs 2 + 1 = 3 moves.

boxes (binary string, '1' = box has a ball)

def min_operations(boxes):
    n = len(boxes)
    answer = [0] * n
    balls = ops = 0
    for i in range(n):
        answer[i] += ops
        balls += int(boxes[i])
        ops += balls
    balls = ops = 0
    for i in range(n - 1, -1, -1):
        answer[i] += ops
        balls += int(boxes[i])
        ops += balls
    return answer

function minOperations(boxes) {
  const n = boxes.length;
  const answer = new Array(n).fill(0);
  let balls = 0, ops = 0;
  for (let i = 0; i < n; i++) {
    answer[i] += ops;
    balls += boxes[i] === "1" ? 1 : 0;
    ops += balls;
  }
  balls = 0; ops = 0;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] += ops;
    balls += boxes[i] === "1" ? 1 : 0;
    ops += balls;
  }
  return answer;
}

int[] minOperations(String boxes) {
    int n = boxes.length();
    int[] answer = new int[n];
    int balls = 0, ops = 0;
    for (int i = 0; i < n; i++) {
        answer[i] += ops;
        balls += boxes.charAt(i) - '0';
        ops += balls;
    }
    balls = 0; ops = 0;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] += ops;
        balls += boxes.charAt(i) - '0';
        ops += balls;
    }
    return answer;
}

vector<int> minOperations(string boxes) {
    int n = boxes.size();
    vector<int> answer(n, 0);
    int balls = 0, ops = 0;
    for (int i = 0; i < n; i++) {
        answer[i] += ops;
        balls += boxes[i] - '0';
        ops += balls;
    }
    balls = 0; ops = 0;
    for (int i = n - 1; i >= 0; i--) {
        answer[i] += ops;
        balls += boxes[i] - '0';
        ops += balls;
    }
    return answer;
}

Explanation

The brute force checks every target box against every ball, summing distances |i − j| — that is O(n²). The key insight is that a target's total cost splits cleanly into a left part (balls to its left) and a right part (balls to its right), and each part can be accumulated incrementally with one linear sweep, like a running prefix sum of ball counts.

In the left-to-right pass we carry two numbers: balls, how many balls live at indices ≤ i, and ops, the total moves needed to drag all of those balls to the current box. At each box we first deposit the carried cost into answer[i], then absorb the current box's ball into balls, then do ops += balls — because shifting the gathering point one step right costs exactly one extra move per carried ball.

The right-to-left pass is the mirror image: reset both carries to zero and sweep from the last box down to the first, adding the cost of balls arriving from the right. Each answer[i] ends up as left cost + right cost, which is exactly the full gathering cost for box i.

Walk through boxes = "110". Left pass deposits [0, 1, 3]: box 0 gets 0, box 1 gets 1 (the ball at 0 walked one step), box 2 gets 3 (the balls at 0 and 1 walked 2 + 1 steps). The right pass deposits [1, 0, 0]: only box 0 has anything to its right (the ball at index 1). Summing gives [1, 1, 3].

Why is the deposited value correct? When the left pass reaches index i, ops has grown by balls(≤ k) once for every k < i, which telescopes to the sum of (i − j) over every ball position j < i — precisely the minimum moves from the left side. The symmetric argument covers the right side, and since each ball moves independently, the two sweeps together give the optimal total.

Both passes touch each box once and keep only two counters, so the algorithm runs in O(n) time with O(1) extra space beyond the output array.

Time: O(n) Space: O(1) extra