Watch 10 video solutions for Minimum Number of Operations to Move All Balls to Each Box, a medium level problem involving Array, String, Prefix Sum. This walkthrough by NeetCodeIO has 15,099 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: boxes = "110" Output: [1,1,3] Explanation: The answer for each box is as follows: 1) First box: you will have to move one ball from the second box to the first box in one operation. 2) Second box: you will have to move one ball from the first box to the second box in one operation. 3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.
Example 2:
Input: boxes = "001011" Output: [11,8,5,4,3,4]
Constraints:
n == boxes.length1 <= n <= 2000boxes[i] is either '0' or '1'.Problem Overview: You receive a binary string where '1' represents a box containing a ball and '0' represents an empty box. For every index, compute how many operations are required to move all balls to that box. Moving a ball from index i to j costs |i - j| operations.
Approach 1: Brute Force Simulation (O(n²) time, O(1) space)
Iterate through every box as the destination. For each destination index i, scan the entire string again and add the distance from every box containing a ball. The operation count increases by |i - j| whenever boxes[j] == '1'. This approach directly models the problem definition, which makes it easy to reason about. However, it performs a full scan for every position, leading to quadratic time complexity. It works fine for small inputs but becomes inefficient for large strings.
Approach 2: Optimized Linear Pass with Prefix Counts (O(n) time, O(1) space)
The key observation: instead of recomputing distances from scratch for each box, you can accumulate the movement cost while scanning from left to right and then right to left. Maintain two running values: the number of balls seen so far and the total operations needed to move them to the current index. During the left pass, each step adds the number of balls encountered because each of them must move one extra step to reach the next index. Repeat the same logic from right to left and add the results together.
This effectively builds a prefix-style accumulation where the movement cost grows incrementally as you traverse the array. You avoid repeated distance calculations and reduce the runtime to linear complexity. The algorithm only keeps a few counters, so the space complexity remains constant.
The technique resembles ideas used in array traversal and cumulative counting similar to prefix sum patterns. Even though the input is a string, treating it as an indexed sequence simplifies the computation.
Recommended for interviews: Interviewers expect the linear two-pass solution. The brute force approach demonstrates that you understand the cost model of the problem, but the optimized prefix accumulation shows algorithmic maturity. Recognizing that distance costs can be updated incrementally is the core insight that reduces the time complexity from O(n²) to O(n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | When constraints are small or when demonstrating the straightforward interpretation of the problem |
| Two-Pass Prefix Accumulation | O(n) | O(1) | Best for interviews and production solutions where linear performance is required |