C++ O(nlogn) BFS + BST
Intuition\nConsider the position of the 1 in the array as a state, e.g. let node k represent 1 is at position k in the array. Then the reverse operation is just
# Intuition\nConsider the position of the $$1$$ in the array as a state, e.g. let node k represent $$1$$ is at position k in the array. Then the reverse operation is just an edge between 2 states. Thus, the question become finding the shortest path from initial state to all other states.\n\n# Approach\nIf we do the bfs in a naive way, the complexity would become $$O(nk)$$ since there are $$nk$$ edges which would be TLE. However, we know that actual number of edges needed to access in bfs is just $$n-1$$ (bfs tree). So we would try to optimize by reducing the number of edges to access.\n\nFirst, let\'s use a set $$s$$ to store all accessible nodes. After we access the node in bfs, we would remove it from the $$s$$. However, we still need to perform a $$O(k)$$ check to the nodes in $$s$$ and the complexity does not reduced.\n\nSecond, note that node $$i$$ could only access either odd nodes or even nodes and the accessible nodes are continuous after spliting. So let split the nodes into odd and even nodes. Then with the help of $$lower\\_bound$$(binary search), we could get the accessible nodes with $$O(logn)$$. Since all nodes would only be accessed once and the overall complexity can be reduced to $$O(nlongn)$$.\n\n# Complexity\n- Time complexity:\n$$O(nlogn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        vector<int> result(n, -1);\n        set<int> even, odd;\n        for (int i = 0; i < n; i++) {\n            if (i & 1) {\n                odd.insert(i);\n            } else {\n                even.insert(i);\n            }\n        }\n        result[p] = 0;\n        // remove init pos and banned nodes\n        odd.erase(p);\n        even.erase(p);\n        for (int v : banned) {\n            odd.erase(v);\n            even.erase(v);\n        }\n        queue<int> q;\n        q.push(p);\n        while (!q.empty()) {\n            int v = q.front();\n            q.pop();\n            // choose correct parity set to work on\n            set<int> &s = (v + k) & 1 ? even : odd;\n            auto it = s.lower_bound(abs(v - k + 1));\n            vector<int> temp;\n            // get all nodes between [abs(v - k + 1), (n - 1 - abs(v + k - n)] with same parity \n            while (it != s.end() && (*it) <= (n - 1 - abs(v + k - n))) {\n                temp.push_back((*it));\n                it++;\n            }\n            for (int t: temp) {\n                result[t] = result[v] + 1;\n                q.push(t);\n                // remove the accessed node\n                s.erase(t);\n            }\n        }\n        return result;\n    }\n};\n```
['Breadth-First Search', 'Binary Search Tree', 'C++']