C++ | Clean Code with explanation
Intuition\nTo be honest binary search was the first thing that striked my mind due to the min-max pattern as seen in the problem. But my gut feeling said that s
# Intuition\nTo be honest binary search was the first thing that striked my mind due to the min-max pattern as seen in the problem. But my gut feeling said that something greedy would work. Exact binary search striked very late. \n\nI will take you through my approach from start. \nLets picture it out this way - \nPut each element and its position inside a vector and sort or put inside a hashset. ```(nums[i],i) ```\nNow lets start from back, currently we are standing on the largest number and this could be one possible answer if we could select atleast k-1 non adjacent houses out of the remaining houses behind it.\nIf we could then update ur ```ans = nums[i]``` \nelse you break because if you could not select k-1 houses out of n-1 houses then you wont be able to select it from n-2.\n\nNow we move onto the seccond last element ,this is where we should note one thing, that elements greater than this would be avoided. ```i.e i+1 ... n-1 will be ignored```. \nWhy ? Because at ith position we consider that nums[i] is the max capability that we can get.\n\nA bruteforce solution could be to simply have a loop nested inside and iterate over the non-sorted array where you pick elemnts smaller then equal to current i and make sure that none of them are adjacent. \nHere I was trying to optimise the inner loop that is trying to see if I could check if it is possible to choose k-1 non adjacent house.\n\nAfter a long time I realised that the outer loop could be optimised into a Binary search because if I could do it with i then I am checking for i-1 or else breaking.\n\n## This is bruteforce sol :\n```\nint minCapability(vector<int>& nums, int k) {\n        auto v = nums ; \n        sort(v.begin(),v.end());\n        int ans = 0 ;\n        for(int i = v.size()-1 ; i >= 0 ; i--){\n            int r = 0 , j = 0 ; \n            while(j < nums.size()){\n                if(nums[j] <= v[i]){\n                    r += 1 , j += 2 ;\n                }else j += 1 ;\n            }\n            if(r >= k){\n                ans = v[i] ; \n            }\n            else break ;\n        }\n        return ans ;\n    }\n```\n\n\n\n\n# Approach\nThe binary search is in the same direction, so take your l = 0 , r = n-1 and apply binary seaach on the sorted array. \nIf you could do it with mid than check if you could do it for lower index or check for higher. The inner loop in bruteforce becomes the checker.\n\n# Complexity\n- Time complexity:\nO(logn * n) \n\n- Space complexity:\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int minCapability(vector<int>& nums, int k) {\n        auto v = nums ; \n        sort(v.begin(),v.end());\n\n        auto check = [&](int x){\n            int r = 0 , i = 0; \n            while(i < nums.size()){\n                if(nums[i] <= x){\n                    r += 1 , i += 2 ; \n                    continue ;\n                }\n                i += 1 ;\n            }\n            return r >= k ;\n        };\n\n        int l = 0 , r = nums.size()-1 , ans = 0  ; \n        while(l <= r){\n            int mid = (l+r)/2 ; \n            if(check(v[mid])){\n                ans = v[mid] ; \n                r = mid - 1 ; \n                continue ;\n            }\n            l = mid + 1 ;\n        }\n        return ans ;\n    }\n};\n```
['Binary Search', 'C++']