A string boxes consisted by 0 and 1.
There is only one kind of operation, which is move 1 ball from a box to it's neibhbors, either left or right.
We are asked to calculate the minimum number of operations to move all balls to each box.
One fact is that, the best way to move all balls to one box is that, for each operation, we only move the ball to the target direction. So no matter which ball we move first, the total number of operations would be the same, which is the sum of distance of all balls between the target box.
So the overall time complexity is square, O(boxes.length ** 2).
Since we are given that 1 <= boxes.length <= 2000. So the overall operations is 4,000,000, which means this is a valid solution.
If the problem happens in a Weekly Contest, we would use the previous simple solution. But there could be a faster solution which is shown in the below code, and this solution is currently the fastest python solution.
This solution is an improvement of previous solution, so at least get the idea of previous solution before continue reading.
One hit point of this solution is that, in the problem, for each box, we need to calculate the minimum number of operations. We could use a variable to reduce the calculation.
Just like the previous solution, we will go through each box one by one. But Here I uses 2 variables, balls is the number of balls before box i, operations is the number of operations to move these previous balls to the box i.
Each time, before we handle box i + 1, we maintain these 2 variables. The balls is simple to maintain, we just need to add 1 if there is a ball in current box. To maintain operations, we add the number of balls to the operations. This is because all the previous balls would need 1 more operation to be able to move from box i to box i + 1.
This solution is really fast, since we only have one loop (no inner loop anymore), the time complexity is O(boxes.length).
class Solution:
def minOperations(self, boxes: str) -> List[int]:
balls = 0
operations = 0
min_operations = [0] * len(boxes)
for i, v in enumerate(boxes):
min_operations[i] += operations
if v == '1':
balls += 1
operations += balls
balls = 0
operations = 0
for i in range(len(boxes) - 1, -1, -1):
v = boxes[i]
min_operations[i] += operations
if v == '1':
balls += 1
operations += balls
return min_operations