Pattern Reference
Multiset & Ordered Set
"Order statistic tree, sorted container, balanced BST simulation. K-th element, count of elements in range."
Loading...
Deep Dive Tutorial
Ordered set operations: insert O(log n), delete O(log n), find kth O(log n), count less-than O(log n). In JavaScript: simulate with Fenwick tree on coordinate-compressed values (offline), or sorted array with binary search (O(n) insert but simple). Pattern: sliding window requires removing elements — use a Fenwick tree or sorted array for O(log n) operations.
Sorted array with binary search for ordered set operations
// Sorted array simulation — insert O(n), query O(log n)
// Use when n is small or queries dominate
class SortedList {
constructor() { this.data = []; }
add(val) {
let lo = 0, hi = this.data.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.data[mid] < val) lo = mid + 1; else hi = mid;
}
this.data.splice(lo, 0, val);
}
remove(val) {
const idx = this._bisectLeft(val);
if (this.data[idx] === val) this.data.splice(idx, 1);
}
// Count elements strictly less than val
countLess(val) { return this._bisectLeft(val); }
// kth element (0-indexed)
kth(k) { return this.data[k]; }
_bisectLeft(val) {
let lo = 0, hi = this.data.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (this.data[mid] < val) lo = mid + 1; else hi = mid;
}
return lo;
}
get size() { return this.data.length; }
}Worked Problems
clipboard-list
When to use each ordered-set approach:
- Offline + small values: Fenwick tree with coordinate compression
- Online + small n: SortedList (sorted array with binary search insert)
- Median queries: Two heaps (max-heap lower half, min-heap upper half)
- Near-duplicates in window: Bucket sort by value range
JavaScript gap: Java has TreeMap/TreeSet, Python has SortedList (sortedcontainers). In JS, implement with Fenwick+compression or simulate with sorted array. For interviews, sorted array + binary search is easiest to explain.
- Offline + small values: Fenwick tree with coordinate compression
- Online + small n: SortedList (sorted array with binary search insert)
- Median queries: Two heaps (max-heap lower half, min-heap upper half)
- Near-duplicates in window: Bucket sort by value range
JavaScript gap: Java has TreeMap/TreeSet, Python has SortedList (sortedcontainers). In JS, implement with Fenwick+compression or simulate with sorted array. For interviews, sorted array + binary search is easiest to explain.