[Python] Simple BFS with tree cutting || Derivation/Explanation || O(NlogN)
\n# Explanation\nSame ideas as other\'s,I used the below formula for neighbour i.e\np\' = 2s + k -1 - p\nwhere :-\np\' is new index of 1\np - old index\ns - sta
\n# Explanation\nSame ideas as other\'s,I used the below formula for neighbour i.e\np\' = 2s + k -1 - p\nwhere :-\np\' is new index of 1\np - old index\ns - starting position which ranges max(0,pp-k+1),min(pp+1,n-k+1)\nk - given length\n\nIf you are finding it hard to understand where it comes from just take copy pen and do the calculations yourself!\n\nhint: you can start here, s-p=e-p\' , e = ending = p+k-1\n## Optimize \nNow to optimize, we need to realize that we are traversing visited node again and again. \nie. p\' should only be calculated when it isn\'t visited before.\n\nTo do this i mentain a ordered list so we can remove visited values of p\'.\n\n\n# Code\n```\nfrom sortedcontainers import SortedSet\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, bn: List[int], k: int) -> List[int]:\n        res = [-1]*n\n        res[p] = 0\n        no_need = [False]*n\n        no_need[p] = True\n        for i in bn: no_need[i] = True\n        q = deque() # bfs where nodes are the position of 1\n        q.append((p,0))\n        ev = SortedSet([i for i in range(0,n,2) if(not no_need[i]) ]) # important to make TC O(N)\n        od = SortedSet([i for i in range(1,n,2) if(not no_need[i]) ])\n        while(q):\n            pp,m = q.popleft()\n            left,right = max(0,pp-k+1),min(pp+1,n-k+1) # find range for starting positions of K len array containing 1\n            c = k-1-pp # constant as per the eq\n            ls = ev if (2*left+c)%2==0 else od # select the correct list\n            st = ls.bisect_left(2*left+c) # find begining position\n            end = ls.bisect_left(2*right+c) # ending position\n            sl = ls[st:end] # create a view \n            for i in sl:\n                ls.remove(i) # cut the original arr\n                res[i] = m+1\n                q.append((i,m+1))\n        return res\n```\nUpvote if you find it useful!\nThanks
['Python3']