Problem Statement
Brute Force [accepted]
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
res = [0] * n
for i in range(n):
for l in range(i - 1, -1, -1):
if boxes[l] == '1':
res[i] += (i - l)
for r in range(i + 1, n):
if boxes[r] == '1':
res[i] += (r - i)
return res
Improved Algorithm
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
res = [0] * n
indices = set()
for i in range(n):
if boxes[i] == '1':
indices.add(i)
for i in range(n):
for j in indices:
res[i] += abs(i - j)
return res
Editorial
Approach 1: Brute Force
class Solution:
def minOperations(self, boxes: str) -> List[int]:
answer = [0] * len(boxes)
for current_box in range(len(boxes)):
# If the current box contains a ball, calculate the number of moves for every box.
if boxes[current_box] == "1":
for new_position in range(len(boxes)):
answer[new_position] += abs(new_position - current_box)
return answer
Approach 2: Sum of Left and Right Moves
class Solution:
def minOperations(self, boxes: str) -> List[int]:
n = len(boxes)
answer = [0] * n
balls_to_left = 0
moves_to_left = 0
balls_to_right = 0
moves_to_right = 0
# Single pass: calculate moves from both left and right
for i in range(n):
# Left pass
answer[i] += moves_to_left
balls_to_left += int(boxes[i])
moves_to_left += balls_to_left
# Right pass
j = n - 1 - i
answer[j] += moves_to_right
balls_to_right += int(boxes[j])
moves_to_right += balls_to_right
return answer
