Minimum Number of Operations to Move All Balls to Each Box

Med

#1619Time: O(n^2), where `n` is the length of the `boxes` string. For each of the `n` boxes, we iterate through all `n` boxes again.Space: O(n) to store the output array. If the output array is not considered extra space, the complexity is O(1).

Patterns

Prefix Sum

Data structures

Array String

Prompt

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the i^th 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 i^th 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.length
1 <= n <= 2000
boxes[i] is either '0' or '1'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into code. For each box, we calculate the cost of moving every ball in the entire set to that specific box. This is done by iterating through all n boxes for each of the n target boxes.

Algorithm

Initialize an integer array answer of size n with all elements set to 0.
Iterate through each target box i from 0 to n-1.
For each i, initialize a variable total_ops = 0.
Start a nested loop, iterating through all boxes j from 0 to n-1.
Inside the nested loop, check if boxes.charAt(j) is '1'.
If it is, calculate the distance required to move the ball from j to i, which is Math.abs(i - j).
Add this distance to total_ops.
After the inner loop finishes, assign the accumulated total_ops to answer[i].
After the outer loop finishes, return the answer array.

Walkthrough

We create an answer array of the same size as the input string boxes. We then use a nested loop structure. The outer loop selects a target box, i. The inner loop scans the entire boxes string to find the locations of all balls. For each ball found at index j, we calculate the number of operations needed to move it to box i. Since one operation moves a ball to an adjacent box, the total operations to move a ball from j to i is simply the absolute difference of their indices, abs(i - j). We sum these costs for all balls for a given target box i and store it in answer[i]. We repeat this process for all possible target boxes.

1class Solution {2    public int[] minOperations(String boxes) {3        int n = boxes.length();4        int[] answer = new int[n];5 6        for (int i = 0; i < n; i++) {7            int currentOperations = 0;8            for (int j = 0; j < n; j++) {9                if (boxes.charAt(j) == '1') {10                    currentOperations += Math.abs(i - j);11                }12            }13            answer[i] = currentOperations;14        }15 16        return answer;17    }18}

Complexity

Time

O(n^2), where `n` is the length of the `boxes` string. For each of the `n` boxes, we iterate through all `n` boxes again.

Space

O(n) to store the output array. If the output array is not considered extra space, the complexity is O(1).

Trade-offs

Pros

Very simple and intuitive to understand.
Easy to implement correctly.

Cons

The time complexity is quadratic, which can be slow for larger inputs (though it passes within the given constraints).

A more optimal approach is to use two passes to calculate the costs. The total operations for any box i can be seen as the sum of two parts: the cost to move all balls from the left of i to i, and the cost to move all balls from the right of i to i. We can calculate these two components for all boxes efficiently in two separate linear passes, one from left-to-right and one from right-to-left.

Algorithm

The total operations for a box i is the sum of operations to move balls from its left and operations to move balls from its right.
Pass 1 (Left to Right):
- Initialize an answer array, ballsCount = 0, and operations = 0.
- Iterate i from 0 to n-1.
- For each i, all ballsCount balls seen so far are now one step further. So, add ballsCount to operations.
- Set answer[i] = operations.
- If boxes.charAt(i) is '1', increment ballsCount.
Pass 2 (Right to Left):
- Reset ballsCount = 0 and operations = 0.
- Iterate i from n-1 down to 0.
- Similar to the first pass, add ballsCount to operations.
- Add this operations value to the existing answer[i] (i.e., answer[i] += operations).
- If boxes.charAt(i) is '1', increment ballsCount.
Return the answer array.

Walkthrough

This approach avoids the redundant calculations of the brute-force method.

In the first pass (left-to-right), we calculate left_ops[i], the cost to move all balls from indices less than i to index i. We can observe that left_ops[i] = left_ops[i-1] + (number of balls to the left of i). We can maintain a running count of balls and operations. We iterate from i = 0 to n-1, updating the operations needed based on the number of balls encountered so far, and store this intermediate result in our answer array.

In the second pass (right-to-left), we do the same for right_ops[i], the cost to move balls from indices greater than i. We iterate from i = n-1 down to 0, again keeping a running count of balls and operations. We add this result to the value already in the answer array.

After both passes, answer[i] will contain the sum of left_ops[i] and right_ops[i], which is the total minimum operations.

1class Solution {2    public int[] minOperations(String boxes) {3        int n = boxes.length();4        int[] answer = new int[n];5        int ballsCount = 0;6        int operations = 0;7 8        // Pass 1: Left to Right9        // Calculate the cost to move balls from the left to the current box i10        for (int i = 0; i < n; i++) {11            operations += ballsCount;12            answer[i] = operations;13            if (boxes.charAt(i) == '1') {14                ballsCount++;15            }16        }17 18        // Pass 2: Right to Left19        // Calculate the cost to move balls from the right and add it to the previous result20        ballsCount = 0;21        operations = 0;22        for (int i = n - 1; i >= 0; i--) {23            operations += ballsCount;24            answer[i] += operations;25            if (boxes.charAt(i) == '1') {26                ballsCount++;27            }28        }29 30        return answer;31    }32}

Complexity

Time

O(n), as we perform two independent passes over the array, each taking linear time.

Space

O(n) to store the output array. The extra space used by variables is O(1).

Trade-offs

Pros

Highly efficient with a linear time complexity.
Uses constant extra space (excluding the output array).

Cons

Slightly less intuitive than the brute-force approach, as it requires understanding the relationship between the costs of adjacent boxes.

Solutions

Solution

1class Solution {2public3  int[] minOperations(String boxes) {4    int n = boxes.length();5    int[] left = new int[n];6    int[] right = new int[n];7    for (int i = 1, cnt = 0; i < n; ++i) {8      if (boxes.charAt(i - 1) == '1') {9        ++cnt;10      }11      left[i] = left[i - 1] + cnt;12    }13    for (int i = n - 2, cnt = 0; i >= 0; --i) {14      if (boxes.charAt(i + 1) == '1') {15        ++cnt;16      }17      right[i] = right[i + 1] + cnt;18    }19    int[] ans = new int[n];20    for (int i = 0; i < n; ++i) {21      ans[i] = left[i] + right[i];22    }23    return ans;24  }25}

1class Solution {2public:3  vector<int> minOperations(string boxes) {4    int n = boxes.size();5    int left[n];6    int right[n];7    memset(left, 0, sizeof left);8    memset(right, 0, sizeof right);9    for (int i = 1, cnt = 0; i < n; ++i) {10      cnt += boxes[i - 1] == '1';11      left[i] = left[i - 1] + cnt;12    }13    for (int i = n - 2, cnt = 0; ~i; --i) {14      cnt += boxes[i + 1] == '1';15      right[i] = right[i + 1] + cnt;16    }17    vector<int> ans(n);18    for (int i = 0; i < n; ++i)19      ans[i] = left[i] + right[i];20    return ans;21  }22};

1class Solution:2    def minOperations(self, boxes: str) -> List[int]: n = len(boxes) left = [0] * n right = [0] * n cnt = 0 for i in range(1, n): if boxes[i - 1] == '1': cnt += 1 left[i] = left[i - 1] + cnt cnt = 0 for i in range(n - 2, - 1, - 1): if boxes[i + 1] == '1': cnt += 1 right[i] = right[i + 1] + cnt return [a + b for a, b in zip(left, right)]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem