House Robber IV

medium binary search greedy array

Problem

A robber must steal from at least k houses but never two adjacent ones. His capability for a plan is the maximum amount taken from any single robbed house. Given nums, where nums[i] is the money in house i, return the minimum possible capability over every valid plan that robs at least k houses.

Inputnums = [2,3,5,9], k = 2

Output5

Robbing indices 0 and 2 gives capability max(2, 5) = 5, the smallest achievable.

Inputnums = [2,7,9,3,1], k = 2

Output2

Robbing indices 0 and 4 gives capability max(2, 1) = 2.

nums (comma-separated)

def min_capability(nums, k):
    lo, hi = min(nums), max(nums)
    def feasible(cap):
        taken, i = 0, 0
        while i < len(nums):
            if nums[i] <= cap:
                taken += 1
                i += 2
            else:
                i += 1
        return taken >= k
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

function minCapability(nums, k) {
  let lo = Math.min(...nums), hi = Math.max(...nums);
  const feasible = (cap) => {
    let taken = 0, i = 0;
    while (i < nums.length) {
      if (nums[i] <= cap) { taken++; i += 2; }
      else { i += 1; }
    }
    return taken >= k;
  };
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

int minCapability(int[] nums, int k) {
    int lo = Integer.MAX_VALUE, hi = 0;
    for (int v : nums) { lo = Math.min(lo, v); hi = Math.max(hi, v); }
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        int taken = 0, i = 0;
        while (i < nums.length) {
            if (nums[i] <= mid) { taken++; i += 2; }
            else { i += 1; }
        }
        if (taken >= k) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int minCapability(vector<int>& nums, int k) {
    int lo = INT_MAX, hi = 0;
    for (int v : nums) { lo = min(lo, v); hi = max(hi, v); }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int taken = 0, i = 0;
        while (i < (int)nums.size()) {
            if (nums[i] <= mid) { taken++; i += 2; }
            else { i += 1; }
        }
        if (taken >= k) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Explanation

The capability is the largest value among robbed houses, so the answer is always one of the values in nums, and it lies between min(nums) and max(nums). Instead of enumerating subsets, we binary search on the answer: we look for the smallest capability cap that lets us legally rob at least k houses.

The key insight is monotonicity. If a capability cap works, any larger capability also works (a bigger budget only adds more eligible houses). So the set of feasible capabilities is an upper range, and we can binary search for its left boundary.

To test a candidate cap, run a greedy feasibility check: scan left to right; whenever a house has nums[i] <= cap we rob it and jump two indices ahead (skipping its neighbor), otherwise we move one index ahead. Robbing every eligible house as early as possible maximizes the count, so if this greedy count reaches k the capability is feasible.

Each binary-search step halves the range [lo, hi]. If mid is feasible we tighten hi = mid (try smaller); otherwise lo = mid + 1. When lo == hi that value is the minimum feasible capability.

For nums = [2,3,5,9], k = 2: the search starts on [2, 9]. cap = 5 is feasible (rob houses 0 and 2), cap = 3 and cap = 4 are not (only one eligible house), and the range collapses to 5.

Time: O(n · log(max nums)) Space: O(1)