[Python3] Without The Use Of Imports
Intuition\nI didn\'t really like how every other solution I saw involved some third party packages. I wanted to write a piece of code that works with python3 ou
# Intuition\nI didn\'t really like how every other solution I saw involved some third party packages. I wanted to write a piece of code that works with python3 out of the box, no other packages or libraries.\n\n# Approach\nThe big piece I was missing was two fold:\n\n1. BFS alone is not fast enough. You need to track all elements that have not been queued yet. Since your step-width for every $$i$$ is $$2$$, it means it\'s most efficient to keep track of two lists with even and odd elements respectiveley.\n2. You shouldn\'t iterate other positions. Instead, you should iterate `lower` which is the lower bound of your reversing operation. Every reverse will flip the elements between `lower` and upper. \n\nI believe that most answers here get to the first realization so I want to expand on the second one in my own words. It\'s easy to see that the upper bound will be `lower + k - 1` for any lower and k. We now use the formular that translates a pre-flip position `i` into a post-flip `j` with `j = upper - (i - lower)` to be\n`j = 2 * lower + k - 1 - i`.\nThat was the last puzzle piece for me. With the observations above, we now need to go through all j\'s that have not previously been observed and are in the boundaries (inclusive)\n`[2 * lower_min + k - 1 - i, 2 * lower_max + k - 1 - i]`\nwhere\n`lower_min = max(0, i - k + 1)`\nand\n`lower_max = min(n - k, i)`\n\nTranslated back to plain english: Take all possible inversions, iterate over the lower index of that inversion, translate that iteration into an iteration over the new index j, and use the other observations to speed up that process by only looking at each j once.\n\n# Complexity\n- Time complexity:\nIt seems that all answers for this are $$O(n^2)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\ndef bisect_left(lst, num, lo=0, hi=None):\n    if hi is None: hi = len(lst)\n    while lo < hi:\n        mid = (lo + hi) // 2\n        if lst[mid] < num: lo = mid + 1\n        else: hi = mid\n    return lo\n\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, banned_: List[int], k: int) -> List[int]:\n        banned = set(banned_)\n        lists = [[], []]\n        pos = [(0 if i == p else -1) for i in range(n)]\n        for i in range(n):\n            if i in banned or i == p:\n                continue\n            lists[i % 2].append(i)\n        queue = [ p ]\n\n        for i in queue:\n            l = lists[(k - 1 - i) % 2]\n            lower_min = max(0, i - k + 1)\n            lower_max = min(n - k, i)\n            j_lower_min = 2 * lower_min + k - 1 - i\n            j_lower_max = 2 * lower_max + k - 1 - i\n            j = bisect_left(l, j_lower_min)\n            while j < len(l) and l[j] <= j_lower_max:\n                queue.append(l[j])\n                pos[l[j]] = pos[i] + 1\n                del l[j]\n\n        return pos\n```
['Python3']