Pattern Guide
Multiset & Ordered Set Patterns
"Maintain sorted collections dynamically. Order statistics, rank queries, range operations."
Multiset and ordered set problems require maintaining a dynamically sorted collection with efficient insert, delete, and order-statistic queries (kth smallest, count less than). JavaScript lacks a built-in TreeSet, so common approaches: sort+binary search for offline queries, Fenwick/segment tree on compressed values for online queries, or SortedList simulation. Patterns: sliding window median, kth largest in stream, count inversions.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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; }
}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 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; }
}- 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.