0987MediumArrayBinary SearchDynamic ProgrammingGreedy

Smallest Ceiling for k Non-Neighbouring Picks

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_capability(nums: list[int], k: int) -> int:

Java

public int minCapability(int[] nums, int k)

The intended approach

Time O(n log V) for n readings over a value range V.Space O(1).

Ask the question the other way round: for a given ceiling, how many readings can be picked without taking two in a row, using only readings at or below it? If that count reaches `k` the ceiling works. Raising the ceiling only ever allows more readings, so the smallest workable ceiling can be found by halving the range of reading values. Counting for a candidate ceiling is one greedy pass: walk the readings and take every one at or below the ceiling whose predecessor was not taken. Taking a reading as early as possible is never worse, because skipping it only delays the next chance, so the greedy count is the largest possible. Asking for at least `k` rather than exactly `k` makes no difference to the answer: dropping readings from a pick never raises its ceiling, so any pick of more than `k` can be trimmed back to `k` and the ceiling stays where it was.

Pythonentry point: min_capability

def min_capability(nums, k):
    def fits(ceiling):
        taken = 0
        at = 0
        n = len(nums)
        while at < n:
            if nums[at] <= ceiling:
                taken += 1
                at += 2
            else:
                at += 1
        return taken >= k

    low = min(nums)
    high = max(nums)
    while low < high:
        mid = (low + high) // 2
        if fits(mid):
            high = mid
        else:
            low = mid + 1
    return low

The obvious version

Try every set of readings, keep those taking at least `k` with none next to each other, and take the smallest largest reading among them. Exponential in the reading count and it never asks about a ceiling.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_capability(nums, k):
    n = len(nums)
    best = None
    for mask in range(1 << n):
        ok = True
        taken = 0
        biggest = None
        for i in range(n):
            if not (mask >> i & 1):
                continue
            if i > 0 and (mask >> (i - 1) & 1):
                ok = False
                break
            taken += 1
            if biggest is None or nums[i] > biggest:
                biggest = nums[i]
        if not ok or taken < k:
            continue
        if best is None or biggest < best:
            best = biggest
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in