Minimum Number of Operations to Move All Balls to Each Box solution and explanation
Google
9 more videos on this problem
Minimum Number of Operations to Move All Balls to Each Box - Leetcode 1769 - PythonNeetCodeIO · 17:51 · 15K views
Minimum Number of Operations to Move All Balls to Each Box | Leetcode 1769 | 3 Approaches | MIKcodestorywithMIK · 46:07 · 10K views
Minimum Number of Operations to Move All Balls to Each Box | Leetcode 1769Techdose · 17:53 · 6K views
1769. Minimum Number of Operations to Move All Balls to Each Box | leetcode daily challenge | dsaShashCode · 16:29 · 2K views
@LeetCode 1769 - Minimum Number of Operations to Move All Balls to Each BoxAlgoWizard · 12:33 · 2K views
1769. Minimum Number of Operations to Move All Balls to Each Box | Prefix & Suffix SumsAryan Mittal · 19:12 · 2K views
Leetcode Solution - 1769 Minimum Number of Operations to Move All Balls to Each BoxJohn Leonardo · 5:37 · 1K views
1769. Minimum Number of Operations to Move All Balls to Each Box (Leetcode Medium)Programming Live with Larry · 8:00 · 1K views
Daily Leetcode #1742: Jan 06, 2025 - 1769. Minimum Number of Operations to Move All Balls to Each..Programming Live with Larry · 5:00 · 388 views
Minimum Number of Operations to Move All Balls to Each Box - Leetcode 1769 - JavaCode With K5KC · 11:07 · 214 views
The 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.
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.
def minOperations(boxes: str) -> list:
n = len(boxes)
result = [0] * n
for i in range(n):
for j in range(n):
if boxes[j] == '1':
result[i] += abs(j - i)
return result
print(minOperations('110'))class Solution {
public int[] minOperations(String boxes) {
int n = boxes.length();
int[] result = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (boxes.charAt(j) == '1') {
result[i] += Math.abs(j - i);
}
}
}
return result;
}
}#include <vector>
#include <string>
#include <cmath>
std::vector<int> minOperations(std::string boxes) {
int n = boxes.size();
std::vector<int> result(n, 0);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (boxes[j] == '1') {
result[i] += abs(j - i);
}
}
}
return result;
}var minOperations = function(boxes) {
const n = boxes.length;
const result = Array(n).fill(0);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (boxes[j] === '1') {
result[i] += Math.abs(j - i);
}
}
}
return result;
};
console.log(minOperations("110"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* minOperations(char *boxes, int* returnSize) {
int n = strlen(boxes);
int* result = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
int operations = 0;
for (int j = 0; j < n; j++) {
if (boxes[j] == '1') {
operations += abs(j - i);
}
}
result[i] = operations;
}
*returnSize = n;
return result;
}
int main() {
char boxes[] = "110";
int returnSize;
int* result = minOperations(boxes, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}public class Solution {
public int[] MinOperations(string boxes) {
int n = boxes.Length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (boxes[j] == '1') {
result[i] += Math.Abs(j - i);
}
}
}
return result;
}
}This Python implementation uses list indexing to calculate the operations needed for each possible target box by checking all other boxes for balls.
Time Complexity: O(n^2) as the inner loop runs n times for each outer loop iteration.
Space Complexity: O(n) used to return the result array.
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.
def minOperations(boxes: str) -> list:
n = len(boxes)
result = [0] * n
moves = 0
balls = 0
for i in range(n):
result[i] = moves
balls += boxes[i] == '1'
moves += balls
moves = 0
balls = 0
for i in range(n-1, -1, -1):
result[i] += moves
balls += boxes[i] == '1'
moves += balls
return result
print(minOperations('110'))class Solution {
public int[] minOperations(String boxes) {
int n = boxes.length();
int[] result = new int[n];
int moves = 0, balls = 0;
for (int i = 0; i < n; i++) {
result[i] = moves;
balls += boxes.charAt(i) == '1' ? 1 : 0;
moves += balls;
}
moves = 0; balls = 0;
for (int i = n - 1; i >= 0; i--) {
result[i] += moves;
balls += boxes.charAt(i) == '1' ? 1 : 0;
moves += balls;
}
return result;
}
}#include <vector>
#include <string>
std::vector<int> minOperations(std::string boxes) {
int n = boxes.size();
std::vector<int> result(n, 0);
int moves = 0, balls = 0;
for (int i = 0; i < n; ++i) {
result[i] = moves;
balls += boxes[i] == '1';
moves += balls;
}
moves = 0; balls = 0;
for (int i = n - 1; i >= 0; --i) {
result[i] += moves;
balls += boxes[i] == '1';
moves += balls;
}
return result;
}var minOperations = function(boxes) {
const n = boxes.length;
const result = Array(n).fill(0);
let moves = 0, balls = 0;
for (let i = 0; i < n; i++) {
result[i] = moves;
balls += boxes[i] === '1' ? 1 : 0;
moves += balls;
}
moves = 0; balls = 0;
for (let i = n - 1; i >= 0; i--) {
result[i] += moves;
balls += boxes[i] === '1' ? 1 : 0;
moves += balls;
}
return result;
};
console.log(minOperations("110"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int* minOperations(char *boxes, int* returnSize) {
int n = strlen(boxes);
int* result = (int*)malloc(n * sizeof(int));
int moves = 0, balls = 0;
for (int i = 0; i < n; i++) {
result[i] = moves;
balls += boxes[i] == '1';
moves += balls;
}
moves = 0; balls = 0;
for (int i = n - 1; i >= 0; i--) {
result[i] += moves;
balls += boxes[i] == '1';
moves += balls;
}
*returnSize = n;
return result;
}
int main() {
char boxes[] = "110";
int returnSize;
int* result = minOperations(boxes, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}public class Solution {
public int[] MinOperations(string boxes) {
int n = boxes.Length;
int[] result = new int[n];
int moves = 0, balls = 0;
for (int i = 0; i < n; i++) {
result[i] = moves;
balls += boxes[i] == '1' ? 1 : 0;
moves += balls;
}
moves = 0; balls = 0;
for (int i = n - 1; i >= 0; i--) {
result[i] += moves;
balls += boxes[i] == '1' ? 1 : 0;
moves += balls;
}
return result;
}
}This Python implementation of the linear approach leverages two traversals and aggregates operations both right and left, updating result indices along the way with calculated move counts.
Time Complexity: O(n) through two separate passes.
Space Complexity: O(n) to maintain the output results.
Approach 3: Default Approach
function minOperations(boxes: string): number[] {
const n = boxes.length;
const left = new Array(n).fill(0);
const right = new Array(n).fill(0);
for (let i = 1, count = 0; i < n; i++) {
if (boxes[i - 1] == '1') {
count++;
}
left[i] = left[i - 1] + count;
}
for (let i = n - 2, count = 0; i >= 0; i--) {
if (boxes[i + 1] == '1') {
count++;
}
right[i] = right[i + 1] + count;
}
return left.map((v, i) => v + right[i]);
}func minOperations(boxes string) []int {
n := len(boxes)
left := make([]int, n)
right := make([]int, n)
for i, cnt := 1, 0; i < n; i++ {
if boxes[i-1] == '1' {
cnt++
}
left[i] = left[i-1] + cnt
}
for i, cnt := n-2, 0; i >= 0; i-- {
if boxes[i+1] == '1' {
cnt++
}
right[i] = right[i+1] + cnt
}
ans := make([]int, n)
for i := range ans {
ans[i] = left[i] + right[i]
}
return ans
}impl Solution {
pub fn min_operations(boxes: String) -> Vec<i32> {
let s = boxes.as_bytes();
let n = s.len();
let mut left = vec![0; n];
let mut right = vec![0; n];
let mut count = 0;
for i in 1..n {
if s[i - 1] == b'1' {
count += 1;
}
left[i] = left[i - 1] + count;
}
count = 0;
for i in (0..n - 1).rev() {
if s[i + 1] == b'1' {
count += 1;
}
right[i] = right[i + 1] + count;
}
(0..n).into_iter().map(|i| left[i] + right[i]).collect()
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) as the inner loop runs n times for each outer loop iteration. |
| Optimized Linear Pass | Time Complexity: O(n) through two separate passes. |
| Default Approach | – |
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 |
Frequently asked questions
Is Minimum Number of Operations to Move All Balls to Each Box easy or hard?
The problem is rated Medium on LeetCode. The brute force idea is straightforward, but recognizing the prefix accumulation pattern required to reduce the complexity to O(n) is the key challenge.
Minimum Number of Operations to Move All Balls to Each Box Python/Java solution
Python and Java implementations typically follow the two-pass strategy. Maintain variables for the number of balls seen and current operation cost, update the result array during a left pass, then repeat from the right. This keeps the runtime O(n) and space O(1) aside from the output array.
How to solve Minimum Number of Operations to Move All Balls to Each Box in O(n)?
Use a two-pass prefix accumulation strategy. First scan from left to right while tracking how many balls have appeared and the operations required so far. Then scan from right to left and add the cost from balls on the right side. Combining both passes produces the total operations for every index in linear time.
What is the best approach for Minimum Number of Operations to Move All Balls to Each Box?
The optimal approach uses two linear passes with running ball counts and accumulated movement cost. While scanning left to right and right to left, each step updates the total operations based on how many balls have already been seen. This avoids recomputing distances for every box and achieves O(n) time complexity with O(1) extra space.
Is Minimum Number of Operations to Move All Balls to Each Box asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving prefix accumulation and array traversal. Variations of distance aggregation and prefix-based counting appear frequently in interviews at companies like Amazon, Google, and Meta, especially in medium-level array problems.
What data structure is used in Minimum Number of Operations to Move All Balls to Each Box?
The problem primarily uses arrays for storing the resulting operation counts and simple counters for tracking ball frequency during traversal. Conceptually it relies on prefix-style accumulation rather than advanced data structures.
What is the time complexity of Minimum Number of Operations to Move All Balls to Each Box?
The optimal solution runs in O(n) time because it processes the string twice using two linear passes. Each character is visited a constant number of times while maintaining running counts. The brute force approach takes O(n²) time since it recalculates distances for every box.