Skip to question
ASIC.FYI

Q232FreeSystemVerilog

Forward-looking sliding window maximum

Difficulty
Medium
Topic
Arrays
Language
SV
Interview prompt

Question

For every index i, compute the maximum from a[i] through a[min(i + K - 1, n - 1)]. Return one output per input index, using a truncated window near the end.

Starting point

Question code

function automatic void sliding_window_max_forward(
  int k,
  ref int a[],
  ref int out[]
);
Reviewed example

Trace one case

Input
a=[1,3,-1,-3,5,3,6,7]; K=3
Expected output
[3,3,5,5,6,7,7,7]

Each output looks forward up to three positions, with naturally truncated windows for the last two indices.

What to cover

Requirements

  1. Return an output array with the same length as the input.
  2. Return an empty output for empty input and clamp K to 1 through n otherwise.
  3. First explain the O(nK) scan, then implement an O(n) monotonic-deque solution.
  4. Use indices in the deque so expired elements are identified unambiguously.
Continue practicing
Q233 · ArraysTrailing sliding window maximumQ167 · Data StructuresTrack top-K frequencies in a sliding windowQ289 · ArraysRemove duplicates while preserving order