Minimum Number of Operations to Move All Balls to Each Box

Medium
843.

Minimum Number of Operations to Move All Balls to Each Box

Minimum Number of Operations to Move All Balls to Each Box is a medium coding problem on arrays, strings and greedy, asked in Amazon, Google and Wipro interviews.

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'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} boxes
 * @return {number[]}
 */
var minOperations = function(boxes) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Operations to Move All Balls to Each Box Solution

Minimum Number of Operations to Move All Balls to Each Box solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Operations to Move All Balls to Each Box is a medium coding problem on arrays, strings and greedy, asked in Amazon, Google and Wipro interviews.

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'

Hints for Minimum Number of Operations to Move All Balls to Each Box

  1. Hint 1

    The O(n²) double loop is the obvious answer; the trick is to do it in two linear passes.

  2. Hint 2

    Moving from box i to box i+1 costs one more operation per ball on the left and one less per ball on the right.

  3. Hint 3

    Sweep left to right accumulating the cost of the balls behind you, then right to left for the balls ahead.

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

  1. 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.
  2. Right pass: the same, walking backwards.
  3. 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

Java

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

C++

vector<int> minOperations(string boxes) {
    int n = (int) boxes.size();
    vector<int> out(n, 0);
    int cnt = 0, ops = 0;
    for (int i = 0; i < n; i++) {
        out[i] += ops;
        if (boxes[i] == '1') cnt++;
        ops += cnt;
    }
    cnt = 0;
    ops = 0;
    for (int i = n - 1; i >= 0; i--) {
        out[i] += ops;
        if (boxes[i] == '1') cnt++;
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings