Compute streaming sliding-window minimums

Q: Compute streaming sliding-window minimums

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute streaming sliding-window minimums

Quick Overview

Problem

Example

Constraints

Goal

Comments (0)