Python and C# solutions: from TLE solution during contest to accepted solution
Intuition\n Describe your first thoughts on how to solve this problem. \nAfter reading the question instruction, one should realize BFS is the way to go. From t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAfter reading the question instruction, one should realize BFS is the way to go. From the point p, we check all the possible next flip positions and add 1 extra step\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe logic of the code is pretty simple. However, if $k$ becomes as large as $n$, the code could not pass within $10$ seconds ($700+$ testcases). I note that the time consuming part is the $j$-loop to look for all possible $k$-subarrays which contains the current node of interest. We therefore need a faster lookup data structure to keep the remaining (possibly) reachable nodes instead of constantly looking up the visited set.\n\nWhen we check carefully, we observe that the next reachable nodes are parity separated: $2*j + k - 1 - i$ is either odd or even regardless of value of $j$, but only depends on the parity of k - 1 - i. Therefore, if we keep the odd and even nodes in two binary search trees (sortedlist in Python, SortedSet in C#), we can binary search to get all the remaining relevant nodes, put them in the queue and remove them from the trees. This way we do not even need to refer to the visited / banned set.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nk)$$ for TLE solution, $$O(nlogk)$$ if use 2 sorted lists\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n- TLE solution, but provides the skeleton:\n\n```\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n        result = [-1]*n\n        bannedSet = set(banned)\n        dq = deque()\n        dq.append([p, 0])\n        bannedSet.add(p)\n        while dq:\n            i, flip = dq.popleft()\n            result[i] = flip\n            for j in range(max(0, i - k + 1), min(i + 1, n + 1 - k)):\n                indexflip = 2*j + k - 1 - i\n                if indexflip not in bannedSet and result[indexflip] == -1:\n                    dq.append([indexflip, flip + 1])\n                    bannedSet.add(indexflip)\n        return result\n\n```\n- accepted solution:\n\n```\nfrom collections import deque\nfrom typing import List\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n        result = [-1]*n\n        slOdd = SortedList()\n        slEven = SortedList()\n        bannedSet = set(banned)\n        for i in range(n):\n            if i not in bannedSet:\n                if i % 2 == 1:\n                    slOdd.add(i)\n                else:\n                    slEven.add(i)\n\n        dq = deque()\n        dq.append([p, 0])\n        if p % 2 == 1:\n            slOdd.remove(p)\n        else:\n            slEven.remove(p)\n        while dq:\n            i, flip = dq.popleft()\n            result[i] = flip\n            lowerLimit = 2*max(0, i - k + 1) + k - 1 - i\n            upperLimit = 2*min(i + 1, n + 1 - k) + k - 3 - i\n            tree = slOdd if (k - 1 - i) % 2 == 1 else slEven\n            lstToRemove = list(tree.irange(lowerLimit, upperLimit))\n            for j in lstToRemove:\n                tree.remove(j)\n                dq.append([j, flip + 1])         \n        return result\n```\nC# solution using SortedSet\n```\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\npublic class Solution \n{\n    public int[] MinReverseOperations(int n, int p, int[] banned, int k) \n    {\n        int[] result = new int[n];\n        Array.Fill(result, -1);\n\n        SortedSet<int>[] trees = new SortedSet<int>[2];\n        trees = trees.Select(x => new SortedSet<int>()).ToArray();\n        HashSet<int> bannedSet = new HashSet<int>(banned);\n\n        for (int i = 0; i < n; i++)\n        {\n            if (!bannedSet.Contains(i))\n            {\n                trees[i % 2].Add(i);\n            }\n        }\n\n        Queue<int[]> queue = new Queue<int[]>();\n        queue.Enqueue(new int[2]{p, 0});\n        trees[p % 2].Remove(p);\n        while (queue.TryDequeue(out int[] item))\n        {\n            result[item[0]] = item[1];\n            int[] nodesToRemove = trees[Math.Abs(k - 1 - item[0]) % 2].GetViewBetween(2*Math.Max(0, item[0] - k + 1) + k - 1 - item[0], 2*Math.Min(item[0] + 1, n + 1 - k) + k - 3 - item[0]).ToArray();\n            foreach (int node in nodesToRemove)\n            {\n                trees[Math.Abs(k - 1 - item[0]) % 2].Remove(node);\n                queue.Enqueue(new int[2]{node, item[1] + 1});\n            }\n        }\n        return result;\n    }\n}\n```
['Python3']