DSU,BFS and Easy Maths explained in my best way, beats 96%.✅
Intuition\n Describe your first thoughts on how to solve this problem. \nPropagating in a BFS fashion to get minimum distance from source \'P\' to every other i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nPropagating in a BFS fashion to get minimum distance from source \'P\' to every other index of the array, and using DSU to skip visited node which is the greatest optimization in our code. Why BFS? Why DSU? go through my approach I have tried my best to explain every critical step of the code. I have also explained the mathematics of finding range [l,r] this code in easiest way.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI have commented out the approach in the every step of the code\nGo through the comments line by line. Don\'t worry if you dont\'t understand any particular step read the whole code maybe the thing which you didn\'t understand becomes understandable after reading the whole code.\n\n\n# Code\n```\nclass Solution {\npublic:\n\n\nint even[100100];\nint odd[100100];\n\n//Creating DSU parent finding function for Odd and Even array\n\nint even_par(int i){\n    if(i==even[i])\n    return i;\n    \n    return even[i]=even_par(even[i]);\n}\nint odd_par(int i){\n    if(i==odd[i])\n    return i;\n\n    return odd[i]=odd_par(odd[i]);\n}\n\n vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n\n        vector<int>ans(n,-1);\n//storing parent of every index,in the beginning every element \n//will be parent of it self.\n\n//How and Why DSU? is explained at line no 84.\n        for(int i=0;i<n+2;i++)\n        even[i]=i,odd[i]=i;\n\n        for(auto i:banned){\n            if(i&1)\n            odd[i]=i+2;\n            else even[i]=i+2;\n        }\n\n     /*If any index is visited then we will skip this index and\n     jump to +2 distance because we can only visit every second\n     element in the range. \n     This can get more clear if you draw a sliding window of size K\n     and check the reversal operations, you will observe\n     that every alternating position int the range[left,right] \n     will differ by exactly 2.\n        */\n\n\n        if(p&1)odd[p]=p+2; //This line will get clear from the comment of line no 78-79.\n        else even[p]=p+2;\n\n/*Propagating through the array in BFS style\n will make us achieve the minimum distance from index \'P\'\n to every other index*/\n\n    int dis=0;//Every level will define the minimum distance from source \'P\' to other vertices.\n\n    ans[p]=0; //Source will be at distance 0\n    queue<int>q;\n    q.push(p);\n        \n    while(!q.empty()){\n        \n        dis++;\n        int sz=q.size();\n\n       for(int j=0;j<sz;j++){\n            int curr=q.front();\n            q.pop();\n                \n                int left=curr-k+1; //Left boundary from current index\n\n                /* If left boundary gets out of range, (left<0)\n                Then bring it back to range by taking difference \n                with the leftmost range(0) of the array\n               \'0-(curr-k+1)\' */\n\n                if(left<0)\n                left=k-curr-1;\n\n              \n                int right=curr+k-1;//Right boundary from current index\n\n                 /* If right boundary gets out of range, (right>=n)\n                Then bring it back to range by taking difference \n                with the rightmost range(n) of the array\n                n-((curr+k-1)-n) */\n\n                if(right>=n)\n                right=n+n-k-curr-1;\n\n                /*From the observation we get if our left or right boundary lies on\n                even/odd place then every position from [left,right] will lie on same parity\n                as every next position is at +2 distance. \n                */\n\n           if(left&1){\n\n>            /*For every index i we have found it\'s left and right\n             boundary now we will jump +2 steps from [left,right]\n             and add the unvisited nodes/indexes into the BFS queue,\n             inserting the visited node again and again will be of\n             no help so, it will be better to skip it.\n             And also traversing every index from [left,right] to \n             check if it\'s visited or not-visited will cost us linear\n             time.\n             Overall it will become a costly operation, but\n             to skip the visited node in best time we can do this:\n\n           ->We know that every index/node is parent of itself.\n\n           -> To make sure we don\'t visit the visited index again\n             we will change/point the parent of the visited index \'i\'\n             to its next index/child which is at +2 distance,\n             this will skip the visited index visiting again in \n             the next iteration. \n             We can use Disjoint Set Union(DSU) Parent finding\n             method to do this in in optimized way.\n\n           ->Initially every node is parent of itself.\n             When we will visit any parent will change its parent\n             to its next element(+2).\n             So when next time we reach a visited index \'i\'\n             it will skip us to it\'s next unvisited child/index.\n\n           ->Doing this same thing for even case.\n               */\n\n                for(int i=odd_par(left);i<=right;i=odd_par(i)){\n                   ans[i]=dis;\n                    odd[i]=i+2;\n                    q.push(i);\n                 }\n           }else{\n              for(int i=even_par(left);i<=right;i=even_par(i)){\n                    ans[i]=dis;\n                    even[i]=i+2;\n                    q.push(i);\n                 }\n            }\n       }\n    }\n       return ans; \n    }\n};\n```
['Breadth-First Search', 'Union Find', 'Graph', 'Sliding Window', 'C++']