EF-T05: Fixed-window signal peaks

Exercise contract#

Given an integer array values and an integer k, return the maximum value in every contiguous window of length k, from left to right. For nonempty values, require 1 <= k <= values.length. Empty values returns an empty result only when k=0; every other k is invalid. Do not mutate values.

Constraints

• 0 <= values.length <= 200,000.
• Each value is an integer in [-1,000,000,000, 1,000,000,000].
• For nonempty input, 1 <= k <= values.length; for empty input, k must be 0.
• Return exactly values.length-k+1 maxima for nonempty input.
• Equal arriving values replace older equal candidates; maxima are unchanged, but the tie policy makes the state deterministic.

Examples

values=[6,2,5,1,7], k=3

[6,5,7]The three windows are [6,2,5], [2,5,1], and [5,1,7].

values=[], k=0

[]The empty contract has no windows and admits only k=0.

Derive the approach#

Baseline: For every window start, scan its k elements and select the maximum. This is correct in O((n-k+1)k) time, but adjacent windows repeat almost all comparison work.

1. Store candidate indices, not only values, because window membership expires by position.
2. At index i, remove front indices <= i-k before reading the current window.
3. Remove back indices whose values are <= values[i]. The new value is at least as large and expires later, so those older candidates can never win a future window.
4. Append i. After i reaches k-1, the deque front is the maximum of the complete current window.
5. Each index is appended once and removed at most once, bounding total deque operations by O(n).

Time

O(n) amortized for valid input.

Space

O(k) auxiliary deque space plus O(n-k+1) returned output.

Assumptions

Deque end operations are constant time; each index enters and leaves at most once. Validation is O(1) beyond reading the array length, and integer comparisons do not overflow.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

from collections import deque

def fixed_window_maximum(values, k):
    if not values:
        if k == 0:
            return []
        raise ValueError("empty input requires k=0")
    if k < 1 or k > len(values):
        raise ValueError("nonempty input requires 1 <= k <= len(values)")

    candidates = deque()
    answer = []
    for index, value in enumerate(values):
        while candidates and candidates[0] <= index - k:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(index)
        if index >= k - 1:
            answer.append(values[candidates[0]])
    return answer

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

final class TransferT05 {
    static List<Integer> fixedWindowMaximum(int[] values, int k) {
        if (values.length == 0) {
            if (k == 0) return List.of();
            throw new IllegalArgumentException("empty input requires k=0");
        }
        if (k < 1 || k > values.length) {
            throw new IllegalArgumentException("nonempty input requires 1 <= k <= length");
        }
        Deque<Integer> candidates = new ArrayDeque<>();
        List<Integer> answer = new ArrayList<>();
        for (int index = 0; index < values.length; index++) {
            while (!candidates.isEmpty() && candidates.peekFirst() <= index - k) {
                candidates.removeFirst();
            }
            while (!candidates.isEmpty() && values[candidates.peekLast()] <= values[index]) {
                candidates.removeLast();
            }
            candidates.addLast(index);
            if (index >= k - 1) answer.add(values[candidates.peekFirst()]);
        }
        return answer;
    }
}

Deterministic test plan#

Transfer and follow-ups#

• Return fixed-window minima by reversing the dominance comparison.
• Retain the oldest equal maximum instead; explain which comparison changes and why numeric output does not.
• Compare with a lazy-deletion heap and account for its logarithmic operations.

Reapply the expiration and dominance invariant without reading a visible pattern label during the attempt.

Authorship and review#

Engineering Foundry authored this prompt, examples, tests, explanations, and reference code. It teaches the established monotonic-deque technique, is not attributed to an employer, and does not claim the underlying algorithmic pattern is unique.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09, SRC-DSA-CP-MINIMUM-QUEUE