Binary Search and Dynamic Programming
 # Intuition\n<!-- Describe your first thoughts on how to solve this problem.  \n\n\n# Approach\n\nBinary search to minimize the capability in each robbery and 
<!-- # Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n<!-- Describe your first thoughts on how to solve this problem -->\n\n# Approach\n<!-- Binary search to minimize the capability in each robbery and then use dp inside predicate function to check maximum number of non adjacent houses we can rob whose with given capability. -->\nBinary search to minimize the capability in each robbery and then use dp inside predicate function to check maximum number of non adjacent houses we can rob whose with given capability.\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- O(nlogn) -->\n\n\n- Space complexity: O(n)\n<!-- O(n) -->\n\n\n# Code\n```\nclass Solution {\npublic:\n    int helper(int i,vector<int> &nums,int x,vector<int> &dp){\n        if(i < 0){\n            return 0;\n        }\n        if(dp[i] != -1){\n            return dp[i];\n        }\n        int include, exclude;\n        include = exclude = 0;\n        if(nums[i] <= x){\n            include = 1 + helper( i-2, nums, x, dp);\n        }\n        exclude = helper( i-1, nums, x, dp);\n        return dp[i] = max( include, exclude);\n    }\n    bool predicate(vector<int> &nums,int k,int x){\n        int n = nums.size();\n        vector<int> dp(n,-1);\n        // dp[i] : maximum number of non adjacent houses that can be robbed from nums(0...i) \n        // and each robbed houses must be lesser than equal to x\n        helper( n-1, nums, x, dp);\n        return dp[n-1] >= k;\n    }\n    int minCapability(vector<int>& nums, int k) {\n        int l = INT_MAX;\n        int r = INT_MIN;\n        for(int num : nums){\n            l = min( l, num);\n            r = max( r, num);\n        }\n        int m;\n        int ans = -1;\n        while(l <= r){\n            m = l + (r-l)/2;\n            if(predicate( nums, k, m)){\n                ans = m;\n                r = m-1;\n            }else{\n                l = m+1;\n            }\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'C++']