Maximum of Each Length-k Window in an Integer Array
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given an integer array `nums` and a window length `k`, slide a window of exactly `k` consecutive elements from the left end of the array to the right end, one position at a time. Return the maximum value inside the window at each position, in order from left to right.
### Function Signature
```python
def window_maxima(nums: list[int], k: int) -> list[int]:
```
### Rules
- The window that starts at index `i` covers `nums[i]` through `nums[i + k - 1]`.
- The output has exactly `len(nums) - k + 1` values; the value at index `i` is the maximum of the window that starts at index `i`.
- Equal values are fine: the output holds values, not positions.
### Constraints
- `1 <= len(nums) <= 10^5`
- `1 <= k <= len(nums)`
- `-10^9 <= nums[i] <= 10^9`, so every value fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: nums = [4, 2, 12, 3, 8, 1, 7], k = 3
Output: [12, 12, 12, 8, 8]
```
The windows are `[4, 2, 12]`, `[2, 12, 3]`, `[12, 3, 8]`, `[3, 8, 1]` and `[8, 1, 7]`.
**Example 2**
```text
Input: nums = [5, -1, -3, 2], k = 1
Output: [5, -1, -3, 2]
```
Each window holds one element, so the output equals the input.
**Example 3**
```text
Input: nums = [-2, -5, -1], k = 3
Output: [-1]
```
There is a single window, the whole array.
Overview: Given an integer array and a window length k, return the maximum value of every contiguous window of length k as the window slides from left to right. The problem tests efficient maintenance of a moving window on arrays of up to 100,000 elements, where rescanning each window is too slow.
Given an integer array `nums` and a window length `k`, slide a window of exactly `k` consecutive elements from the left end of the array to the right end, one position at a time. Return the maximum value inside the window at each position, in order from left to right.
Implement `window_maxima(nums, k)`, which returns a list of integers.
### Rules
- The window that starts at index `i` covers `nums[i]` through `nums[i + k - 1]`.
- The output has exactly `len(nums) - k + 1` values; the value at index `i` is the maximum of the window that starts at index `i`.
- Equal values are fine: the output holds values, not positions.
### Constraints
- `1 <= len(nums) <= 10^5`
- `1 <= k <= len(nums)`
- `-10^9 <= nums[i] <= 10^9`, so every value fits in a 32-bit signed integer. Every output value is an element of `nums`, so no input or output value can exceed 2^31 - 1 (Java and C++ use `int`).
### Example 1
```text
Input: nums = [4, 2, 12, 3, 8, 1, 7], k = 3
Output: [12, 12, 12, 8, 8]
```
The windows are `[4, 2, 12]`, `[2, 12, 3]`, `[12, 3, 8]`, `[3, 8, 1]` and `[8, 1, 7]`.
### Example 2
```text
Input: nums = [-2, -5, -1], k = 3
Output: [-1]
```
There is a single window, the whole array.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= k <= len(nums)
- -10^9 <= nums[i] <= 10^9, so every value fits in a 32-bit signed integer
Examples
Input: ([4, 2, 12, 3, 8, 1, 7], 3)
Expected Output: [12, 12, 12, 8, 8]
Explanation: Source example 1: the maximum 12 covers three windows, then 8 takes over; 7 - 3 + 1 = 5 values.
Input: ([-2, -5, -1], 3)
Expected Output: [-1]
Explanation: Source example 3: k = len(nums), one window covering the whole all-negative array.
Hints
- Recomputing every window from scratch costs up to len(nums) * k comparisons; with len(nums) up to 10^5 and k up to len(nums), look for work that neighbouring windows can share.
- Moving the window one position removes exactly one element on the left and adds exactly one on the right.
- The output holds values, not positions, so equal values need no tie-breaking.