Two approaches | backtracking | binary search(optimal) | beats 71% |
Solution 1: Backtracking (TLE)Approach & IntuitionThis solution tries all possible ways to select k houses while ensuring that no two adjacent houses are picked
# Solution 1: Backtracking (TLE)

# Approach & Intuition
This solution tries all possible ways to select k houses while ensuring that no two adjacent houses are picked. It stores the maximum amount stolen in each valid selection in a list and then returns the minimum of those maximum values.

# Complexity
- Time complexity: O(2ⁿ × k) 
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(k)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public int minCapability(int[] nums, int k) {
        int n=nums.length;
        List<Integer> l1=new ArrayList<>();
        helper(nums,k,0,l1,new ArrayList<>());
        return min(l1);

    }
    public static void helper(int [] nums,int k,int idx,List<Integer> l1,List<Integer> l2){
        if(l2.size()==k){
            int maxval=max(l2);
            l1.add(maxval);
            return;
        }
        for(int i=idx;i<nums.length;i++){
            l2.add(nums[i]);
            helper(nums,k,i+2,l1,l2);
            l2.remove(l2.size()-1);
        }
    } 
    public static int max(List<Integer> l1){
        int max=l1.get(0);
        int n=l1.size();
        for(int i=1;i<n;i++){
            max=Math.max(l1.get(i),max);
        }
        return max;
    }
    public static int min(List<Integer> l1){
        int min=l1.get(0);
        int n=l1.size();
        for(int i=1;i<n;i++){
            min=Math.min(l1.get(i),min);
        }
        return min;
    }
}

```
# Why Does This Solution Get TLE?
It explores all subsets of k houses while ensuring non-adjacent selection.
Since we can either pick or skip a house, the recursion tree grows exponentially.
For n houses, the worst-case number of recursive calls is O(2ⁿ).
Even for moderate values of n (≈ 30-40), this approach becomes too slow.


# Solution 2: Binary Search on Capability (Optimized)

# Approach & Intuition
Instead of generating all valid ways, we use binary search on the capability value to find the minimum maximum house value the robber can rob.

# Complexity Analysis
Time Complexity: O(n log max(nums))

Space Complexity: O(1)

```java []
class Solution {
    public int minCapability(int[] nums, int k) {
        int n=nums.length;
        int lo=min(nums,n);
        int hi=max(nums,n);
        int ans=lo;
        while(lo<=hi){
            int mid=lo+(hi-lo)/2;
            if(is_it_possible(nums,k,mid)){
                ans=mid;
                hi=mid-1;
            }
            else{
                lo=mid+1;
            }
        }
        return ans;
    }
    public static boolean is_it_possible(int [] arr,int k,int mid){
        int count=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]<=mid){
                count++;
                i++;
            }
            if(count>=k){
                return true;
            }
        }
        return false;
    }
    public static int max(int [] arr,int n){
        int max=arr[0];
        for(int i=0;i<n;i++){
            max=Math.max(arr[i],max);
        }
        return max;
    }
    public static int min(int [] arr,int n){
        int min=arr[0];
        for(int i=0;i<n;i++){
            min=Math.min(arr[i],min);
        }
        return min;
    }
}
```
![upvote.jpeg](https://assets.leetcode.com/users/images/68f364b0-e9c6-4069-a180-1507571daa72_1742016149.7122638.jpeg)






['Array', 'Binary Search', 'Backtracking', 'Recursion', 'Java']