C/C++ Explained || Binary Search + Greedy or DP || Beats 100% || nlog(m) time, O(1) space
Explanation\nThe problem has essentially asked us to find the $k$-element subset, $S$, of nums such that $\max(S)$ (the capability) is minimized and no two elem
# Explanation\nThe problem has essentially asked us to find the $k$-element subset, $S$, of ```nums``` such that $\\max(S)$ (the capability) is minimized and no two elements of the subset are adjacent to $\\max(S)$ in ```nums``` (we\'ll call a set with the latter property an independent set). \n\nWe know that we can limit our search to the range $[min($```nums```$), max($```nums```$)]$ since the minimum capability is necessarily in ```nums```. From here, all we need to do is find the minimal $n \\in [min($```nums```$), max($```nums```$)]$ such that $n$ is the maximum of some $k$-element independent subset of ```nums```. We accomplish this by performing a binary search on the specified range. In each step of the binary search, we place an upper bound on the capability of any independent subset of `nums`. In other words, for some considered $n$ in the binary search, we check if there exists a $k$-element independent subset of `nums` whose capability is upper bounded by $n$. If such an independent set of $k$ elements exists, then we need only search the left half of our current range for a potentially smaller capability. Otherwise, we search the right half of our current range since there is clearly no value $m$ smaller than $n$ such that $m$ is greater than or equal to the maximum of a $k$-element independent subset of ```nums``` (since such a $k$-element independent subset would\'ve been found when considering $n$). Just to make sure, you must understand that each step of the binary search places an UPPER BOUND, $n$, on the capability of each $k$-element independent subset of `nums`, however, discovering that such a subset exists does not mean that $n$ is a valid capability under the constrain of $k$. Let\'s look at an example to make this clear: suppose `nums = [3,9,2,5,1]` and $k = 3$. The minimum capability of `nums` is `3`. However, notice that the first $n$ considered during our binary search will be $5$. We will find that there exists a $k$-element independent set with a capability less than $5$, namely $\\{3,2,1\\}$, however, this does not mean $5$ is a valid capability of `nums` even though $5$ is in `nums` (there is no independent set of $3$ elements less than $5$ in `nums`).\n\nOne step that was brushed over was checking if for some $n$, there exists a $k$-element independent subset of `nums` with a capability upper bounded by $n$. To do this check, we will construct the largest possible independent subset of `nums` with a capability less than or equal to $n$ and determine if it has a size of at least $k$. One way to approach this is to derive a recurrence and apply dynamic programming. If for some $n$ we let $dp(i)$ denote the largest independent subset with capability less than $n$ and elements in the subarray `nums[0,...,i]`, then `dp(i) = max(dp(i - 1), ((nums[i] <= n) ? 1 : 0) + dp(i - 2))` because we can either choose to include the current element in the $k$-element independent subset or not (given that the current element is upper bounded by $n$). It\'s possible to implement this as a constant space dynamic programming problem, but we can also just choose elements greedily for our $k$-element independent subset with capability less than $n$. Here\'s why: suppose we iterate over `nums` and find an element `nums[i]` such that `nums[i] <= n`. If `nums[i + 1] > n`, we can just add `nums[i]` to our set. But if `nums[i + 1] <= n`, how do we know to add `nums[i]` or `nums[i + 1]` to our set? Could adding `nums[i]` to our set lead to a worse solution than adding `nums[i + 1]`. It turns out that choosing `nums[i]` is always at least as good as choosing `nums[i + 1]`. I won\'t write a formal proof for this, but think of it this way: if we choose `nums[i]` or `nums[i + 1]`, the size of our set increases by $1$ either way, however, suppose `nums[i + 2] <= n`, then by choosing `nums[i + 1]`, we lose the possibility of adding `nums[i + 2]` to our set whereas if we choose `nums[i]`, we can also add `nums[i + 2]` to our set.\n\n\n# Complexity\n- Time complexity:\n$$O(n \\cdot log(m))$$ where $n$ is the size of `nums` and \n$m$ is $max($`nums`$) - min($`nums`$)$\n\n- Space complexity:\n$$O(1)$$\n\n# Greedy Code\n```\nclass Solution {\npublic:\n    int minCapability(vector<int>& nums, int k) {\n\n        int left, right, mid, subsetLength, n;\n\n        n = nums.size();\n        left = right = nums[0];\n\n        for (int i = 1; i < n; ++i)\n        {\n            if (nums[i] < left) left = nums[i];\n            else if (nums[i] > right) right = nums[i];\n        }\n\n        for (; left < right; )\n        {\n            mid = left + ((right - left) / 2);\n            subsetLength = 0;\n\n            for (int i = 0; i < n && subsetLength < k; ++i)\n                if (nums[i] <= mid)\n                    ++i, ++subsetLength;\n\n            if (subsetLength == k)\n                right = mid;\n            else\n                left = mid + 1;\n        }\n\n        return left;\n    }\n```\n\n# DP Code\n```\nclass Solution {\npublic:\n    int minCapability(vector<int>& nums, int k) {\n\n        int left, right, mid, n;\n\n        n = nums.size();\n        left = right = nums[0];\n\n        for (int i = 1; i < n; ++i)\n        {\n            if (nums[i] < left) left = nums[i];\n            else if (nums[i] > right) right = nums[i];\n        }\n\n        for (; left < right; )\n        {\n            mid = left + ((right - left) / 2);\n\n            int dpOneBack, dpTwoBack;\n\n            if (nums[0] <= mid)\n                dpOneBack = dpTwoBack = 1;\n            else \n            {\n                dpTwoBack = 0;\n                dpOneBack = (nums[1] <= mid) ? 1 : 0;\n            }\n\n            for (int i = 2, tmp; i < n && dpOneBack < k; ++i)\n            {\n                tmp = dpOneBack;\n                dpOneBack = max(dpOneBack, ((nums[i] <= mid) ? 1 : 0) + dpTwoBack);\n                dpTwoBack = tmp;\n            }\n\n            if (dpOneBack == k)\n                right = mid;\n            else\n                left = mid + 1;\n        }\n\n        return left;\n    }\n};\n```
['Binary Search', 'Dynamic Programming', 'Greedy', 'C', 'C++']