Katkat
Back

Compute streaming sliding-window minimums

AuroraSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's understanding of streaming algorithms and efficient data-structure techniques for maintaining sliding-window minima, measuring competency in algorithmic thinking, time and space complexity, and online processing.

Problem

You are given an integer array nums of length n and an integer window size k.

You scan nums from left to right (streaming). At each index i, you must output the minimum value in the most recent window of up to k elements ending at i.

Formally, define:

  • L = max(0, i - k + 1)
  • The active window is nums[L..i]
  • ans[i] = min(nums[L..i])

Return the array ans of length n.

Example

If nums has 10 values and k = 3, you must still return 10 outputs (one per element), not n-k+1.

Constraints

  • 1 <= n <= 2 * 10^5
  • 1 <= k <= 10^5
  • nums[i] fits in 32-bit signed integer

Goal

Design an algorithm that works in a streaming fashion (produce ans[i] as soon as you read nums[i]) and runs in O(n) time.