Advanced Optimization

Data Structures for Windows

Deque (Double-Ended Queue)

Efficient add/remove from both ends
- Append: O(1)
- Pop: O(1)

Perfect for sliding windows!

Heap (Priority Queue)

Find min/max in window
- Insert: O(log n)
- Find min: O(1)

Trade-off: slower insert, instant find

Balanced BST

Ordered window data
- Insert/Remove: O(log n)
- Find range: O(log n + result)

More powerful than deque

Hash Map

Track element frequencies
- Insert/Remove: O(1)
- Query: O(1)

No ordering, but fast

Common Patterns

Monotonic Deque

Maintain window elements in sorted order:

[3, 1, 4, 1, 5]
Window [1, 4, 1]: Keep deque [1, 4] not [4, 1]

Benefit: Know min/max without searching

Frequency Counting

Track what elements in window:

HashMap: {element: count}
Query: "Are all elements unique?" O(1)

Two Passes

First pass: Collect info
Second pass: Apply info

Example:
Pass 1: Find optimal window bounds
Pass 2: Collect detailed stats

Performance Tricks

1. Lazy deletion: Mark removed, clean later
2. Caching: Remember computed values
3. Early termination: Stop if bound impossible
4. Preprocessing: Sort/index before sliding