JAVA | Binary Search on answers | Explained ✅
Previous post with one of the best explanations got removed \u2639\uFE0F\n---\n\n\n---\n### Code with commented explanation:\n\nclass Solution {\n    public int
# Previous post with one of the best explanations got removed \u2639\uFE0F\n---\n![image.png](https://assets.leetcode.com/users/images/b770bf6e-40a6-4e07-b7e4-9727b689ba4f_1678915050.242989.png)\n\n---\n### Code with commented explanation:\n```\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        // We don\'t know what our minimum capability is going to be\n        // so we would do a hit and trial on the given range 1 to 10^9\n        // trying a linear search is possible, but that\'d not fit in our constraints\n        // since the range is sorted, we can use binary search\n        // to look for the minimum capability to reduce our runtime\n        int l = 1, r = (int) 1e9;  // initial range\n        while (l < r) {\n            // lets try fixing a min capability = mid\n            int mid = l + (r - l) / 2;\n            // check if its possible to rob atleast k houses by fixing a min capability = mid\n            // if yes, we will try again by decreasing our min capability\n            if (isPossible(nums, mid, k)) { \n                // mid is a candidate so we keep it in our range\n                // if we do r = mid - 1 and say we don\'t get any new candidate in the new range \n                // this mid which could be the answer would be lost\n                r = mid;\n            } \n            // if not, we will fix a min capability more than \'mid\' and try again \n            else {\n                // mid is not a candidate so skip it and take range from after mid\n                l = mid + 1;\n            }\n        }\n        \n        return r;   // return r as it\'d be holding the \'mid\'\n    }\n    \n    private boolean isPossible(int[] nums, int maxMoney, int k) {\n        int houseStolen = 0;    // to count the number of houses we have robbed \n        // we can\'t rob adjacent houses, so we need to keep track of the last index we robbed at\n        int lastStolenIdx = -2;\n        for (int i = 0; i < nums.length; i++) {\n            // if money in current house is more than what we have fixed\n            // we can\'t rob it, otherwise our minimum capability would increase\n            if (nums[i] > maxMoney) {\n                continue;\n            }\n            // we cannot rob the house if we just robbed the previous house\n            if (i == lastStolenIdx + 1) {\n                continue;\n            }\n            \n            // otherwise, we rob\n            houseStolen++;      // number of robbed houses increments\n            lastStolenIdx = i;  // last robbed place is the current index\n        }\n        \n        // return if we have been able to rob atleast k houses\n        return houseStolen >= k;\n    }\n}\n```\n---\n### Clean solution:\n``` java []\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        int l = 1, r = (int) 1e9;  \n        while (l < r) {\n            int mid = l + (r - l) / 2;\n            if (isPossible(nums, mid, k)) { \n                r = mid;\n            } else {\n                l = mid + 1;\n            }\n        }\n        \n        return r;   \n    }\n    \n    private boolean isPossible(int[] nums, int maxMoney, int k) {\n        int houseStolen = 0, lastStolenIdx = -2;\n        for (int i = 0; i < nums.length; i++) {\n            if (nums[i] > maxMoney) {\n                continue;\n            }\n            if (i == lastStolenIdx + 1) {\n                continue;\n            }\n            \n            houseStolen++;    \n            lastStolenIdx = i; \n        }\n        \n        return houseStolen >= k;\n    }\n}\n```\n---\n*The for loop inside* `isPossible()` *can be written this way well:*\n``` java[]\nfor (int i = 0; i < nums.length; i++) {\n    // if money is lesser than minimum capability\n    if (nums[i] <= maxMoney) {  \n        houseStolen++;  // we can rob\n        i++;   // make an extra jump to skip the next house\n    }\n}\n```\n\n---\n#### *Short and simplified solution:*\n``` java []\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        int l = 1, r = (int) 1e9;\n        while (l < r) {\n            int mid = l + (r - l) / 2;\n            int houseStolen = 0;\n            for (int i = 0; i < nums.length; i++) {\n                if (nums[i] <= mid) {\n                    houseStolen++;\n                    i++;\n                }\n            }\n            if (houseStolen >= k) {\n                r = mid;\n            } else {\n                l = mid + 1;\n            }\n        }\n        \n        return r;\n    }\n}\n```\n--- \n### Complexity analysis:\nLet $$n$$ be the size of our search space ($$1$$ -> $$10^9$$) and $$m$$ be the number of houses. \n\nWe are performing a binary search on the search space which would cost $$O(logn)$$ runtime and a thorough looping over the houses which would cost $$O(m)$$ runtime.\n##### Time complexity: $$O(m * logn)$$\n##### Space complexity: $$O(1)$$
['Binary Search', 'Java']