Get started

House Robber IV — Medium Problem & Solution

A robber will not rob two adjacent houses. The capability of a robbery is the largest amount taken from any single house.

Problem statement

A robber will not rob two adjacent houses. The capability of a robbery is the largest amount taken from any single house.

Given that the robber steals from at least k houses, return the minimum possible capability.

Example 1

Input: nums = [2,3,5,9], k = 2
Output: 5
Explanation: Robbing houses 0 and 2 caps at 5.

Example 2

Input: nums = [2,7,9,3,1], k = 2
Output: 2
Explanation: Houses 0 and 4 both hold at most 2.

Example 3

Input: nums = [1,2,3,4,5,6], k = 3
Output: 5

Constraints

  • 1 <= nums.length <= 100000
  • 1 <= nums[i] <= 1000000000
  • 1 <= k <= (nums.length + 1) / 2

How to solve House Robber IV

Binary search the capability. For a fixed c, the houses holding at most c are known, and the question becomes how many non-adjacent ones can be chosen — a greedy left-to-right sweep answers it exactly.

Approach

  1. Search c over [min(nums), max(nums)].
  2. can(c): walk the array; when nums[i] <= c, take it and jump two, otherwise advance one. Feasible when at least k houses are taken.
  3. Return the smallest feasible c.

Why it works

Taking an eligible house as early as possible is optimal: any selection can be shifted left house by house without reducing its size, since skipping an eligible house only frees a slot that the next choice could have used anyway. Raising c makes more houses eligible, which can only raise the count — the monotonicity the search needs.

Complexity

  • Time — O(n log V)
  • Space — O(1)

Pitfalls

  • Jumping by 2 is what enforces non-adjacency; jumping by 1 after taking a house allows neighbours.
  • The search range must start at the minimum, not at 0 — any capability below it admits nothing.
  • This is not the classic maximum-sum House Robber; the objective is a minimax.

Reference solution

Python

from typing import List

def minCapability(nums: List[int], k: int) -> int:
    lo, hi = min(nums), max(nums)

    def can(cap: int) -> bool:
        cnt, i = 0, 0
        while i < len(nums):
            if nums[i] <= cap:
                cnt += 1
                i += 2
            else:
                i += 1
        return cnt >= k

    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var minCapability = function(nums, k) {
    var lo = nums[0], hi = nums[0], i;
    for (i = 1; i < nums.length; i++) {
        if (nums[i] < lo) lo = nums[i];
        if (nums[i] > hi) hi = nums[i];
    }
    var can = function(cap) {
        var cnt = 0, j = 0;
        while (j < nums.length) {
            if (nums[j] <= cap) { cnt++; j += 2; } else j++;
        }
        return cnt >= k;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (can(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue