0066EasyArrayBinary Search

Threshold Insert Slot

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.

An alerting service keeps its trigger levels in thresholds, an array of distinct integers held in increasing order. Slots are numbered from 0.

An operator wants to add the trigger level level. Report where it belongs:

if level is already one of the stored trigger levels, report the slot it currently occupies;
otherwise report the slot level would occupy after being inserted, with every later trigger level shifting one slot along so the array stays in increasing order. A level above every stored trigger level therefore belongs at slot thresholds.length.

Scanning the array end to end is too slow for the service. Your routine has to finish in time logarithmic in the length of thresholds.

Examples

Example 1

Input: thresholds = [-40, -12, 5, 18, 63], level = 18
Output: 3

The level 18 is already stored at slot 3, so that slot is reported.

Example 2

Input: thresholds = [-40, -12, 5, 18, 63], level = 6
Output: 3

Inserting 6 pushes 18 and 63 one slot along, so 6 lands at slot 3.

Example 3

Input: thresholds = [-40, -12, 5, 18, 63], level = 90
Output: 5

Every stored level is below 90, so it is appended one past the last slot.

Constraints

1 <= thresholds.length <= 10^4
-10^4 <= thresholds[i] <= 10^4
thresholds holds distinct integers in increasing order
-10^4 <= level <= 10^4

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 insert_slot(thresholds: list[int], level: int) -> int:

Java

public int insertSlot(int[] thresholds, int level)

The intended approach

Time O(log n)Space O(1)

The answer is the count of stored levels strictly below `level`, which is also the slot of the first entry that is at least `level`. Keep a half-open window `[lo, hi)` of candidate slots over `0 .. thresholds.length`, and each step either discard the lower half when the midpoint is still below `level` or pull `hi` down to the midpoint otherwise; the window collapses onto that first slot, and it collapses onto `thresholds.length` when no entry qualifies.

Pythonentry point: insert_slot

def insert_slot(thresholds, level):
    lo = 0
    hi = len(thresholds)
    while lo < hi:
        mid = (lo + hi) // 2
        if thresholds[mid] < level:
            lo = mid + 1
        else:
            hi = mid
    return lo

The obvious version

Walk the array from slot 0 and stop at the first entry that is not below the level; if none qualifies the level belongs one past the end.

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_insert_slot(thresholds, level):
    for slot, stored in enumerate(thresholds):
        if stored >= level:
            return slot
    return len(thresholds)

How this problem was checked

Reference solution executed against 12 test cases — 12 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