Minimum Number of Operations to Move All Balls to Each Box

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

Understanding the Visualization

Input

Binary string representing boxes with balls

Process

Calculate minimum operations to move all balls to each position

Output

Array of operation counts for each position

Key Takeaway

🎯 Key Insight: Use two passes to calculate left and right ball contributions separately, avoiding redundant distance calculations

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

Approach	Time	Space	Notes
✓ Two-Pass Prefix Sum	O(n)	O(1)	Use two passes to calculate left and right contributions separately
Brute Force	O(n²)	O(1)	For each position, calculate distance to every ball and sum them up

Two-Pass Prefix Sum — Algorithm Steps

First pass: calculate contributions from left balls
Second pass: add contributions from right balls
Combine both contributions for final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Left Pass

Count balls seen so far from left, add to result

Right Pass

Count balls seen so far from right, add to result

Final Result

Sum of left and right contributions

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*)calloc(n, sizeof(int));
    *returnSize = n;
    
    // Left pass: calculate contribution from balls on the left
    int ballsCount = 0;
    for (int i = 0; i < n; i++) {
        result[i] += ballsCount;
        if (boxes[i] == '1') {
            ballsCount++;
        }
    }
    
    // Right pass: add contribution from balls on the right
    ballsCount = 0;
    for (int i = n - 1; i >= 0; i--) {
        result[i] += ballsCount;
        if (boxes[i] == '1') {
            ballsCount++;
        }
    }
    
    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)

Two single passes through the array, each O(n)

✓ Linear Growth

Space Complexity

O(1)

Only using variables for running totals, 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Prefix Sum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler