[Python] Simple approach with SortedList + comments
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is formulated as a graph exploration problem, and the answer can be found b
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is formulated as a graph exploration problem, and the answer can be found by using BFS\n\nThe first complex issue is finding out to which other nodes I can go from a given node and a given k. Let\'s ignore cases too close to the margins for now. Notice that the furthest node we can go right is current_index + k - 1. This is done by using a subarray that starts at current_index and ends at current_index + k - 1. If we slide this subarray by one, making it start at current_index -1, and end at current_index + k - 2, the new position of the 1 is current_index + k - 3. So we slide to the left by 2 positions.\ncurrent_index + k - 1 => current_index + k - 3 => current_index + k - 5 etc.\n\nThis means that we maintain the parity of the index for a given iteration, if the first position that is attainable is even, then all subsequent attainable positions are even as well, same goes for odd. \n\nThe second complex issue is how to make the algorithm run fast enough.\nWe need to store the non visited and visitable indexes, these can be stored in a SortedList. This will make iterating over the attainable values easy and fast. Once we visited a node we can remove it from the list.\n\nThis is enough to have an AS.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nClassic BFS with a few twists:\n\n```\nstart at p\nwhile nodes to visit:\n    visit node\n    compute min attainable index, max attainable index and parity\n    iterate over given indexes in the correct parity list:\n        update res value\n        add index to next node to visit\n        remove nodes from non visited nodes\n```\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n log n), we visit each node once\neach visit is O(log n), computing lo and high is O(1), but finding the correct indices from the sorted list is O(log n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\nwe simple store all the indexes we have not visited\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n        \n        res = [-1 for _ in range(n)]\n        res[p] = 0\n        banned = set(banned)\n        non_visited = [SortedList(), SortedList()]\n\n        for i in range(n):\n            if i not in banned and i != p:\n                non_visited[i % 2].add(i)\n\n        d = 0\n        cand = set([p])\n\n        while len(cand) > 0:\n\n            next = set()\n            d += 1\n            \n            for c in cand:\n                #this is the position where the subarray can start, furthest down is c-k+1, unless it\'s smaller than 0 (subarray cannot start at index under 0)\n                lo = max(c-k+1, 0)\n                #once we have the lowest position the subarray can start at, easy to find new position of the 1, it\'s simply st_position + end_position - current_position\n                low_po = lo + (lo +k-1) - c\n\n                #this is the highest position the subarray can start at, it\'s c+k-1 unless it\'s bigger than n-1 (size of the array)\n                hi = min(n-1, c+k-1)\n                #once we have the lowest position the subarray can start at, easy to find new position of the 1, it\'s simply st_position + end_position - current_position\n                hi_pos = (hi-k+1) + hi -c \n\n                par = (c - k + 1) % 2\n\n                #we store the values we want to iterate over in a separate list in memory\n                #because in the loop we remove the values from the SortedList, and removing values from a list you are iterating over is bad\n                iterations = list(non_visited[par].irange(low_po, hi_pos+1))\n                for e in iterations:\n                    res[e] = d\n                    next.add(e)\n                    non_visited[par].remove(e)\n\n            cand = next\n\n        return res\n\n```
['Python3']