DEV Community

Prashant Mishra
Prashant Mishra

Posted on

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 
Enter fullscreen mode Exit fullscreen mode

Top comments (0)