Stupid Greedy & Union Find Solution || No Binary search || C++
Intuition\nGreedy.. No binary search... I don\'t know why I didn\'t think of binary search which is much easier. \nUse priority queue and sort nums array with i
# Intuition\nGreedy.. No binary search... I don\'t know why I didn\'t think of binary search which is much easier. \nUse priority queue and sort nums array with its index in the queue(or heap). Pop element from queue 1 by 1 and as soon as you can create a sequence of size >=k with non consecutive elements, you are done.\n\n# Approach\nYou have to find minimum number -> num such that you can construct a sequence of length >=k of non consecutive elements and all the numbers in this sequence are <=num. We start with smallest number and move on to bigger numbers using heap. At any point if we pop an element from heap and find that we can construct such sequence, we are done. \n\nMaintain a parent array and size array (standard union find) of all the numbers already popped from the heap. Suppose at any iteration we pop the element at index idx(initially it is its own parent) but we have already popped the element at index ->idx-1 earlier, so we now need to merge these two components. \nThe idea behind this is that any component represents the consecutive elements that we have already popped from heap (Suppose the elements popped are 1,2,3,6,7,8 then 1,2,3 are present in one component and 6,7,8 in other component). Similarly check if we had earlier popped element at index-> idx+1. If yes, merge again. The benefit is that suppose a component contains x elements. We can only select [(x+1)/2] elements from this component because of non consecutive requirement. \n\nMaintain a counter->cur which at any iteration denotes the maximum sequence of non consecutive elements that we can form such that all elements are  <= element popped from heap. Suppose num=[1,2,3,4]. We pop 1 and put it in component 1. We pop 2 and merge with 1st component. Still cur=1. Pop 3 and merge. Now cur=[(3+1)/2]=2. Pop 4. Still cur=[(4+1)/2]=2.\n\n# Complexity\n- Time complexity:\nO(nlogn)\n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass helper\n{\n    public:\n    bool operator()(const pair<int,int>& a,const pair<int,int>& b)\n    {\n        if(a.first<b.first)\n            return false;\n        \n            return true;\n    }\n};\nclass Solution {\npublic:\n    int find(vector<int>& parent,int i)\n    {\n        if(i<0 ||i>=parent.size())\n            return -1;\n        if(parent[i]==-1) //This means element at index i has not yet been popped from the heap\n            return -1;\n        if(parent[i]==i)  \n            return i;\n        return parent[i]=find(parent,parent[i]);\n    }\n    int flo(int i)\n    {\n        return (i+1)/2;\n    }\n    void merge(int a,int b,vector<int>& parent,vector<int>& size)\n    {\n        parent[a]=b;\n        size[b]+=size[a];\n    }\n    int minCapability(vector<int>& nums, int k) {\n        priority_queue<pair<int,int>,vector<pair<int,int>>,helper> pq;\n        for(int i=0;i<nums.size();i++)\n        {\n            pq.push({nums[i],i});\n        }\n        int n = nums.size();\n        int cur=0; // Length of longest sequence with non consecutive element\n        vector<int> parent(n,-1),size(n,0);\n        while(cur<k)\n        {\n            pair<int,int> p=pq.top();\n            pq.pop();\n            int index=p.second;  //Index of popped element in nums\n            parent[index]=index; //Add this element as its own parent            \n            size[index]++;     //Size of this component is now 1 \n            \n            int comp_prev=find(parent,index-1); //Gives component of index-1 if that element is already popped from heap\n            int comp_next=find(parent,index+1); //Gives component of index+1 if that element is already popped from heap\n            \n            if(comp_prev!=-1 && comp_next!=-1)  //We need to merge 3 components\n            {\n                cur-=flo(size[comp_prev]);\n                cur-=flo(size[comp_next]);\n                merge(comp_prev,index,parent,size);\n                merge(comp_next,index,parent,size);\n                cur+=flo(size[index]);\n            }\n            else if(comp_prev!=-1)  //Merge 2 components\n            {\n                cur-=flo(size[comp_prev]);\n                merge(comp_prev,index,parent,size);\n                cur+=flo(size[index]);\n            }\n            else if(comp_next!=-1)  //Merge 2 components\n            {\n                cur-=flo(size[comp_next]);\n                merge(comp_next,index,parent,size);\n                cur+=flo(size[index]);\n            }\n            else    //No merge required\n                cur++;\n            if(cur>=k)\n                return p.first;\n        }\n        return -5; //Return anything... it does not matter\n    }\n};\n```
['Union Find', 'Heap (Priority Queue)', 'C++']