Kth Greatest Element in Sliding Subarrays

Problem Statement

Given an integer array nums and a window size w, return for each window of size w the k-th largest element inside that window.

Special case k = 1: Return the maximum of each window. This is LC 239 (Sliding Window Maximum).

Example 1 (k = 1, sliding max):

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], w = 3
Output: [3, 3, 5, 5, 6, 7]
Explanation:
  Window [1, 3, -1]: max 3
  Window [3, -1, -3]: max 3
  Window [-1, -3, 5]: max 5
  Window [-3, 5, 3]: max 5
  Window [5, 3, 6]: max 6
  Window [3, 6, 7]: max 7

Example 2 (general k, e.g., k = 2):

Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], w = 3, k = 2
Output: [1, -1, -1, 3, 5, 6]

Constraints:

• 1 <= nums.length <= 10^5.
• 1 <= w <= nums.length.
• 1 <= k <= w.

Difficulty: Hard (for general k) LC: 239 (k=1), general case is Technical R2 / follow-up Round: Technical R2

---

Pattern Recognition

• What is the input structure? A flat array and a window size.
• What are we optimizing? Efficient per-window aggregate.
• What pattern does this fit?
  • For k = 1: monotonic deque.
  • For general k: balanced BST / ordered multiset / two heaps with lazy deletion.
• Why does this pattern fit?
  • Monotonic deque keeps only "potential maxes" — as a new element enters, pop all smaller trailing elements (they can never be the max of any future window containing the new element).
  • For general k, a sorted multiset lets you insert/erase in O(log w) and find the k-th largest in O(k) or O(log w) with order-statistics.

---

Approach

Brute Force — Sort Each Window

For each window, sort and pick the k-th largest.

Time: O(n * w log w). Space: O(w). Why insufficient: For n = 10^5, w = 10^4, this is 10^9 * 14 ≈ TLE.

Optimal (k = 1) — Monotonic Deque

Key Insight: Maintain a deque of indices such that the corresponding values are strictly decreasing. The front of the deque is the max of the current window. When a new element nums[i] is added, pop all trailing deque entries <= nums[i] (they can't be future maxes while nums[i] is in the window). When an index falls off the left of the window, pop it from the front.

Step-by-step:

1. Initialize empty deque dq (stores indices), output out.
2. For i from 0 to n-1:
   • If dq.front() <= i - w, pop front (out of window).
   • While dq.back() has value <= nums[i], pop back.
   • Push i.
   • If i >= w - 1, append nums[dq.front()] to output.
3. Return output.

Time: O(n) — each index pushed and popped at most once. Space: O(w).

Optimal (General k) — Multiset

Key Insight: A sorted multiset (C++ std::multiset, or a balanced BST) supports O(log w) insert, O(log w) erase, and (with order-statistics) O(log w) k-th lookup. Without order-statistics, use prev(end(), k) in O(k).

Step-by-step:

1. Initialize empty multiset ms.
2. For i from 0 to n-1:
   • Insert nums[i].
   • If i >= w, erase nums[i - w] (one instance — use find + erase by iterator, not by value).
   • If i >= w - 1, walk backward from end() k times to find the k-th largest; append to output.
3. Return output.

Time: O(n log w) with per-window k-th lookup amortized. Tight if k is small. Space: O(w).

---

Walkthrough (Sliding Max, k = 1)

Trace on nums = [1, 3, -1, -3, 5, 3, 6, 7], w = 3:

i	nums[i]	deque before (indices → values)	pop front?	pop back while <= nums[i]?	push	deque after	emit
0	1	[]	no	no	0	[0:1]	—
1	3	[0:1]	no	pop 0:1	1	[1:3]	—
2	-1	[1:3]	no	no	2	[1:3, 2:-1]	3
3	-3	[1:3, 2:-1]	no (front 1 > 3-3=0)	no	3	[1:3, 2:-1, 3:-3]	3
4	5	[1:3, 2:-1, 3:-3]	pop 1 (1 <= 4-3=1)	pop 3, 2, 1	4	[4:5]	5
5	3	[4:5]	no	no	5	[4:5, 5:3]	5
6	6	[4:5, 5:3]	no	pop 5, 4	6	[6:6]	6
7	7	[6:6]	no	pop 6	7	[7:7]	7

Output: [3, 3, 5, 5, 6, 7].

Note: when i = 4, we first pop the front (index 1 falls off the left) then pop back trailing entries that 5 dominates.

---

Implementation

TypeScript

// k = 1 (Sliding Window Maximum).
function maxSlidingWindow(nums: number[], w: number): number[] {
    const out: number[] = [];
    const dq: number[] = []; // indices, values strictly decreasing

    for (let i = 0; i < nums.length; i++) {
        // Pop front if it falls out of the window.
        if (dq.length > 0 && dq[0] <= i - w) dq.shift();
        // Pop back while the new element dominates.
        while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
        dq.push(i);
        // Emit once the first full window is formed.
        if (i >= w - 1) out.push(nums[dq[0]]);
    }
    return out;
}

C++

#include <vector>
#include <deque>

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int w) {
    std::vector<int> out;
    std::deque<int> dq;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (!dq.empty() && dq.front() <= i - w) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= w - 1) out.push_back(nums[dq.front()]);
    }
    return out;
}

General k (C++ multiset):

C++

#include <vector>
#include <set>

std::vector<int> kthLargestInWindow(std::vector<int>& nums, int w, int k) {
    std::multiset<int> ms;
    std::vector<int> out;
    for (int i = 0; i < (int)nums.size(); i++) {
        ms.insert(nums[i]);
        if (i >= w) ms.erase(ms.find(nums[i - w])); // erase one instance by iterator
        if (i >= w - 1) {
            auto it = ms.end();
            for (int j = 0; j < k; j++) --it;
            out.push_back(*it);
        }
    }
    return out;
}

TypeScript lacks a built-in balanced BST, so for general k in TS you would:

• Implement a min-heap of size k with lazy deletion of out-of-window elements, or
• Implement a small-size sorted array (O(w) per insert/erase, acceptable for small w).

Watch out:

1. Using shift on deque in TS. Array.shift() is O(n). For huge n, implement a two-pointer deque or use a real deque library. Most interview-time inputs are small enough to pass.
2. Erase by value on multiset. ms.erase(nums[i-w]) erases all instances. Use ms.erase(ms.find(nums[i-w])) to erase one.
3. Pop front before pop back. Order matters: first check out-of-window, then maintain monotonic invariant.

---

Complexity Analysis

	Time	Space
Brute Force	O(n * w log w)	O(w)
Monotonic Deque (k=1)	O(n)	O(w)
Multiset (general k)	O(n log w + n * k)	O(w)

Bottleneck (deque): Each index pushed and popped at most once — amortized O(1) per step. Bottleneck (multiset): The per-window k-th lookup is O(k) with iterator decrement, or O(log w) with an order-statistics tree.

---

Edge Cases

1. w == 1 — every window is a single element; output is the input.
2. w == n — one window, the whole array. One output.
3. k == w — always the minimum of each window.
4. All identical values — every answer is that value.
5. Strictly increasing array — monotonic deque stays size 1 (every new element pops all trailing).
6. Strictly decreasing array — deque grows to size w (nothing pops until the left falls out).

---

Related Problems

• LC 239 — Sliding Window Maximum — k = 1 case.
• LC 480 — Sliding Window Median — Two-heap approach for the median (k = w/2).
• LC 862 — Shortest Subarray with Sum at Least K — Monotonic deque on prefix sums.
• LC 1499 — Max Value of Equation — Sliding window + monotonic deque on a pairwise objective.

---

Interview Strategy Notes

This is a Technical R2 problem. Budget 25-35 minutes. Always start with k = 1 and the monotonic deque — explain why it is amortized O(1) per step. If asked for general k, discuss the multiset approach and the lack of built-in ordered multiset in TS. If the interviewer asks for the median specifically, pivot to two heaps (max-heap for bottom half, min-heap for top half).

---

What is Expected at Each Level

Junior: Solves brute force. With heavy hints, arrives at the deque for k=1. Struggles with general k.

Mid-level: Writes the monotonic deque cleanly for k=1. Explains the amortized analysis. Offers multiset for general k.

Senior: Implements both without prompting. Discusses the order-statistics-tree alternative for O(log w) k-th lookup. Mentions the two-heap approach for the median variant and its lazy-deletion bookkeeping.