0524MediumArrayHash TableSliding Window

Drift Marks Over Sensor Blocks

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.

A calibration log holds readings, the drift each sensor sweep measured. A negative reading means the sweep came out below the reference.

Every block of span consecutive readings gets a drift mark, worked out like this. Take the negative readings in the block and put them in increasing order, keeping repeats. If that ordering holds at least rank readings, the block's drift mark is the rank-th reading in it. Otherwise the block's drift mark is 0.

Return the drift marks of every block, in the order the blocks appear from the start of the log to its end.

Examples

Example 1

Input: readings = [-2, 4, -3, -1, 0, -50, 5], span = 3, rank = 2
Output: [-2, -1, -1, -1, 0]

The first block is [-2, 4, -3]; its negative readings in increasing order are -3 and -2, and the second of those is -2. The last block is [0, -50, 5], which holds only one negative reading, so its mark is 0.

Example 2

Input: readings = [-2, -2, -1, -4], span = 3, rank = 2
Output: [-2, -2]

The block [-2, -2, -1] orders its negative readings as -2, -2, -1, and the second of those is -2. The block [-2, -1, -4] orders them as -4, -2, -1, so its mark is -2 as well.

Example 3

Input: readings = [3, 7, 2, 9], span = 2, rank = 1
Output: [0, 0, 0]

No block holds a negative reading, so every mark is 0.

Constraints

n == readings.length
1 <= n <= 10^5
1 <= span <= n
1 <= rank <= span
-50 <= readings[i] <= 50

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 drift_marks(readings: list[int], span: int, rank: int) -> list[int]:

Java

public int[] driftMarks(int[] readings, int span, int rank)

The intended approach

Time O(n * 50): constant work to slide, then a fifty-bucket scan per block.Space O(1) beyond the returned list of marks.

A reading that matters is one of only fifty values, so keep a tally with one bucket per value from -50 up to -1 and slide it along the log: the arriving reading raises its bucket, and once the block is full the departing reading lowers its own. Reading a mark off the tally means adding bucket sizes from the most negative value upward until the running count reaches `rank`; if it never does, the mark is 0.

Pythonentry point: drift_marks

def drift_marks(readings, span, rank):
    # O(n * 50): only the 50 possible negative values matter, so a tally over
    # those buckets replaces sorting each block.
    counts = [0] * 50
    out = []
    for i in range(len(readings)):
        v = readings[i]
        if v < 0:
            counts[v + 50] += 1
        if i >= span:
            gone = readings[i - span]
            if gone < 0:
                counts[gone + 50] -= 1
        if i >= span - 1:
            seen = 0
            mark = 0
            for b in range(50):
                seen += counts[b]
                if seen >= rank:
                    mark = b - 50
                    break
            out.append(mark)
    return out

The obvious version

Cut out each block in turn, sort its negative readings from scratch, and index the sorted list, falling back to 0 when it is too short.

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_drift_marks(readings, span, rank):
    out = []
    for start in range(len(readings) - span + 1):
        block = readings[start:start + span]
        negs = sorted(v for v in block if v < 0)
        if len(negs) >= rank:
            out.append(negs[rank - 1])
        else:
            out.append(0)
    return out

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