🔥 Binary Search + Greedy
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nsee code\n\n# Complexit
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nsee code\n\n# Complexity\n- Time complexity: O(nlog(10e9)) ~ O(30(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java\nclass Solution {\n    public int minCapability(int[] a, int k) {\n        int n = a.length;\n        int l = a[0], r = a[0]; // left and right bound for binary search\n\n        for (int x : a) {\n            l = Math.min(l, x);\n            r = Math.max(r, x);\n        }\n\n        while (l < r) { // straight forward binary search logic for min valid value\n            int m = l + (r-l)/2;\n            if (valid(a, m, k)) r = m;\n            else l = m + 1;\n        }\n\n        return l; // when search ends l == r, could return either one\n    }\n\n    private boolean valid(int[] a, int m, int k) {\n        for (int i = 0; i < a.length; ) {\n            if (a[i] <= m) { // will hit ith house, GREEDY\n                if (--k == 0) return true; // hit enough of k houses\n                i += 2; // if this one is taken, stip next\n            } else i++; // if this one is not taken, move on to next\n        }\n\n        return false; // fail to hit k houses\n    }\n}\n```
['Binary Search', 'Greedy', 'Java']