Logo

dev-resources.site

for different kinds of informations.

Min no. of operations to move all balls to each box

Published at
1/6/2025
Categories
Author
Prashant Mishra
Categories
1 categories in total
open
Min no. of operations to move all balls to each box

Problem
This is similar to Product of array except self

TC: O(n) ,SC:O(n)

# this is same as product of subarray except self
class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        res = [0]*len(boxes)
        # intialize balls and moves going from left to right
        balls,moves = 0,0
        for i in range(len(boxes)):
            res[i] = balls+moves
            moves = balls+moves # moves should be updated before the no. of balls are updated, because this tell us the no of moves it took to mvoe all the ball to the current index
            balls+= int(boxes[i]) # once the moves are updated we an then updated no. of balls if the current index value is also 1

        balls,moves = 0,0 # reinitialize them now going from right to left
        for i in reversed(range(len(boxes))):
            res[i]+= balls+moves # this time we just need to add the values intead of overriding as we have already calculated moves from left and from right we will just add to the existing moves present
            moves = balls+moves
            balls += int(boxes[i])
        return res


Featured ones: