C++ Commented Solution | Using BFS, Set | Time- O(nlogn), Space - O(n)
Code\n\n\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        int len = banned.size(), res = -1
# Code\n```\n\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        int len = banned.size(), res = -1, sz, cur, low, high;\n        vector<int> ans(n, -1);\n        set<int> even, odd;// Create two sets to store even and odd indices respectively Initially, all indices are present in the corresponding set\n        for (int i = 0; i < n; i++) i % 2 == 0 ? even.insert(i) : odd.insert(i);\n        for (int i = 0; i < len; i++)  banned[i] % 2 == 0 ? even.erase(banned[i]) : odd.erase(banned[i]); // Remove the banned indices from their corresponding sets\n        queue<int> q; // Use a BFS approach to traverse the array and find the minimum number of reverse operations required to move the 1 to all other indices\n        q.push(p);\n        p % 2 == 0 ? even.erase(p) : odd.erase(p); // p is insert in the queue, so remove it form set\n        while (!q.empty()) {\n            res++;\n            sz = q.size();\n            while (sz--) {\n                cur = q.front();\n                q.pop();\n                ans[cur] = res; // Update the answer for the current index\n                low = cur < k ? 0 : cur - k + 1; // Determine the lowest index from which if we take subarray of length k then cur is part of that subarray\n                high = n - 1 - cur < k ? n - 1 : cur + k - 1; // Determine the highest index if subarray of length k end to that index then cur is part of that subarray\n                low += low + k - 1 - cur; // Determine the lowest index where cur element can go after reverse opreation\n                high -= cur + k - 1 - high; // Determine the highest index where cur element can go after reverse opreation\n                // Use the sets to find the next indices that can be visited within the allowed range\n                if (low % 2 == 0) {\n                    auto it = even.lower_bound(low);\n                    while (it != even.end() && *it <= high) {\n                        q.push(*it);\n                        auto ij = it;\n                        it++;\n                        even.erase(ij);\n                    }\n                } else {\n                    auto it = odd.lower_bound(low);\n                    while (it != odd.end() && *it <= high) {\n                        q.push(*it);\n                        auto ij = it;\n                        it++;\n                        odd.erase(ij);\n                    }\n                }\n            }\n        }\n        return ans; // Return the final answer\n    }\n};\n\n```\n\n# Complexity\n**Time complexity:**\n\nRemoving the banned indices from the sets takes O(len) time.\nThe BFS algorithm has a worst-case time complexity of O(n), where n is the number of elements in the array, as each index is visited at most once.\nFinding the lower and upper bounds for each index takes O(log n) time in the worst case.\nUpdating the sets and the queue takes O(log n) time for each index.\nTherefore, the overall time complexity of the algorithm is O(n log n).\n\n**Space complexity:**\n\nThe space required to store the sets is O(n) as each index is stored at most once.\nThe space required to store the queue is also O(n) as each index is stored at most once.\nThe space required to store the answer vector is O(n).\nTherefore, the overall space complexity of the algorithm is O(n).
['Breadth-First Search', 'Ordered Set', 'C++']