RTL + LTR explanation | Python 3 | 100%
I was having some trouble grasping the idea of doing two traversals, and I wrote down it in a way that helped me understand. Perhaps it might help some of you a
I was having some trouble grasping the idea of doing two traversals, and I wrote down it in a way that helped me understand. Perhaps it might help some of you as well.\n\nFor any element `i`, the left-to-right traversal will provide the number of operations needed to move all the balls in `0..i` to the `i`\'th box. Similarly, the right-to-left traversal provides us the number of operations needed to move the balls in `i+1..n` range. Summing these two up, we get the total number of operations for `i`.\n\nTo calculate the LTR/RTL sum, we keep track of the number of balls encountered thus far. Let\'s call this variable `ctr`. For every array index traversed, we increment the number of operations needed by `ctr`, because we need **one operation each** to move those balls from `i-1` to `i` and we have encountered `ctr` such balls so far. To keep track of the number of operations for each `i`, we use an array.\n\n```\nclass Solution:\n    def minOperations(self, boxes: str) -> List[int]:\n        operations = 0\n        ctr = 0\n        answer = [0]*len(boxes)\n        for i in range(len(boxes)):\n            operations += ctr\n            if boxes[i] == "1":\n                ctr += 1\n            answer[i] += operations\n        operations = 0\n        ctr = 0\n        for i in range(len(boxes)-1, -1, -1):\n            operations += ctr\n            if boxes[i] == "1":\n                ctr += 1\n            answer[i] += operations\n        return answer\n```
[]