Brute Force To Binary Search full explanation | Beginner Friendly | Easy to Understand
Intuition (Brute Force)\nWhat we need to do?\nWe need the min capability and also the capability is the max element he could rob from the array.\nSo the capabil
# Intuition (Brute Force)\nWhat we need to do?\nWe need the min capability and also the capability is the max element he could rob from the array.\nSo the capability/ans will be any one element from the array.\nSo we can just check each element if it is my ans or not.\n\n**HOW?**\nFor any element to be my ans, there must be k-1 valid robberies in the array.\n\n***What are valid robberies?***\n1. The element must be less than or equal to my selected element, that is if we are checking for say nums[i], then element must be less than or equal to nums[i].\n    Why?\n    Because I want my selected element to be the max element.\n2. Since adjacent elements can not be robbed, valid robbery won\'t have adjacent elements.\n\nIf any element can pass both this condition, that means this can be my ans. So we can simply do\n```\nif(check(nums[i], nums, k)){\n    ans = Math.min(ans, nums[i]);\n}\n```\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Understanding the check function**\nIf we want nums[i] to be my ans, this nums[i] must be my max element among k valid robbery.\nSo we can have a variable cnt, that will be the count of valid robberies.\nAnd since there is a factor of adjacent indexes, we will also have a variable prev which tells us the index of previously taken element, so that we won\'t be able to take any adjacent element of prev.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nIt would be O(n^2) solution since for every element we are iterating the array.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1) // since no extra space used.\n\n# Code (Brute Force)\n```\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        int ans = Integer.MAX_VALUE;\n        for(int i=0; i<nums.length; i++){\n            if(func(nums[i], k, nums)){\n                ans = Math.min(ans, nums[i]);\n            }\n        }\n    }\n\n    public boolean func(int max, int k, int[] nums){\n        int cnt = 0, prev = -1;\n        for(int i=0; i<nums.length; i++){\n            if(nums[i] > max || (prev != -1 && i == prev+1 || i == prev-1) ){\n                continue; \n            }else{\n                prev = i;\n                cnt++;\n            }\n        }\n\n        return cnt >= k;\n    }\n}\n```\n\n# Binary Search Approach\nFrom the brute force approach we got how to check if my curr element is valid or not, we just need to find a way of getting the element is logn time.\nIf we carefully observe, we can following observations --\n1. My maximum ans can be the maximum element of my array, since that will be the maximum capability robber can have.\n2. Also if my robber can have capability of 6 then we can also have capability of 7,8,9 and so on, because if he has capability of 6 then there must be k element >= 6,then obviously there will be k elements >= 7,8,9,etc.\n3. Similarly if there are not k elements >= 3 then there will never be k elements >= 2,1 and so on..\n4. From this we can have a binary search intution.\n\n# Approach\nWe can do binary search on ans, where ans can be in the range of [1, max(nums)], if my mid is valid then my mid can be my ans, but we will go further left to get any smaller ans, else move right to get a valid ans.\nOur check function will be the same.\n\n# Time Complexity\nO(nlogn)\nO(n) for every check that we do, for each mid and (logn) for binary search.\n\n\n# Code\n```\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        int low = 1, high = 0;\n\n        for(int i=0; i<nums.length; i++){\n            high = Math.max(high, nums[i]);\n        }\n\n        while(low < high){\n            int mid = low + (high-low)/2;\n\n            if(func(mid, k, nums)){\n                high = mid;\n            }else{\n                low = mid+1;\n            }\n        }\n\n        return high;\n    }\n\n    public boolean func(int max, int k, int[] nums){\n        int cnt = 0, prev = -1;\n        for(int i=0; i<nums.length; i++){\n            if(nums[i] > max || (prev != -1 && i == prev+1 || i == prev-1) ){\n                continue; \n            }else{\n                prev = i;\n                cnt++;\n            }\n        }\n\n        return cnt >= k;\n    }\n}\n```
['Binary Search', 'Java']