0023HardArrayQueueSliding WindowMonotonic Queue

Rolling Peak Readings

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 weather mast logs one temperature per minute for an entire shift. readings[i] is the whole-degree Celsius value captured during minute i; anything below freezing is negative.

The report generator studies blocks of span back-to-back minutes. The first block covers minutes 0 through span - 1. Each following block starts one minute later than the one before it, and the last block is the one whose final minute is the final minute of the shift. For every block the generator keeps a single number: the largest reading anywhere inside that block.

Return those block peaks, listed in the same order the blocks were studied. For n readings and a block of span minutes there are n - span + 1 peaks to report.

span is never smaller than 1 and never larger than the number of readings, so there is always at least one block. When span is 1 each block is a single minute, and when span equals the number of readings there is exactly one block covering the whole shift.

Examples

Example 1

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

Five blocks of three minutes fit in seven readings. The two sixes keep the peak at 6 for the first four blocks, and once both have dropped out of view the last block peaks at 7.

Example 2

Input: readings = [9, 5, 1], span = 1
Output: [9, 5, 1]

Every block is one minute long, so each reading is its own peak and the output copies the input.

Example 3

Input: readings = [-8, -2, -5, -9], span = 4
Output: [-2]

The block width matches the shift length, so a single block covers all four minutes and its warmest reading is -2 degrees.

Constraints

1 <= readings.length <= 10^5
-10^4 <= readings[i] <= 10^4
1 <= span <= readings.length

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

Java

public int[] rollingPeaks(int[] readings, int span)

The intended approach

Time O(n)Space O(span)

Hold indices in a deque whose readings decrease from front to back, so the front is always the peak of the current block. Before pushing a new index, discard every index at the back whose reading is no larger than the incoming one, since an older smaller reading can never be a peak while the newer one is still in view. Then drop the front if it has fallen behind the block, and once the first full block is reached emit the reading at the front. Each index enters and leaves the deque once, giving a single linear pass.

Pythonentry point: rolling_peaks

from collections import deque


def rolling_peaks(readings, span):
    pending = deque()
    peaks = []
    for i, value in enumerate(readings):
        while pending and readings[pending[-1]] <= value:
            pending.pop()
        pending.append(i)
        while pending[0] <= i - span:
            pending.popleft()
        if i >= span - 1:
            peaks.append(readings[pending[0]])
    return peaks

The obvious version

Slice out each block of span readings and take the maximum of the slice directly, O(n * span).

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_rolling_peaks(readings, span):
    peaks = []
    for start in range(len(readings) - span + 1):
        peaks.append(max(readings[start:start + span]))
    return peaks

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