Choose at least non-adjacent houses to rob while minimizing the maximum money taken from any robbed house.
You are given an array of integers representing the money in each house arranged in a line, and an integer . You want to rob exactly houses such that no two robbed houses are adjacent.
For any valid selection, define its capability as the maximum amount of money in any robbed house.
Your task is to find the minimum possible capability among all valid selections of exactly non-adjacent houses.
If no valid selection exists, the problem is typically treated as having no feasible answer, but the intended challenge assumes the input allows a solution.
Input Format
- An integer array
numswherenums[i]is the money in the -th house. - An integer
k, the number of houses to rob.
The houses are in a straight line, so adjacent indices cannot both be chosen.
Output Format
- Return the minimum possible capability of a valid selection of exactly
khouses.
Constraints
- Houses are arranged in a line.
- Chosen houses must be non-adjacent.
- Exactly
khouses must be selected. - The optimal value is determined by minimizing the maximum robbed value among the selected houses.
Example 1
Input
nums = [2,3,5,9], k = 2
Output
5
Explanation
With capability 4, you can only take one house with value at most 4. With capability 5, you can take houses 0 and 2 with values 2 and 5, which are non-adjacent. So the minimum possible capability is 5.
Example 2
Input
nums = [2,7,9,3,1], k = 2
Output
2
Explanation
Choose houses with values 2 and 1. They are not adjacent, and the capability is max(2, 1) = 2, which is optimal.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.