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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
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'.

Similar Problems

Product of Array Except Self Trapping Rain Water

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive

The naive way will be for each box at index i in the string boxes, we calculate its distance to box at index j , if boxes[j] has a ball, i.e. boxes[j] == 1, and sum up all the distances.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

 class Solution {
     public int[] minOperations(String boxes) {
         int n = boxes.length();
         int[] ans = new int[n];
         for (int i = 0; i < n; i++) {
             int res = 0;
             for (int j = 0; j < n; j++) {
                 if (boxes.charAt(j) == '1') {
                     res += Math.abs(i - j);
                 }
             }
             ans[i] = res;
         }
         return ans;
     }
 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n
        for i in range(n):
            res = 0
            for j in range(n):
                if boxes[j] == '1':
                    res += abs(i - j)
            ans[i] = res
        return ans

Complexity

  • ⏰ Time complexity: O(n^2) due to nested loop
  • 🧺 Space complexity: O(1)

Method 2 - Using Prefix Sum

  1. *Initial Observations
    • For each box, the number of operations to bring all balls to it is the sum of distances from all other boxes containing balls.
    • To directly calculate the distances, we can precompute the results using prefix sums.
  2. Forward Pass
    • Traverse from left to right, maintaining the number of balls seen so far and the total distance needed to bring these balls to the current box.
    • Use a cumulative sum to store distances.
  3. Backward Pass
    • Traverse from right to left, maintaining the same information, updating the distances similarly.
  4. Result Combination
    • Combine results from the forward and backward passes to get the minimum operations for each box.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public int[] minOperations(String boxes) {
        int n = boxes.length();
        int[] ans = new int[n];
        int balls = 0, ops = 0;
        
        // Forward pass
        for (int i = 0; i < n; i++) {
            ans[i] += ops;
            balls += boxes.charAt(i) - '0';
            ops += balls;
        }
        
        balls = 0; ops = 0;
        
        // Backward pass
        for (int i = n - 1; i >= 0; i--) {
            ans[i] += ops;
            balls += boxes.charAt(i) - '0';
            ops += balls;
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        ans = [0] * n
        balls = 0
        ops = 0
        
        # Forward pass
        for i in range(n):
            ans[i] += ops
            balls += int(boxes[i])
            ops += balls
        
        balls = 0
        ops = 0
        
        # Backward pass
        for i in range(n-1, -1, -1):
            ans[i] += ops
            balls += int(boxes[i])
            ops += balls
        
        return ans

Complexity

  • ⏰ Time complexity:  O(n) because we traverse the list twice.
  • 🧺 Space complexity: O(n) to store the answer