House robber iv

Array Binary Search Dynamic Programming Greedy

64.8% acceptance

Feb 25, 2026

1706

102

There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes. The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed. You are given an integer array nums representing how much money is stashed in each house. More formally, the ith house from the left has nums[i] dollars. You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses. Return the minimum capability of the robber out of all the possible ways to steal at least k houses.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_capability(nums: Vec<i32>, k: i32) -> i32 {
    // Binary search on capability cap
    // For a given cap, greedily count max houses robbed with value <= cap (no adjacent)
    let can_rob = |cap: i32| -> bool {
      let mut count = 0;
      let mut i = 0;
      while i < nums.len() {
        if nums[i] <= cap {
          count += 1;
          i += 2; // skip adjacent
        } else {
          i += 1;
        }
      }
      count >= k
    };
    let mut lo = *nums.iter().min().unwrap();
    let mut hi = *nums.iter().max().unwrap();
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if can_rob(mid) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}