Python3 | BFS w/o a queue beats 100% time and memory (Index math explained)
Index math\n\nA length-$N$ list has $N-k+1$ length-$k$ slices, one starting at each $i \in [0, N-k]$.\n\nSuppose the set/on/one bit is currenlty at position $p 
# Index math\n\nA length-$N$ list has $N-k+1$ length-$k$ slices, one starting at each $i \\in [0, N-k]$.\n\nSuppose the set/on/one bit is currenlty at position $p \\in [0, N)$. Reverseing one of these slices, `bits[i:i+k]`, has no effect. if $p < i$ or $p \\geq i+k$; we should only consider reversing slices `bits[i:i+k]` s.t. $i \\leq p < i+k$. This gives us limits on $i$, the starting position of the slice: $p-k < i \\leftrightarrow p-k+1 \\leq i$ and $i \\leq p$, so $i \\in [p-k+1, p]$. Furthermore, we should make sure $0 \\leq i \\leq N-k$, so `i_lo = max(0, p-k+1)` and `i_hi = min(N-k, p)`.\n\nReversing `bits[i:i+k]` where the set bit is at position $p \\in [i, i+k]$ simply moves the set bit to posiiton $i+k-1-(p-i) = 2i+k-1-p$. Rather than iterating through the appropritate $i$s and calculating $2i+k-1-p$ for each $i$, we can just iterate throught `range(p_lo, p_hi+1, 2)` where `p_lo = 2*i_lo + k - 1 - p` and `p_hi = 2*i_hi + k - 1 - p`.\n\nSo given the position of the set bit, $p$, we can calculate the possible next positions. We do a BFS to identify all the possible positions in operations order, each time recording how many operations were necessary to reach said position.\n\n# Complexity\n- Time complexity: I think it\'s $O(N \\lg N)$.\n- Space complexity: $O(N)$\n\n# Code\n\nThis is an improvement on [awice\'s SortedList.irange soltuion](https://leetcode.com/problems/minimum-reverse-operations/solutions/3368819/python3-bfs-sortedlist-keep-track-of-remaining-nodes/).\n\n```\nIMPOSSIBLE = -1\nEVEN, ODD = 0, 1\nclass Solution:\n    def minReverseOperations(self, N: int, p: int, banned: List[int], k: int) -> List[int]:\n        if k == 1 or len(banned) == N-1:\n            numOps = [IMPOSSIBLE] * N\n            numOps[p] = 0\n            return numOps\n        \n        numOps = [IMPOSSIBLE] * N\n        numOps[p] = 0\n        \n        remaining = [[], []]\n        banned = set(banned)\n        for pos in range(0, N, 2):\n            if pos != p and pos not in banned:\n                remaining[EVEN].append(pos)\n            pos += 1\n            if pos != p and pos not in banned:\n                remaining[ODD].append(pos)\n        \n        # BFS\n        numOp = 1\n        p0s = [p]\n        while p0s:\n            p1s = []\n            for p0 in p0s:\n                i_lo = max(0, p0+1-k)\n                i_hi = min(N-k, p0)\n                p1_lo = p1_hi = k-1-p0\n                p1_lo += 2*i_lo\n                p1_hi += 2*i_hi\n                parity = p1_lo & 0b1\n                rem = remaining[parity]\n                lo = bisect_left(rem, p1_lo)\n                hi = bisect_right(rem, p1_hi)\n\n                # Alt 1\n                for j in reversed(range(lo, hi)):\n                    p1 = rem.pop(j)\n                    numOps[p1] = numOp\n                    p1s.append(p1)\n\n                # # Alt 2\n                # for _ in range(hi - lo):\n                #     p1 = rem.pop(lo)\n                #     numOps[p1] = numOp\n                #     p1s.append(p1)\n            \n            p0s = p1s\n            numOp += 1\n        \n        return numOps\n```
['Python3']