Show problems as
Classic problem #2560MediumArrayBinary SearchDynamic ProgrammingGreedy

House Robber IV

Real-world version: Smallest Ceiling for k Non-Neighbouring Picks
Tracked in this browser only
Read House Robber IV on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Readings are given as nums. A pick takes at least k of them, and no two picked readings may sit next to each other in the list.

A pick's ceiling is the largest reading it takes. Return the smallest ceiling any pick can have.

Examples

Example 1

Input
nums = [14, 3, 27, 9, 41, 6], k = 2
Output
6

The readings 3 and 6 sit at positions 1 and 5, so they are not next to each other, and taking them gives a ceiling of 6. A ceiling of 3 leaves only the single reading 3 available, which is one short of the two wanted.

Example 2

Input
nums = [1000000000, 1, 1000000000], k = 2
Output
1000000000

Two readings must be taken and the only non-neighbouring pair is the two ends, both a billion.

Example 3

Input
nums = [1, 1, 1, 1, 1], k = 3
Output
1

Every reading is 1, and three can be taken at positions 0, 2 and 4.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= (nums.length + 1) / 2

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_capability(nums: list[int], k: int) -> int:
Java
public int minCapability(int[] nums, int k)

More on the same topics