Minimum Number of Operations to Move All Balls to Each Box - Solution & Explanation
Problem Statement
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'.
Approach Overview
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 1: Brute Force Approach
The simplest way to solve this problem is by iterating through each box, and for each box, calculate the number of moves required to bring all balls to that box by checking every other box. For each pair of boxes (i, j), a ball present at box j needs |j - i| moves to reach box i.
This straight-forward approach has a time complexity of O(n^2) since for every position, we are traversing the list of boxes.
This solution iterates through each possible target box and, for each box, counts the required number of moves by checking each ball's current position. The operations counted for a ball at position j moving to position i is the absolute difference |j - i|.
Complexity
Time Complexity: O(n^2) because it requires traversing the entire boxes string for each target box.
Space Complexity: O(n) for storing the result.
Approach 2: Optimized Linear Pass
This approach significantly reduces redundant calculations by using prefix sums. First, make one pass from left to right to calculate the number of operations needed to bring balls to each position considering only balls to its left. Next, make another pass from right to left to factor in the balls on the right. By separating these concerns, we use prefix sums to compute the required operations in linear time.
In essence, it accumulates the number of moves by maintaining a running total of moves per box as you encounter them through the linear scan.
This C program makes two passes over the input string. In the first pass, it calculates the cost of moving balls from the left of each box, and in the second pass, it does the same for balls on the right.
Complexity
Time Complexity: O(n) because it makes two linear passes over the input.
Space Complexity: O(n) for storing the result array.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Rust
C
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) because it requires traversing the entire boxes string for each target box. |
| Optimized Linear Pass | Time Complexity: O(n) because it makes two linear passes over the input. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Minimum Number of Operations to Move All Balls to Each Box - Leetcode 1769 - Python • NeetCodeIO • 15,491 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Operations to Move All Balls to Each Box easy or hard?
Minimum Number of Operations to Move All Balls to Each Box Python/Java solution
How to solve Minimum Number of Operations to Move All Balls to Each Box in O(n)?
What is the best approach for Minimum Number of Operations to Move All Balls to Each Box?
Is Minimum Number of Operations to Move All Balls to Each Box asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Operations to Move All Balls to Each Box?
What is the time complexity of Minimum Number of Operations to Move All Balls to Each Box?
Ready to solve this problem?
Practice Minimum Number of Operations to Move All Balls to Each Box with our built-in code editor and test cases.
Practice on FleetCode