0025MediumArrayBinary Search

Deviation Value Span

Tracked in this browser only

Trains the technique from

LeetCode 34Find First and Last Position of Element in Sorted Array

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.

A machine shop keeps an archive of how far finished parts drifted from a reference line, measured in tenths of a millimetre. A part on the long side of the line records a positive drift and a part on the short side records a negative one.

The archive readings is filed from smallest drift to largest, never decreasing as you move forward. Any drift may be filed more than once, because different parts can miss the line by the very same amount. Because the filing is ordered, all copies of one drift sit shoulder to shoulder in a single unbroken run.

Given the archive and one drift value, report where that run begins and where it ends: return [first, last], the lowest index holding value and the highest index holding value. When the archive holds no copy of value at all, return [-1, -1] instead.

The archive can grow to a hundred thousand readings and may also be completely empty. Each answer has to be produced in time that grows only with the logarithm of the archive size, so stepping through the readings one after another is not fast enough.

Examples

Example 1

Input: readings = [-4, -1, -1, -1, 3, 7], value = -1
Output: [1, 3]

Three parts drifted -1 tenths and they occupy indices 1, 2 and 3. Index 0 holds a smaller drift and index 4 already holds a larger one.

Example 2

Input: readings = [-4, -1, 3], value = 5
Output: [-1, -1]

A drift of 5 would belong between 3 and the end of the archive, but no part actually recorded it, so the absent marker is returned.

Example 3

Input: readings = [2, 2, 2], value = 2
Output: [0, 2]

Every filed part drifted the same amount, so the run stretches from the first index to the last.

Constraints

0 <= readings.length <= 10^5
-10^9 <= readings[i] <= 10^9
readings is filed in non-decreasing order
-10^9 <= value <= 10^9
The lookup must run in O(log n) time

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 value_span(readings: list[int], value: int) -> list[int]:

Java

public int[] valueSpan(int[] readings, int value)

The intended approach

Time O(log n)Space O(1)

Use one helper that halves the archive to find the leftmost index where a given drift could be inserted while keeping the order. Calling it with `value` lands on the first copy if one exists, which also settles presence: if that index runs off the end or holds a different drift, nothing matches. Calling it with `value + 1` lands just past the final copy, so one less than that index is the last copy. Two halving searches means two logarithmic passes and no extra storage.

Pythonentry point: value_span

def value_span(readings, value):
    def first_at_least(bound):
        low = 0
        high = len(readings)
        while low < high:
            mid = (low + high) // 2
            if readings[mid] < bound:
                low = mid + 1
            else:
                high = mid
        return low

    start = first_at_least(value)
    if start == len(readings) or readings[start] != value:
        return [-1, -1]
    end = first_at_least(value + 1) - 1
    return [start, end]

The obvious version

Walk the archive from index 0, remembering the first and the last index whose reading equals the wanted drift. O(n) with no halving at all.

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_value_span(readings, value):
    first = -1
    last = -1
    for i in range(len(readings)):
        if readings[i] == value:
            if first == -1:
                first = i
            last = i
    return [first, last]

How this problem was checked

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