Freezer Warmest Stretch

HardqueueAlso known as Sliding Window Maximum

A restaurant's walk-in freezer logs its temperature once a minute, in degrees Celsius. A food-safety rule looks at every stretch of k consecutive minutes and cares about the warmest reading in that stretch: one warm spike can matter even if the average looks fine.

The inspector wants a report with the warmest reading for every possible k-minute stretch: minutes 0 to k - 1, then 1 to k, and so on to the end of the log. Logs cover whole weeks, so the report must be quick to compute.

Your task

Write warmestStretches(temps, k). Return a list with one entry for each window of k consecutive readings, in order from the start: the largest value in that window. A log of n readings has n - k + 1 windows.

Aim for O(n) time in total, no matter how large k is.

warmestStretches(temps: int[], k: int) → int[]

Examples

Example 1

Input

temps = [-18, -16, -19, -20, -17, -21]
k = 3

Output

[-16, -16, -17, -17]

Why

Windows of 3: [-18, -16, -19] peaks at -16. [-16, -19, -20] still has -16. [-19, -20, -17] peaks at -17, because -16 has left. [-20, -17, -21] peaks at -17.

Example 2

Input

temps = [-6, -9, -12]
k = 1

Output

[-6, -9, -12]

Why

With k = 1 every window holds one reading, so the report is the log itself.

Constraints

1 ≤ temps.length ≤ 100,000
1 ≤ k ≤ temps.length
-40 ≤ temps[i] ≤ 40

Start with brute force

For each of the n - k + 1 windows, scan its k readings and take the maximum.

That is O(n·k). With 100,000 readings and k = 50,000 there are 50,001 windows of 50,000 readings each: about 2.5 billion comparisons. Neighbouring windows share all but one reading, yet every scan starts from nothing.

Hints

0 of 4 shown

Hint 1
In the window [-19, -20, -17], the reading -17 arrived last. Can -19 or -20 ever be the warmest of a later window that also contains -17?
Hint 2
A reading that is colder than (or equal to) a newer reading can never be the peak again: the newer one is warmer and stays in the window at least as long. So you can throw such readings away for good.
Hint 3
Keep only readings that could still be a peak, in arrival order. They are then in falling order, so the front is the current peak. You need to add at the back, drop useless readings from the back, and drop expired readings from the front. Which structure does all three in O(1)?
Hint 4
Use a deque of indexes. For each minute i: pop from the back while temps[back] <= temps[i], push i, then pop the front if it is i - k or older. Once i >= k - 1, record temps[front].

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

When a warmer reading arrives, every older reading that is not warmer than it becomes useless: the new one beats it and stays in the window longer. Throw those away. What remains, in arrival order, is falling, so the front is always the peak. Readings enter at the back and leave at both ends, which is a deque. Store indexes so you can tell when the front has expired.

Trace [-18, -16, -19, -20, -17, -21] with k = 3 (deque shown as index(temp), front first):

i = 0 (-18). Push. Deque: 0(-18).
i = 1 (-16). -18 ≤ -16, so drop 0. Push. Deque: 1(-16).
i = 2 (-19). Colder than -16, keep both. Deque: 1(-16), 2(-19). First full window: peak -16.
i = 3 (-20). Push. Deque: 1(-16), 2(-19), 3(-20). Front index 1 is still inside (window is 1 to 3). Peak -16.
i = 4 (-17). Drop 3 and 2 from the back (both colder). Push. Deque: 1(-16), 4(-17). Front index 1 is 4 - 3 = 1, so it expired: drop it. Peak -17.
i = 5 (-21). Push. Deque: 4(-17), 5(-21). Peak -17.

Report: [-16, -16, -17, -17]. Note the order in each step: clean the back, push, then check the front. Checking the front against i - k keeps exactly the last k minutes.

Reference solution

function warmestStretches(temps, k) {
  const dq = []; // indexes; their temps fall from front to back
  let head = 0;  // front of the deque (avoids slow shift())
  const peaks = [];
  for (let i = 0; i < temps.length; i++) {
    // drop readings that can never be a peak again
    while (dq.length > head && temps[dq[dq.length - 1]] <= temps[i]) dq.pop();
    dq.push(i);
    if (dq[head] <= i - k) head++; // the front reading left the window
    if (i >= k - 1) peaks.push(temps[dq[head]]);
  }
  return peaks;
}

from collections import deque
 
def warmest_stretches(temps, k):
    dq = deque()  # indexes; their temps fall from front to back
    peaks = []
    for i, t in enumerate(temps):
        # drop readings that can never be a peak again
        while dq and temps[dq[-1]] <= t:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:  # the front reading left the window
            dq.popleft()
        if i >= k - 1:
            peaks.append(temps[dq[0]])
    return peaks

TimeO(n)Each index enters the deque once and leaves it at most once, from one end or the other.

SpaceO(k)The deque only ever holds indexes from the current window.

Learn the idea: Queues and Deques Monotonic Stack Sliding Window

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code