House Robber IV

Medium
826.

House Robber IV

House Robber IV is a medium coding problem on arrays, greedy and binary search, asked in Amazon, Google, Sprinklr and Arcesium interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minCapability = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

House Robber IV — Solution in Python, Java & C++

House Robber IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and greedy.

House Robber IV is a medium coding problem on arrays, greedy and binary search, asked in Amazon, Google, Sprinklr and Arcesium interviews.

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

Hints for House Robber IV

  1. Hint 1

    If a capability c allows k houses, so does any larger c — the feasibility is monotone.

  2. Hint 2

    Binary search c; for a candidate, count how many non-adjacent houses hold at most c.

  3. Hint 3

    The greedy left-to-right count is optimal: take a house whenever you can.

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

Java

private static boolean canRob(int[] nums, int k, int cap) {
    int cnt = 0, i = 0;
    while (i < nums.length) {
        if (nums[i] <= cap) {
            cnt++;
            i += 2;
        } else {
            i++;
        }
    }
    return cnt >= k;
}

public static int minCapability(int[] nums, int k) {
    int lo = nums[0], hi = nums[0];
    for (int x : nums) {
        lo = Math.min(lo, x);
        hi = Math.max(hi, x);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canRob(nums, k, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

C++

static bool canRob(vector<int>& nums, int k, int cap) {
    int cnt = 0, i = 0;
    while (i < (int) nums.size()) {
        if (nums[i] <= cap) {
            cnt++;
            i += 2;
        } else {
            i++;
        }
    }
    return cnt >= k;
}

int minCapability(vector<int>& nums, int k) {
    int lo = nums[0], hi = nums[0];
    for (int x : nums) {
        lo = min(lo, x);
        hi = max(hi, x);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canRob(nums, k, 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms