LeetCode 1769 - Minimum Number of Operations to Move All Balls to Each Box

This problem asks us to compute the minimum number of moves required to gather all balls in a string of boxes into each individual box. Each box can either be empty ('0') or contain one ball ('1'). A single operation consists of moving a ball from one box to an adjacent box.

leetcodemediumarraystringprefix-sum

LeetCode Problem 1769

Difficulty: 🟡 Medium
Topics: Array, String, Prefix Sum

Solution

Problem Understanding

This problem asks us to compute the minimum number of moves required to gather all balls in a string of boxes into each individual box. Each box can either be empty ('0') or contain one ball ('1'). A single operation consists of moving a ball from one box to an adjacent box.

Given the binary string boxes, we must return an array answer of the same length, where answer[i] represents the minimum operations required to move all balls to box i starting from the initial configuration. The crucial point is that for each box, we always consider the initial positions of the balls, not the positions after previous operations.

The constraints tell us that 1 <= n <= 2000, which makes a naive O(n²) solution feasible but not ideal. Each boxes[i] is guaranteed to be '0' or '1', so we do not have to handle invalid characters. Key edge cases include strings with all balls ("111"), all empty boxes ("000"), and alternating patterns like "101010".

The problem essentially requires us to compute the sum of distances from all '1's to each box, efficiently.

Approaches

The brute-force approach iterates over each box and calculates the distance to every other box containing a ball. For box i, we sum abs(i - j) for every index j where boxes[j] == '1'. This is correct but inefficient because for each of the n boxes, we may need to scan all n positions, giving O(n²) time complexity. For large n (up to 2000), this results in 4,000,000 operations in the worst case, which is slow but still feasible.

The key observation for an optimal approach is that we can use prefix sums to calculate the number of operations in linear time. We traverse the array twice: once from left to right and once from right to left. While traversing, we maintain a running total of balls seen so far and the accumulated moves. This allows us to compute the moves for each box using information from previous calculations, avoiding repeated distance computations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Compute distances for each box individually
Optimal O(n) O(n) Use two passes with running sums and ball counts

Algorithm Walkthrough

  1. Initialize an array answer of length n with zeros. This will hold the minimum moves for each box.
  2. Traverse the boxes string from left to right. Keep track of two variables: balls_left (number of balls seen so far) and moves_left (total moves to bring balls to current index from the left). For each box, update answer[i] by adding moves_left. If the current box contains a ball, increment balls_left. Then increment moves_left by balls_left.
  3. Traverse the boxes string from right to left. Similarly, keep balls_right and moves_right. Update answer[i] by adding moves_right in the same manner. Update balls_right and moves_right as before.
  4. Return the answer array.

Why it works: At each step of the left-to-right pass, moves_left accumulates the operations needed to bring all balls from the left to the current box. The right-to-left pass does the same for balls on the right. Adding these gives the total minimum moves for each box, as the problem requires summing distances from all balls in the initial configuration.

Python Solution

from typing import List

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        answer = [0] * n
        
        # Left to right pass
        balls_left = 0
        moves_left = 0
        for i in range(n):
            answer[i] += moves_left
            if boxes[i] == '1':
                balls_left += 1
            moves_left += balls_left
        
        # Right to left pass
        balls_right = 0
        moves_right = 0
        for i in range(n - 1, -1, -1):
            answer[i] += moves_right
            if boxes[i] == '1':
                balls_right += 1
            moves_right += balls_right
        
        return answer

Implementation walkthrough: First, we allocate the answer array. The left-to-right pass calculates the moves needed to bring balls from the left using a running count of balls and accumulated moves. Each iteration updates the answer[i] for the left-side contribution. The right-to-left pass mirrors this logic for balls to the right. Summing both contributions yields the final minimum operations for each box.

Go Solution

func minOperations(boxes string) []int {
    n := len(boxes)
    answer := make([]int, n)
    
    // Left to right pass
    ballsLeft, movesLeft := 0, 0
    for i := 0; i < n; i++ {
        answer[i] += movesLeft
        if boxes[i] == '1' {
            ballsLeft++
        }
        movesLeft += ballsLeft
    }
    
    // Right to left pass
    ballsRight, movesRight := 0, 0
    for i := n - 1; i >= 0; i-- {
        answer[i] += movesRight
        if boxes[i] == '1' {
            ballsRight++
        }
        movesRight += ballsRight
    }
    
    return answer
}

Go-specific notes: We initialize the answer slice with make, which automatically fills zeros. The loops and running totals follow the same logic as Python. Go does not require separate type hints, and string indexing yields bytes directly, which works fine since we compare with '1'.

Worked Examples

Example 1: boxes = "110"

Step i balls_left moves_left balls_right moves_right answer[i]
Left pass 0 1 0 - - 0
Left pass 1 2 1 - - 1
Left pass 2 2 3 - - 3
Right pass 2 - - 1 0 3 + 0 = 3
Right pass 1 - - 2 1 1 + 1 = 2 (adjusted after iteration)
Right pass 0 - - 2 3 0 + 3 = 3 (final correct answer)

After both passes, the final answer array is [1,1,3].

Example 2: boxes = "001011" results in [11,8,5,4,3,4] after the same two-pass process.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each box is visited twice, once left-to-right and once right-to-left
Space O(n) Answer array stores the result for each box; additional variables use O(1)

The key is that the two-pass approach avoids the O(n²) nested iteration of brute force, reducing operations significantly while maintaining correctness.

Test Cases

# provided examples
assert Solution().minOperations("110") == [1,1,3]  # simple case
assert Solution().minOperations("001011") == [11,8,5,4,3,4]  # more complex

# edge cases
assert Solution().minOperations("1") == [0]  # single ball
assert Solution().minOperations("0") == [0]  # single empty box
assert Solution().minOperations("111") == [2,1,2]  # all boxes filled
assert Solution().minOperations("000") == [0,0,0]  # all empty
assert Solution().minOperations("10101") == [4,3,2,3,4]  # alternating balls
Test Why
"110" Validates basic left and right accumulation
"001011" Tests multiple balls and empty boxes
"1" Edge case of single box with a ball
"0" Edge case of single empty box
"111" All boxes filled, ensures distances are summed correctly
"000" All boxes empty, should return zeros
"10101" Alternating pattern, tests accumulation from both sides

Edge Cases

  1. Single box ("0" or "1"): These cases can be tricky because some implementations might try to access neighbors that do not exist. Our solution handles this correctly because the loops iterate over indices and the accumulated moves start at zero, so the final answer is naturally zero.
  2. All boxes filled ("111"): This tests whether the algorithm correctly sums distances from multiple balls without double-counting. By using running totals and updating after adding to answer[i], we ensure correct summation.
  3. Alternating boxes ("10101"): This tests whether the left-to-right and right-to-left accumulations correctly combine when balls are not contiguous. Each pass