[Python] Beats 100% time with 14 lines, simple BFS idea
Intuition\n\nSome observations about the problem:\n\n   Each subarray reverse operation is just moving the position p of the single 1 in the array.\n   Therefor
# Intuition\n\nSome observations about the problem:\n\n*   Each subarray reverse operation is just moving the position p of the single 1 in the array.\n*   Therefore the current "state" after any number of reverses can be summarized by the current position `pos` of the 1, and the number of `moves` taken to get there.\n*   The potential reversal operations at any state are limited by just two factors:\n    *   The banned positions: the 1 isn\'t allowed to be moved there by a subarray reversal\n    *   The boundaries of the array: the subarray being reversed should contain the 1 (otherwise there\'s no point), but it can\'t extend beyond the overall array.\n\n\n# Approach\n\nThe idea is to take a dynamic programming approach, sort of a breadth-first search from the starting point `pos=p` with `moves=0`.\n\nAt each step, we form an array `added` of the new positions that can be reached with one more reverse operation (i.e. `moves+1` steps).\n\nWhen the newly-reachable array `added` is empty, the search ends. We never add anything twice to this array.\n\nThe key observation for efficiency is that the **newly-reachable positions consist of all even or odd indexes within a sub-array**. That means that by just computing the left and right *boundaries* (called `lbound` and `rbound`) of what is newly-reachable, we have all the information we need. This saves a nested loop and makes the code much faster!\n\n# Complexity\n- Time complexity: $$O(n^2/k)$$. The bottleneck is the list comprehension to compute the next `added` set, which iterates over (half of) the integers in the range `[lbound..rbound]`. This outer while loop is then repeated $$O(n/k)$$ times in order to potentially reach from one side of the array to the other.\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n        banda = [False] * n\n        for i in banned: banda[i] = True\n        ops = [-1] * n\n        moves = 0\n        added = [p]\n        while added:\n            lbound, rbound = n, -1\n            for pos in added:\n                ops[pos] = moves\n                lbound = min(lbound, abs(pos - k + 1))\n                rbound = max(rbound, n - 1 - abs(n - k - pos))\n            added = [i for i in range(lbound, rbound+1, 2) if (ops[i] == -1 and not banda[i])]\n            moves += 1\n        return ops\n\n\n```
['Python3']