Top-K Largest Elements in Every Sliding Window
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an integer array `nums` together with two integers `W` (the window size) and `K`. A sliding window of size `W` starts at the left end of `nums` and moves one position to the right at a time, so there are `len(nums) - W + 1` windows in total.
For each window, find the `K` largest elements inside that window and list them in non-increasing (descending) order. Return a list with one entry per window, in left-to-right window order.
Note that this asks for the top `K` elements of each window, not just the single maximum.
Duplicates count separately: if a window contains several equal values, each copy is an independent element and may appear more than once among the top `K` (for example, the top 2 of `[5, 5, 3]` is `[5, 5]`).
A naive approach that re-sorts every window costs `O(n * W log W)`. Aim to do better by maintaining an ordered structure for the current window so that each element entering or leaving the window costs `O(log W)`.
### Constraints
- `1 <= K <= W <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- Elements may repeat.
### Examples
- `nums = [1, 3, 2, 5, 4]`, `W = 3`, `K = 2`
- Window `[1, 3, 2]` → top 2 = `[3, 2]`
- Window `[3, 2, 5]` → top 2 = `[5, 3]`
- Window `[2, 5, 4]` → top 2 = `[5, 4]`
- Output: `[[3, 2], [5, 3], [5, 4]]`
- `nums = [4, 4, 1, 4]`, `W = 3`, `K = 2`
- Window `[4, 4, 1]` → top 2 = `[4, 4]`
- Window `[4, 1, 4]` → top 2 = `[4, 4]`
- Output: `[[4, 4], [4, 4]]`
Quick Answer: This question evaluates the ability to design and maintain an ordered data structure that efficiently tracks the top K largest values within a moving window over an array. It tests knowledge of sliding window techniques combined with balanced search trees or ordered sets, commonly used to assess data structure selection beyond simple heaps or monotonic queues. The question is a practical coding and algorithms problem targeting logarithmic-time updates.
You are given an integer array `nums` together with two integers `W` (the window size) and `K`. A sliding window of size `W` starts at the left end of `nums` and moves one position to the right at a time, so there are `len(nums) - W + 1` windows in total.
For each window, find the `K` largest elements inside that window and list them in non-increasing (descending) order. Return a list with one entry per window, in left-to-right window order.
Note that this asks for the top `K` elements of each window, not just the single maximum.
Duplicates count separately: if a window contains several equal values, each copy is an independent element and may appear more than once among the top `K` (for example, the top 2 of `[5, 5, 3]` is `[5, 5]`).
A naive approach that re-sorts every window costs `O(n * W log W)`. Aim to do better by maintaining an ordered structure for the current window so that each element entering or leaving the window costs `O(log W)`.
### Constraints
- `1 <= K <= W <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- Elements may repeat.
Constraints
- 1 <= K <= W <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- Elements may repeat; each duplicate is an independent element.
Examples
Input: ([1, 3, 2, 5, 4], 3, 2)
Expected Output: [[3, 2], [5, 3], [5, 4]]
Explanation: Windows [1,3,2]->[3,2], [3,2,5]->[5,3], [2,5,4]->[5,4].
Input: ([4, 4, 1, 4], 3, 2)
Expected Output: [[4, 4], [4, 4]]
Explanation: Duplicates count separately: [4,4,1] top2=[4,4]; [4,1,4] top2=[4,4].
Input: ([5], 1, 1)
Expected Output: [[5]]
Explanation: Single-element window with W=K=1 yields one window containing just [5].
Input: ([3, 1, 2], 3, 3)
Expected Output: [[3, 2, 1]]
Explanation: One window; K==W so all three elements returned in descending order.
Input: ([-1, -5, -3, -2], 2, 1)
Expected Output: [[-1], [-3], [-2]]
Explanation: All-negative values, K=1: each window returns its single maximum.
Input: ([5, 5, 3], 3, 2)
Expected Output: [[5, 5]]
Explanation: The two equal 5s both appear among the top 2.
Input: ([2, 1, 2, 1, 2], 2, 2)
Expected Output: [[2, 1], [2, 1], [2, 1], [2, 1]]
Explanation: Every window of size 2 sorts to [2,1] in descending order.
Hints
- A monotonic deque only tracks the single maximum, so it cannot recover the 2nd..Kth largest after they are discarded. You need every element in the window kept in order.
- Maintain the current window as an ordered multiset. When the window slides, erase the element leaving on the left and insert the new element on the right, each in O(log W).
- In Python, `sorted(nums[:W])` plus `bisect.insort` / `bisect.bisect_left` keeps the window sorted; take the last K entries and reverse them to get the top K in descending order.
- Because duplicates count separately, erase by position (e.g. bisect_left then pop), not by value-set removal that would drop all copies.