Minimum Number of Operations to Move All Balls to Each Box — Medium Problem & Solution

boxes[i] is '1' if box i holds a ball and '0' if it is empty. One operation moves a single ball to an adjacent box.

Difficulty: Medium
Topics: Arrays, Strings, Greedy, Prefix Sum
Asked at: Amazon, Google, Wipro
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

boxes[i] is '1' if box i holds a ball and '0' if it is empty. One operation moves a single ball to an adjacent box.

Return an array whose i-th entry is the minimum number of operations to bring every ball into box i. The answers are computed independently — the boxes start over each time.

Example 1

Input: boxes = "110"
Output: [1,1,3]
Explanation: For box 0 the ball at index 1 moves once; for box 2 both balls move, costing 2 + 1.

Example 2

Input: boxes = "001011"
Output: [11,8,5,4,3,4]

Example 3

Input: boxes = "1"
Output: [0]

Constraints

n == boxes.length
1 <= n <= 2000
boxes[i] is '0' or '1'

How to solve Minimum Number of Operations to Move All Balls to Each Box

Split each answer into the cost from the left and the cost from the right, and compute each with one running sweep. Stepping one box further from a group of balls adds exactly one operation per ball in that group.

Approach

Left pass: keep cnt, the balls seen so far, and ops, their total distance to the current index. Add ops to out[i], then update cnt and ops += cnt.
Right pass: the same, walking backwards.
The two contributions sum to the answer for each box.

Why it works

ops is maintained as the total cost of bringing every ball at an index below i to box i. Advancing by one box adds one operation for each such ball, which is exactly cnt — so the recurrence ops += cnt after updating cnt keeps it exact. The right pass covers the balls ahead by symmetry, and the two sets are disjoint.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

The order inside the loop matters: record ops for the current box before folding this box's own ball into cnt.
The two passes must be added, not combined into one sweep.
The total reaches about 2000²/4 = 10^6, comfortably inside int.

Reference solution

Python

from typing import List

def minOperations(boxes: str) -> List[int]:
    n = len(boxes)
    out = [0] * n
    cnt = ops = 0
    for i in range(n):
        out[i] += ops
        if boxes[i] == "1":
            cnt += 1
        ops += cnt
    cnt = ops = 0
    for i in range(n - 1, -1, -1):
        out[i] += ops
        if boxes[i] == "1":
            cnt += 1
        ops += cnt
    return out

JavaScript

var minOperations = function(boxes) {
    var n = boxes.length;
    var out = [];
    for (var t = 0; t < n; t++) out.push(0);
    var cnt = 0, ops = 0, i;
    for (i = 0; i < n; i++) {
        out[i] += ops;
        if (boxes.charAt(i) === "1") cnt++;
        ops += cnt;
    }
    cnt = 0; ops = 0;
    for (i = n - 1; i >= 0; i--) {
        out[i] += ops;
        if (boxes.charAt(i) === "1") cnt++;
        ops += cnt;
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue