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.
- Difficulty: Medium
- Topics: Arrays, Strings, Greedy, Prefix Sum
- Asked at: Amazon, Google, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.length1 <= n <= 2000boxes[i] is '0' or '1'
Hints for Minimum Number of Operations to Move All Balls to Each Box
Hint 1
The
O(n²)double loop is the obvious answer; the trick is to do it in two linear passes.Hint 2
Moving from box
ito boxi+1costs one more operation per ball on the left and one less per ball on the right.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
- Left pass: keep
cnt, the balls seen so far, andops, their total distance to the current index. Addopstoout[i], then updatecntandops += cnt. - Right pass: the same, walking backwards.
- 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
opsfor the current box before folding this box's own ball intocnt. - The two passes must be added, not combined into one sweep.
- The total reaches about
2000²/4 = 10^6, comfortably insideint.
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 outJava
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.