Katkat
Back

Minimize the Largest Value When Picking at Least k Non-Adjacent Houses

MicrosoftSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

Return the minimum capability over all valid ways to choose at least k non-adjacent houses.

Function Signature

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.