Minimize the Largest Value When Picking at Least k Non-Adjacent Houses
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A row of houses stands along a street, and `nums[i]` is the amount of money in house `i`. A robber will rob **at least** `k` houses but never two adjacent houses: any two chosen indices must differ by at least 2. The **capability** of a chosen set of houses is the largest amount held by any house in that set.
Return the minimum capability over all valid ways to choose at least `k` non-adjacent houses.
### Function Signature
```python
def min_capability(nums: list[int], k: int) -> int:
```
### Rules
- A valid choice is any set of indices of size at least `k` in which no two indices are consecutive.
- The capability of a valid choice is `max(nums[i] for i in chosen)`.
- The answer is the smallest capability over all valid choices, which is a single integer.
### Constraints
- `1 <= len(nums) <= 100000`
- `1 <= nums[i] <= 10^9` (every value fits in a signed 32-bit integer)
- `1 <= k <= (len(nums) + 1) // 2`, so at least one valid choice always exists.
### Examples
**Example 1**
Input: `nums = [2, 3, 5, 9]`, `k = 2`
Output: `5`
Explanation: the valid choices are `{0, 2}`, `{0, 3}`, and `{1, 3}` (no 3 houses among 4 can be pairwise non-adjacent). Their capabilities are 5, 9, and 9, so the minimum is 5.
**Example 2**
Input: `nums = [2, 7, 9, 3, 1]`, `k = 2`
Output: `2`
Explanation: robbing houses 0 and 4 gives capability `max(2, 1) = 2`. Capability 1 is impossible because only house 4 holds at most 1.
**Example 3**
Input: `nums = [5, 1, 5]`, `k = 2`
Output: `5`
Explanation: the only valid choice of at least 2 houses is `{0, 2}`, whose capability is 5.
Overview: Pick at least k houses from a row without choosing two neighbors, so that the largest amount in any chosen house is as small as possible, and return that minimum. With up to 100,000 houses and values up to one billion, the task tests reasoning about a min-max objective under an adjacency constraint.
A row of houses stands along a street, and `nums[i]` is the amount of money in house `i`. A robber will rob **at least** `k` houses but never two adjacent houses: any two chosen indices must differ by at least 2. The **capability** of a chosen set of houses is the largest amount held by any house in that set.
Implement `min_capability(nums, k)`, which returns the minimum capability over all valid ways to choose at least `k` non-adjacent houses.
### Rules
- A valid choice is any set of indices of size at least `k` in which no two indices are consecutive.
- The capability of a valid choice is `max(nums[i] for i in chosen)`.
- The answer is the smallest capability over all valid choices, which is a single integer.
### Constraints
- `1 <= len(nums) <= 100000`
- `1 <= nums[i] <= 10^9` (every value fits in a signed 32-bit integer)
- `1 <= k <= (len(nums) + 1) // 2`, so at least one valid choice always exists.
- No input value and no answer exceeds 2^31 - 1, so a 32-bit `int` is sufficient in Java and C++.
### Example 1
Input: `nums = [2, 3, 5, 9]`, `k = 2`
Output: `5`
Explanation: the valid choices are `{0, 2}`, `{0, 3}`, and `{1, 3}` (no 3 houses among 4 can be pairwise non-adjacent). Their capabilities are 5, 9, and 9, so the minimum is 5.
### Example 2
Input: `nums = [2, 7, 9, 3, 1]`, `k = 2`
Output: `2`
Explanation: robbing houses 0 and 4 gives capability `max(2, 1) = 2`. Capability 1 is impossible because only house 4 holds at most 1.
Constraints
- 1 <= len(nums) <= 100000
- 1 <= nums[i] <= 10^9 (every value fits in a signed 32-bit integer)
- 1 <= k <= (len(nums) + 1) // 2, so at least one valid choice always exists
- No input value and no answer exceeds 2^31 - 1, so a 32-bit int is sufficient in Java and C++
Examples
Input: ([2, 3, 5, 9], 2)
Expected Output: 5
Explanation: Source example 1: choices {0,2}, {0,3}, {1,3} have capabilities 5, 9, 9.
Input: ([2, 7, 9, 3, 1], 2)
Expected Output: 2
Explanation: Source example 2: houses 0 and 4 give capability 2; only house 4 holds at most 1.
Hints
- The capability of any choice is the amount in one of its houses, so the answer is always one of the values in nums.
- Any valid choice of more than k houses contains a valid choice of exactly k houses whose capability is no larger.
- Two small amounts in adjacent houses cannot both be robbed, so the answer can be larger than the k-th smallest amount.