From TLE to 110ms
Intuition\n Describe your first thoughts on how to solve this problem. \nThe first sight of this problem is looking for the shortest distance from starting poin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe first sight of this problem is looking for the shortest distance from starting point p to all the other cells. Every flip is the essential distance 1, and the banned cells indicate the cells are not reachable from or to. The final result number in each cell shows the shortest distance from the starting point to the given cell, and -1 indicates unreachable. It is a typical graph routing problem. Frankly, I prefer the modified Dijkstra rather than BFS as it will involve the queue, which requires additional cost to operation time due to the data structure reason.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo achieve this goal, we should know how to connect the current cell to all its reachable cells unless it\'s on the banned list. Let us take an example with k=5 as below for study.\n```\nk=5\n|i-4|i-3|i-2|i-1| i |i+1|i+2|i+3|i+4|\n                |<v---------------v>|\n            |<----v-------v---->|\n+---+---+---+---+---+---+---+---+---+\n| o | x | o | x | o | x | o | x | o |\n+---+---+---+---+---+---+---+---+---+\n|<^---------------^>|\n    |<----^-------^---->|\n        |<--------^-------->|\n                Fig 1.\no  : Reachable Cell\nx  : Unreachable Cell\n^/v: Position of Cell Flip from or to                \n```\n\nFrom Fig 1, we can see that the (i-4,i-2,i,i+2,i+4) are reachable within one flip distance. And all reachable cells are separated by one unreachable cell. If we generalize the k, we find that the most left reachable cell index is i-k+1, and the most right cell index is i+k-1 if we don\'t care whether the index is negative, over the max index boundary or any banned cells.\n\nHowever, we must also care for the actual k-length array left and right boundaries falling within the n-length array.\n\nLeft Boundary:\n```\nk>i\n  |<------------v-------v------------>|\n  +---+---+---+---+---+---+---+---+---+\n  |   |   |   | o | x | i |   |   |   |\n  +---+---+---+---+---+---+---+---+---+\n  |<------------->|               \n  ^             ^   \n  0           k-i-1\nk<=i\n          |<v-------v>|\n  +---+---+---+---+---+---+---+---+\n  |   |   | o | x | i |   |   |   |\n  +---+---+---+---+---+---+---+---+\n  |<--------->|               \n  ^         ^ \n  0       i+1-k\n\nk>i\n  |<------------v-------v------------>|\n  +---+---+---+---+---+---+---+---+---+\n  |   |   |   | i | x | o |   |   |   |\n  +---+---+---+---+---+---+---+---+---+\n  |<------------->|               \n  ^             ^   \n  0             i\nk<=i\n          |<v-------v>|\n  +---+---+---+---+---+---+---+---+\n  |   |   | i | x | o |   |   |   |\n  +---+---+---+---+---+---+---+---+\n  |<--------->|               \n  ^         ^ \n  0         i\no  : Reachable Cell\nx  : Unreachable Cell\n^/v: Position of Cell Flip from or to\n                Fig 2.\n```\nIn Fig 2, we suppose the visited cell i explored the reachable cell o; the margin is its lowest index. Just make the k-length array\'s left boundary hit the left boundary of the n-length array, 0. We notice abs(k-i-1)>=0 or i>=0. Therefore, the simplified answer is abs(k-i-1)>=0.\n\nSo, keeping the left boundary valid only requires abs(k-i-1)>=0, and the abs(k-i-1) would be the lowest index as well.\n\nRight Boundary:\n```\nk>i\n  |<------------v-------v------------>|\n  +---+---+---+---+---+---+---+---+---+\n  |   |   |   | i | x | o |   |   |   |\n  +---+---+---+---+---+---+---+---+---+\n  |<-[k-(n-1-i)]->|   |<-[k-(n-1-i)]->|\n                        ^             ^\n       n-1-[k-(n-1-i)]+1=2n-k-i-1    n-1\n                     \nk<=i\n              |<--------v-------v-------->|\n  +---+---+---+---+---+---+---+---+---+---+\n  |   |   |   |   |   | i | x | o |   |   |\n  +---+---+---+---+---+---+---+---+---+---+\n              |<k-(n-1-i)>|   |<k-(n-1-i)>|\n                              \n                               ^          ^\n            n-1-[k-(n-1-i)]+1=2n-k-i-1   n-1\n                            \n\nk>i\n  |<------------v-------v------------>|\n  +---+---+---+---+---+---+---+---+---+\n  |   |   |   | o | x | i |   |   |   |\n  +---+---+---+---+---+---+---+---+---+\n                      |<------------->|\n                        ^             ^\n                      n-1-i          n-1\nk<=i\n          |<v-------v>|\n  +---+---+---+---+---+---+---+\n  |   |   | o | x | i |   |   |\n  +---+---+---+---+---+---+---+\n                  |<--------->|\n                    ^         ^\n                   n-1-i     n-1\no  : Reachable Cell\nx  : Unreachable Cell\n^/v: Position of Cell Flip from or to\n                Fig 3.\n```\nIn Fig 2, we suppose the visited cell i explored the reachable cell o, and the margin is its highest index, making the k-length array right boundary hit the right boundary of the n-length array, which is n-1. We notice n-1-i<=n-1 and 2n-k-i+1<=n-1. Simplified, we get 2n-i-k+1<n.\n\nSo, keeping the right boundary valid only requires selecting the min(2n-i-k+1,i+k-1).\n\nAdditional Exploration:\n```\n    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n    |   |   |   |   | o | x | o | x | o | x | o | x | o |   |   |   |   |<- visited cells for generating next layer visiting cells\n    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n                      0       1       2       3       4                  \n    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n    |o-0| x |o-0| x |o-0| x |o-0| x |o-0|   |   |   |   |   |   |   |   |<- cell 0 generated reachable cells\n    |   | x |o-1| x |o-1| x |o-1| x |o-1| x |o-1|   |   |   |   |   |   |<- cell 1 generated reachable cells\n    |   |   |   | x |o-2| x |o-2| x |o-2| x |o-2| x |o-2|   |   |   |   |<- cell 2 generated reachable cells\n    |   |   |   |   |   | x |o-3| x |o-3| x |o-3| x |o-3| x |o-3|   |   |<- cell 3 generated reachable cells\n    |   |   |   |   |   |   |   | x |o-4| x |o-4| x |o-4| x |o-4| x |o-4|<- cell 4 generated reachable cells\n    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+\n      ^                                                               ^\nmin(abs(k-i-1))                                           max(min(2n-i-k+1,i+k-1))                                                     \n                                Fig 4.\n```\nLet\'s take a step further. Fig 4 shows the same flip distance cells\' reachable cells lined up and overlapping. If we handle them individually, we will have lots of duplicate work. So, we can get the minimal lowest and maximal highest indexes and handle all the reachable cells in the same batch.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        vector<int> graph(n,0);\n\n        if(k>1 && k<=n){\n            for(int i:banned){\n                graph[i]=-1;\n            }\n\n            if(!graph[p]){\n                vector<int> visited={p};\n                int distance=0;\n                int v_size=1;\n                int m=1;\n                int l_ptr=n;\n                int r_ptr=0;\n                for(int it =0;it<v_size;++it)\n                {   \n                    int i=visited[it];\n                    int t_kmi=k-i;\n                    int t_ipk=i+k;\n                    graph[i]=distance;\n                    l_ptr=min(l_ptr,abs(t_kmi-1));\n                    r_ptr=max(r_ptr,min((n<<1)-t_ipk,t_ipk));\n                    if(--m<1){\n                        for(int j=l_ptr;j<r_ptr;j+=2)\n                        {\n                            if(!graph[j]){\n                                visited.emplace_back(j);\n                            }\n                        }\n                        m=visited.size()-v_size;\n                        v_size+=m;\n                        ++distance;\n                        l_ptr=n;\n                        r_ptr=0;\n                    }\n                }\n            }\n        }\n        replace_if(graph.begin(),graph.end(),[](int x){return !x;},-1);\n        graph[p]=0;\n        return graph;\n    }\n};\n```
['C++']