Ordered Window

When To Use

Use this when the active window needs ordered queries like min, max, median, or closest value.

Common tools: balanced BST, multiset, TreeMap, SortedList, or two heaps with lazy deletion.

Template

for r = 0; r < n; r++:
    insert nums[r]
 
    if window too large:
        erase nums[l]
        l++
 
    query ordered structure

Problems Using This Pattern

Sliding Window Median

Problem: find the median of every size-k window.

State: two heaps or ordered multiset.

Contains Duplicate III

Problem: find two indices within distance k whose values differ by at most t.

State: ordered set of last k values and query nearest values.

Maximum Number of Robots Within Budget

Problem: find the longest window whose max charge plus running cost fits the budget.

State: ordered structure for max charge, plus running sum.