From TLE using DP to 100% fast using Binary Search
Intuition for DP\nI think without looking at the constraints, the first idea that comes to mind is to check all the scenarios and return the best one, i.e., DP.
# Intuition for DP\nI think without looking at the constraints, the first idea that comes to mind is to check all the scenarios and return the best one, i.e., DP.\n\n# Approach\nTo implement DP we first come up with the recurrance relation, we have a choice to make on each index, we can either take the element or skip it. If we take the element, we need to skip the next element. Also, we need to return the maximum element of the selected minimum sum subsequence so we can have:\n```\n    // this helps in finding the maximum element is the subsequence\n    int take = max(nums[i], f(i+2, k-1));\n    int not_take = f(i+1, k);\n    // this helps is selecting the minimum sum subsequence\n    return min(take, not_take);\n```\n\n# Complexity\n- Time complexity:\nO(n * k)\n\n- Space complexity:\nO(n * k)\n\n# Code\n```\nclass Solution {\npublic:\n    int f(int i, vector<int>& nums, int k, vector<vector<int> > &dp) {\n        if (k == 0)\n            return 0;\n        if (i>=nums.size()) return INT_MAX;\n        if (dp[i][k] != -1) return dp[i][k];\n\n        int take = max(nums[i], f(i+2, nums, k-1, dp));\n        int not_take = f(i+1, nums, k, dp);\n        return dp[i][k] = min(take, not_take);\n    }\n    int minCapability(vector<int>& nums, int k) {\n        vector<vector<int> > dp(nums.size(), vector<int>(k+1, -1));\n        return f(0, nums, k, dp);\n    }\n};\n```\n# Intution for Binary Search\nAfter looking at the constraints we know that we need a solution with **O(n * logn)** or better TC, thus DP will be too expensive and will give TLE. Moreover, if we read carefully we can observe that the question asks to find the "***minimum capability of the robber to steal at least k houses***", this is a central idea in binary search, as we need to find minimum possible value of capability from a range of values, we should start thinking of applying BS on capability.\n\n# Approach for Binary Search\nWe can observe that the range of our answer(capability) will be from 1 to 1e9. We can simply check for each of these values starting from 1, whether it is possible to have at least k elements with current value as the minimum capability. To improve the TC, we can simply use BS. We first need to write the helper function which will tell us if it is possible to select at least "k" elements with current capability as minimum. If the answer is "yes", we look for a lower value of capability, if not, we search for a higher one.\n\nAlso note that this helper function can pick the element if is lower or equal to the current capability, greedily! We can observe that using simple cases for n<5. Mathematically, we can prove this works using induction on n.\n\n# Complexity\n- Time complexity:\nO(n * log n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution {\npublic:\n    bool isPossible(int m, vector<int>& nums, int k) {\n        int i=0;\n        while (i<nums.size()) {\n            if (nums[i] <= m) {\n                i+=2;\n                k--;\n            }\n            else i++;\n\n            if (k==0) return true;\n        }\n        return false;\n    }\n    int minCapability(vector<int>& nums, int k) {\n        int l = 1, r = *max_element(nums.begin(), nums.end());\n        \n        while (l<r) {\n            int m = (l + r) / 2;\n            if (isPossible(m, nums, k))\n                r = m;\n            else\n                l = m+1;\n        }\n        return r;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Greedy', 'C++']