Minimum Number of Operations to Move All Balls to Each Box
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]Moving all balls to the first, second, and third boxes requires 1, 1, and 3 operations respectively.
Example 2
Input
boxes = "001011"Output
[11,8,5,4,3,4]For each target box in the initial state, summing the distances from all boxes containing balls gives [11, 8, 5, 4, 3, 4].
Constraints
- n == boxes.length
- 1 <= n <= 2000
- boxes[i] is either '0' or '1'.
Asked at 6 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.