Minimum Number of Operations to Move All Balls to Each Box - Problem

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

Input & Output

Example 1 — Basic Case

$ Input: boxes = "110"

› Output: [1,1,3]

💡 Note: For position 0: move ball from pos 1 (1 op). For position 1: move ball from pos 0 (1 op). For position 2: move balls from pos 0,1 (2+1=3 ops).

Example 2 — More Balls

$ Input: boxes = "001011"

› Output: [11,8,5,4,3,4]

💡 Note: Position 0: balls at 2,4,5 need 2+4+5=11 ops. Position 1: balls need 1+3+4=8 ops. And so on for each position.

Example 3 — Single Ball

$ Input: boxes = "1"

› Output: [0]

💡 Note: Only one box with one ball - no operations needed to move all balls to position 0.

Constraints

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

Visualization

Tap to expand

Asked in

F Facebook 15 G Google 12 a Amazon 8

The key insight is to avoid recalculating distances by using a two-pass approach. First pass accumulates contributions from balls on the left, second pass adds contributions from balls on the right. Best approach is Two-Pass Prefix Sum with Time: O(n), Space: O(1).

Common Approaches

✓ Brute Force

⏱️ Time: O(n²) Space: O(1)

For each box position i, iterate through all boxes to find balls (boxes[j] == '1') and sum the distances abs(i - j). This gives the total operations needed to move all balls to position i.

Two-Pass Prefix Sum

⏱️ Time: O(n) Space: O(1)

Instead of recalculating distances, use two passes: left-to-right to accumulate contributions from balls on the left, and right-to-left for balls on the right. Track running totals of balls and distances.

Brute Force — Algorithm Steps

For each target position i
Find all balls in the boxes
Sum distances from each ball to position i

Visualization

Tap to expand

Step-by-Step Walkthrough

Target Position

Choose a position to move all balls to

Find All Balls

Locate all positions with balls (value '1')

Sum Distances

Add up distances from each ball to target position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(char* boxes, int* returnSize) {
    int n = strlen(boxes);
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = n;
    
    for (int i = 0; i < n; i++) {
        int totalOps = 0;
        for (int j = 0; j < n; j++) {
            if (boxes[j] == '1') {
                totalOps += abs(i - j);
            }
        }
        result[i] = totalOps;
    }
    
    return result;
}

int main() {
    char boxes[100001];
    fgets(boxes, sizeof(boxes), stdin);
    boxes[strcspn(boxes, "\n")] = 0;
    
    int returnSize;
    int* result = solution(boxes, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop n positions × inner loop n boxes

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculations, output array doesn't count

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Minimum Number of Operations to Move All Balls to Each Box - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler