#1769
Minimum Number of Operations to Move All Balls to Each Box
MediumArrayStringPrefix SumPrefix SumTwo Pass Technique
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(1) | O(n) |
💡
Intuition
Time O(n)Space O(n)
The optimal solution uses a single pass to calculate the number of operations needed to move all balls to each box. By maintaining a running total of moves and the number of balls seen so far, we can efficiently compute the result in linear time.
⚙️
Algorithm
3 steps- 1Step 1: Initialize an array to store the result and variables to track the total moves and the number of balls seen so far.
- 2Step 2: First pass from left to right to calculate moves for each box, updating the total moves and number of balls as you go.
- 3Step 3: Second pass from right to left to adjust the moves based on balls moving from the right side.
solution.py18 lines
1def minOperations(boxes):
2 n = len(boxes)
3 result = [0] * n
4 moves = 0
5 balls = 0
6 for i in range(n):
7 result[i] += moves
8 if boxes[i] == '1':
9 balls += 1
10 moves += balls
11 moves = 0
12 balls = 0
13 for i in range(n-1, -1, -1):
14 result[i] += moves
15 if boxes[i] == '1':
16 balls += 1
17 moves += balls
18 return resultℹ
Complexity note: This complexity is linear because we only traverse the boxes twice, once from left to right and once from right to left.
- 1Understanding how to calculate distances efficiently is crucial.
- 2Using two passes can often simplify problems that seem complex at first.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.