Compute streaming sliding-window minimums
Company: Aurora
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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.
Quick Answer: 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.
For each index, output the minimum in the most recent window of up to k elements ending at that index.
Constraints
- k >= 1
Examples
Input: ([4, 2, 12, 3, -1, 6], 3)
Expected Output: [4, 2, 2, 2, -1, -1]
Explanation: One output per element.
Input: ([1, 2, 3], 1)
Expected Output: [1, 2, 3]
Explanation: Window size one.
Input: ([3, 2, 1], 5)
Expected Output: [3, 2, 1]
Explanation: Window larger than prefix.
Input: ([], 3)
Expected Output: []
Explanation: Empty stream.
Hints
- Use a monotonic deque of candidate indices.