Minimum Number of Operations to Move All Balls to Each Box

Intuition

Analysis Problem Description

Input

A string boxes consisted by 0 and 1.

Limitation

There is only one kind of operation, which is move 1 ball from a box to it's neibhbors, either left or right.

Output

We are asked to calculate the minimum number of operations to move all balls to each box.

Basic Greedy Solution

Idea

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.

Time Complexity

In the outer loop, we need to go through each box and calculate the minimum number of operations for that box. The time complexity of this operation is O(boxes.length).
For each box, to calculate the minimum number of operations to move all balls to it, we need to go through all boxes with ball in it, and calculate the distance between the ball and the target box. The time complexity of this operation is O(boxes.length).

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.

Advanced DP 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.

Idea

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.

Time Complexity

This solution is really fast, since we only have one loop (no inner loop anymore), the time complexity is O(boxes.length).

Solution


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