C++  | 100% | Understandable (very detailed)
Approach 1\nAt first glance the problem doesn\'t look very hard. (But it is :))\nWhat we need to do:\n1. Mark banned positions\n2. Start the queue from specifie
# Approach 1\nAt first glance the problem doesn\'t look very hard. (But it is :))\nWhat we need to do:\n1. Mark banned positions\n2. Start the queue from specified position\n3. Add to the queue following positions from the current according to the rule from the condition (skip visited positions)\n4. Go through all of the queue till the end\n\nSome remarks before we start:\n\nAt the begginng we will mark unvisited position as -1. So if position is not visited at the end it will have correct value. The initial position $$p$$ we mark as visited at $$0$$. When we add any position to the queue we get value from current position and increase it by 1.\nSo at the end our $$visited$$ array will be the result.\n\nAnd about how we get following positions from the current. \nLet\'s for example $$k = 6$$ What we can do here:\n$$ 0 0 0 0 0 1 0 0 0 0 0 $$\n$$|0 0 0 0 0 1|0 0 0 0 0 $$ => $$|1 0 0 0 0 0|0 0 0 0 0 $$\n$$ 0|0 0 0 0 1 0|0 0 0 0 $$ => $$ 0|0 1 0 0 0 0|0 0 0 0 $$\n$$ 0 0|0 0 0 1 0 0|0 0 0 $$ => $$ 0 0|0 0 1 0 0 0|0 0 0 $$\n$$ 0 0 0|0 0 1 0 0 0|0 0 $$ => $$ 0 0 0|0 0 0 1 0 0|0 0 $$\n$$ 0 0 0 0|0 1 0 0 0 0|0 $$ => $$ 0 0 0 0|0 0 0 0 1 0|0 $$\n$$ 0 0 0 0 0|1 0 0 0 0 0|$$ => $$ 0 0 0 0 0|0 0 0 0 0 1|$$\n\nSo the starting position is $$position - k + 1$$. And next we get every even position (even if we count from the starting position, not from 0) up to $$position + k - 1$$\nAlso we should check edge cases when $$position - k + 1 < 0$$ or $$position + k - 1 >= n$$\n\n# Code\n```\nclass Solution \n{\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) \n    {\n        std::vector<int> visited(n, -1);\n        std::vector<int> ban(n , 0);\n        for (const int& b: banned)\n        {\n            ban[b] = -1;\n            visited[b] = -1;\n        }\n\n        std::queue<int> q;\n        q.push(p);\n        visited[p] = 0;\n        while (!q.empty())    \n        {\n            int curr = q.front();\n            q.pop();\n\n            int begin = curr - k + 1;\n            int end   = curr + k - 1;\n\n            for (int i = begin, start = begin; i <= end; i += 2, ++start)\n            {\n                if (start < 0 || start + k - 1 >= n || -1 == ban[i])\n                    continue;\n\n                if (-1 == visited[i])\n                {\n                    q.push(i);\n                    visited[i] = visited[curr] + 1;\n                }\n            }\n        }\n\n        return visited;\n    }\n};\n```\n\nThis solution is okay, but we get TLE here.\n\n# Approach 2\nImprove check for edge cases first\n\n```\nclass Solution \n{\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) \n    {\n        std::vector<int> visited(n, -1);\n        std::vector<int> ban(n , 0);\n        for (const int& b: banned)\n        {\n            ban[b] = -1;\n            visited[b] = -1;\n        }    \n\n        std::queue<int> q;\n        q.push(p);\n        visited[p] = 0;\n        while (!q.empty())    \n        {\n            int curr = q.front();\n            q.pop();\n\n            int begin = std::abs(curr - k + 1);\n            int end   = n - 1 - std::abs(n - curr - k);\n\n            for (int i = begin; i <= end; i += 2)\n            {\n                if (-1 == ban[i])\n                    continue;\n\n                if (-1 == visited[i])\n                {\n                    q.push(i);\n                    visited[i] = visited[curr] + 1;\n                }\n            }\n        }\n\n        return visited;\n    }\n};\n```\nObviously we haven\'t improved anything much, so again we will get TLE here\nSo, what is  the problem?\nWe add each position at most once to the queue and we must check each position. So the problem in the way we find following positions from the current one. The larger the window size $$k$$ we have, the greater its intersection for neighboring points. So we have to control positions that we have already checked.\n\n# Approach 3\n\nHere we store all non-banned positions in two arrays for even and odd positions. When ever the position is used we erase it from array.\n```\nclass Solution \n{\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) \n    {\n        std::vector<int> visited(n, -1);\n        std::vector<int> ban(n , 0);\n        for (const int& b: banned)\n        {\n            ban[b] = -1;\n            visited[b] = -1;\n        }\n        \n        std::vector<int> odd;\n        std::vector<int> even;\n        for (int i = 0; i < n; ++i) \n        {            \n            if (!ban[i] && i != p) \n            {\n                if (i & 1)\n                    odd.push_back(i);\n                else\n                    even.push_back(i);\n\n            }\n        }\n\n        std::queue<int> q;\n        q.push(p);\n        visited[p] = 0;\n        while (!q.empty())    \n        {\n            int curr = q.front();\n            q.pop();\n\n            int begin = std::abs(curr - k + 1);\n            int end   = n - 1 - std::abs(n - curr - k);\n            \n            std::vector<int>& list = begin & 1 ? odd : even;\n            for (int pos = list.size() - 1; pos >= 0; --pos)\n            {\n                if (list[pos] > end)\n                    continue;\n                if (list[pos] < begin)\n                    break;\n                \n                q.push(list[pos]);\n                visited[list[pos]] = visited[curr] + 1;\n                list.erase(list.begin() + pos);\n            }            \n        }\n\n        return visited;\n    }\n};\n```\nUnfortunately we will get TLE again. The main reason, because erase operation on a vector is not so fast. \n\n# Approach 4\n\nTo improve the performance of removing an element, replace the vector with a linked list. Let\'s write a simple implementation.\n\n# Code\n```\nclass Solution \n{\nprivate:\n    \n    struct ListEntry\n    {\n        int val;\n        ListEntry* next;\n        ListEntry* prev;\n        \n        ListEntry(const int& v)\n        {\n            val  = v;\n            next = nullptr;\n            prev = nullptr;\n        }\n    };\n    class LinkedList\n    {\n    public:\n        LinkedList()\n        {\n            head = nullptr;\n            tail = nullptr;\n        }\n        ~LinkedList()\n        {\n            while (head)\n            {\n                ListEntry* temp = head->next;\n                delete head;\n                head = temp;\n            }\n            \n            head = nullptr;\n            tail = nullptr;\n        }\n        void push(const int& v)\n        {\n            if (!tail)\n            {\n                head = new ListEntry(v);\n                tail = head;                \n            }\n            else\n            {\n                ListEntry* p = new ListEntry(v);\n                p->prev = tail;\n                tail->next = p;\n                tail = p;\n            }\n        }\n        ListEntry* find(const int& v)\n        {\n            ListEntry* cur = head;\n            while (cur && cur->val < v)\n            {\n                cur = cur->next;                    \n            }\n            return cur;\n        }\n        void erase(ListEntry* p)\n        {\n            if (head == tail && p == head)\n            {\n                head = nullptr;\n                tail = nullptr;\n            }\n            else if (head == p)\n            {\n                head = head->next;\n                head->prev = nullptr;\n            }\n            else if (tail == p)\n            {\n                tail = tail->prev;\n                tail->next = nullptr;\n            }\n            else\n            {\n                ListEntry* prev = p->prev;\n                p->prev->next = p->next;\n                p->next->prev = p->prev;\n            }\n            delete p;\n        }\n        \n    private:\n        ListEntry* head;        \n        ListEntry* tail;\n    };\n    \npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) \n    {\n        std::vector<int> visited(n, -1);\n        std::vector<int> ban(n , 0);\n        for (const int& b: banned)\n        {\n            ban[b] = -1;\n            visited[b] = -1;\n        }\n        \n        LinkedList odd;\n        LinkedList even;\n        for (int i = 0; i < n; ++i) \n        {            \n            if (!ban[i] && i != p) \n            {\n                if (i & 1)\n                    odd.push(i);\n                else\n                    even.push(i);\n            }\n        }\n        \n\n        std::queue<int> q;\n        q.push(p);\n        visited[p] = 0;\n        while (!q.empty())    \n        {\n            int curr = q.front();\n            q.pop();\n\n            int begin = std::abs(curr - k + 1);\n            int end   = n - 1 - std::abs(n - curr - k);\n\n            LinkedList& list = begin & 1 ? odd : even;\n            ListEntry* entry = list.find(begin), *nextEntry;\n            while (entry && entry->val <= end)\n            {\n                q.push(entry->val);\n                visited[entry->val] = visited[curr] + 1;\n                nextEntry = entry->next;\n                list.erase(entry);\n                entry = nextEntry;\n            }            \n        }\n\n        return visited;\n    }\n};\n```\n\nHooray, we did it. All tests passed. Cheers :)\n\n# Update. Approach 5: \n\nWe passed all tests, but as mentioned in the comments, we can still get TLE in some edge situations.\nFor example here:\n```\nminReverseOperations(100000, 50000, {}, 2);\n```\nThis is because in the previous approach, our $$LinkedList::find$$ method started searching from the beginning of the list and had to go through the entire list to the desired element, which gives us the linear complexity $$O(n)$$.\nSo let\'s try to replace linked list with a Binary Search Tree to achieve time complexity for all operations equal to $$O(log n)$$\nSince we have a sorted list at the beginning, it will be easy to build a balanced BST.\nTo leave our main algorithm untouched, we add $$find$$ and $$erase$$ methods to the $$Tree$$ class.\n\n```\nclass Solution \n{\nprivate:\n    \n    struct TreeNode\n    {\n        int val;\n\n        TreeNode* left;\n        TreeNode* right;\n        TreeNode* parent;\n\n        TreeNode(const int& v)\n        {\n            val    = v;\n            left   = nullptr;\n            right  = nullptr;\n            parent = nullptr;\n        }\n    };\n\n    class Tree\n    {\n    public:\n\n        Tree(const std::vector<int>& v)\n        {\n            root = initFrom(v, 0, v.size() - 1);\n        }\n        TreeNode* find(const int& val)\n        {\n            return find(root, val);\n        }\n        TreeNode* next(TreeNode* node)\n        {\n            if (node->right)\n            {\n                node = node->right;\n                while (node->left)\n                    node = node->left;\n\n                return node;\n            }\n        \n            TreeNode* parent = node->parent;\n            while (parent && node == parent->right) \n            {\n                node = parent;\n                parent = parent->parent;\n            }\n            return parent;\n        }\n        TreeNode* erase(TreeNode* node)\n        {\n            if (!node)\n                return nullptr;\n\n            TreeNode* parent = node->parent;\n            if (!node->left && !node->right)\n            {\n                TreeNode* nextNode = next(node);\n                if (!parent)\n                {\n                    root = nullptr;\n                }\n                else\n                {\n                    if (parent->left == node)\n                        parent->left = nullptr;\n                    else\n                        parent->right = nullptr;\n                }\n                \n                return nextNode;\n            }\n            else if (!node->left) \n            {\n                TreeNode* nextNode = next(node);\n\n                if (!parent)\n                {\n                    root = node->right;\n                    node->right->parent = nullptr;\n                }\n                else if (parent->left == node)\n                {\n                    parent->left = node->right;\n                    node->right->parent = parent;\n                }\n                else\n                {\n                    parent->right = node->right;\n                    node->right->parent = parent;\n                }\n\n                delete node;\n                return nextNode;\n            }\n            else if (!node->right) \n            {\n                TreeNode* nextNode = next(node);\n                if (!parent)\n                {\n                    root = node->left;\n                    node->left->parent = nullptr;\n                }\n                else if (parent->left == node)\n                {\n                    parent->left = node->left;\n                    node->left->parent = parent;\n                }\n                else\n                {\n                    parent->right = node->left;\n                    node->left->parent = parent;\n                }\n\n                delete node;\n                return nextNode;\n            }\n            else\n            {\n                TreeNode* temp = node->right;\n                while (temp->left)\n                    temp = temp->left;\n\n                node->val = temp->val;\n\n                erase(temp);\n                return node;\n            }\n        }\n\n    private:      \n        TreeNode* initFrom(const std::vector<int>& vec, int start, int end)\n        {       \n            if (start > end)\n                return nullptr;\n        \n            int mid = (start + end) / 2;\n            TreeNode* node = new TreeNode(vec[mid]);\n            node->left  = initFrom(vec, start, mid - 1);\n            node->right = initFrom(vec, mid + 1, end);\n\n            if (node->left)\n                node->left->parent = node;\n            if (node->right)\n                node->right->parent = node;\n\n            return node;\n        }\n        TreeNode* find(TreeNode* node, const int& val)\n        {\n            TreeNode* stored = nullptr;\n            while (node)\n            {\n                if (node->val >= val)\n                {\n                    stored = node;\n                    node = node->left;\n                }\n                else\n                {\n                    node = node->right;\n                }\n            }\n            return stored;\n        }\n    private:\n\n        TreeNode* root;\n    };\npublic:    \n    std::vector<int> minReverseOperations(int n, int p, std::vector<int>& banned, int k) \n    {\n        std::vector<int> visited(n, -1);\n        std::vector<int> ban(n , 0);\n        for (const int& b: banned)\n        {\n            ban[b] = -1;\n            visited[b] = -1;\n        }\n        \n        std::vector<int> vOdd, vEven;\n        for (int i = 0; i < n; ++i) \n        {            \n            if (!ban[i] && i != p) \n            {\n                if (i & 1)\n                    vOdd.push_back(i);\n                else\n                    vEven.push_back(i);\n            }\n        }          \n\n        Tree odd(vOdd);\n        Tree even(vEven);    \n        \n        std::queue<int> q;\n        q.push(p);\n        visited[p] = 0;\n        while (!q.empty())    \n        {\n            int curr = q.front();\n            q.pop();\n\n            int begin = std::abs(curr - k + 1);\n            int end   = n - 1 - std::abs(n - curr - k);\n\n            Tree& tree = begin & 1 ? odd: even;\n            TreeNode* entry = tree.find(begin);\n            while (entry && entry->val <= end)\n            {\n                q.push(entry->val);\n                visited[entry->val] = visited[curr] + 1;\n                entry = tree.erase(entry);\n            }\n        }\n        return visited;\n    };\n};\n```\n\nWe did it again :)\nTest passing time has been improved and we didn\'t get TLE for edge case mentioned in the title of this approach.\n
['C++']