from TLE to 100% time and space, the key is "insert intervals"
Here is the first iteration, straightforward BFS, but TLE\n\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        vector<in
Here is the first iteration, straightforward BFS, but TLE\n```\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        vector<int> res(n,-1);\n        for (int b : banned) res[b]=INT_MAX;\n        queue<int> q;\n        q.push(p);\n        int d=0;\n        res[p]=d;\n        while (not q.empty()) {\n            ++d;\n            for (int i=0, m=int(q.size()); i<m; ++i) {\n                int x=q.front(); q.pop();\n                // y1+2*z>=0, z>=(1-y1)/2\n                // y1+z>=0, z>=-y1\n                int y1=x-k+1;\n                if (y1<0) y1+=max(((1-y1)/2),-y1)*2;\n                // y2-2*z<n, z>=(y2-n)/2+1\n                // y2-z<n, z>=(y2-n)+1\n                int y2=x+k-1;\n                if (y2>=n) y2-=max((y2-n)/2,y2-n)*2+2;\n                for (int y=y1; y<=y2; y+=2) {\n                    if (res[y]==-1) {\n                        res[y]=d;\n                        q.push(y);\n                    }\n                }\n            }\n        }\n        for (int i=0; i<n; ++i)\n            if (res[i]==INT_MAX) res[i]=-1;\n        return res;\n    }\n```\nThe problem is that for each x, an index range of [y1,y2] increment of 2 is checked. The range size is O(K)=O(N). Therefore the overal algorithm is O(N^2)\nThe insight is that all those range [y1,y2] have a lot of overlaps, especially for large K. On the other hand, each y could be propagated from K different x and the same computation repeated K times. As an example without considering the bound and banned, K=4\n![image](https://assets.leetcode.com/users/images/6a655030-b751-436a-869f-a8b976db3fff_1680790943.0055997.png)\n\nIndex ranges should be combined first before BFS propagation. \nThe key is https://leetcode.com/problems/insert-interval/\nHere is the implementation, \n```\n    void insert(vector<vector<int>>& intervals, vector<int>& newInterval) {\n        auto p1=lower_bound(intervals.begin(),intervals.end(),newInterval[0],[](const auto& x, int v){ return x[1]<v; });\n        auto p2=upper_bound(intervals.begin(),intervals.end(),newInterval[1],[](int v, const auto& x){ return v<x[0]; });\n        vector<int>& x=newInterval;\n        if (p1!=p2) {\n            x[0]=min((*p1)[0],x[0]);\n            x[1]=max((*prev(p2))[1],x[1]);\n        }\n        intervals.erase(p1,p2);\n        intervals.insert(p1,x);\n    }\n```\n\nThen the solution is modified as, 229 ms and 100.2 MB, both metrics are 100%\n```\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        vector<int> res(n,-1);\n        for (int b : banned) res[b]=INT_MAX;\n        queue<int> q;\n        q.push(p);\n        int d=0;\n        res[p]=d;\n        while (not q.empty()) {\n            ++d;\n            vector<vector<int>> intervals;\n            for (int i=0, m=int(q.size()); i<m; ++i) {\n                int x=q.front(); q.pop();\n                // y1+2*z>=0, z>=(1-y1)/2\n                // y1+z>=0, z>=-y1\n                int y1=x-k+1;\n                if (y1<0) y1+=max(((1-y1)/2),-y1)*2;\n                // y2-2*z<n, z>=(y2-n)/2+1\n                // y2-z<n, z>=(y2-n)+1\n                int y2=x+k-1;\n                if (y2>=n) y2-=max((y2-n)/2,y2-n)*2+2;\n                vector<int> r{y1,y2+2};\n                insert(intervals,r);\n            }\n            for (auto& r : intervals) {\n                for (int y=r[0]; y<r[1]; y+=2) {\n                    if (res[y]==-1) {\n                        res[y]=d;\n                        q.push(y);\n                    }\n                }\n            }\n        }\n        for (int i=0; i<n; ++i)\n            if (res[i]==INT_MAX) res[i]=-1;\n        return res;\n    }\n```
['Breadth-First Search']