Ordered sets without a TreeMap

What an ordered set has to answer

A hash set answers one question: is x in here? A heap answers one more: what is the smallest item? A large family of problems asks something in between, about neighbours in sorted order inside a collection that keeps changing. What is the first booking that starts after 15? Which stored number is closest to 12? What is the median of the current window? How many earlier prefix sums fall inside [a, b]? Java answers these with TreeMap and TreeSet, C++ with std::set and std::map. JavaScript has nothing like them: Set and Map are hash tables that iterate in insertion order, and the sort order of keys plays no part in them.

This chapter is about what to put in that gap, how to choose between the options, and the problems where an ordered set is the whole idea. The Binary search tree chapter owns the tree itself: insert, delete, rotations, AVL, the red-black idea, and a short SortedList class. The JavaScript toolkit has the same sorted-array class with a comparator, and the Segment and Fenwick trees chapter owns the Fenwick tree. None of that is repeated here. What this chapter adds is the working engineer's side: the interface, a complete balanced structure with rank and select, a faster one for large inputs, an offline alternative, and the problems.

The interface

The two rows marked "no direct method" are the surprise. The standard ordered sets of Java and C++ do not give you rank or select in O(log n); programmers who need them write an order-statistic tree or use a Fenwick tree. So the structures in this chapter are not a poor copy of TreeMap. With subtree sizes they can answer more than it can.

One observation shortens everything that follows. Five of the rows can be computed from two counting primitives. Let rank(x) be the number of keys smaller than x, and countAtMost(x) the number of keys not larger than x. Then, counting positions from 0:

• floor(x) = at(countAtMost(x) − 1), higher(x) = at(countAtMost(x))
• lower(x) = at(rank(x) − 1), ceiling(x) = at(rank(x))
• countRange(lo, hi) = countAtMost(hi) − rank(lo)

So any structure that supports add, remove, rank, countAtMost and at supports the whole interface. A sorted array gets rank from a binary search and at from an index. A Fenwick tree over compressed values gets both from prefix sums. A balanced tree gets both from subtree sizes. The rest of the chapter is three ways of providing those five operations, and then using them.

Decide first whether the collection is a set (adding a key that is already there changes nothing) or a multiset (every copy counts). The structures here are multisets, because sliding-window medians and prefix-sum counts need every copy: add always adds one, and remove removes one copy and says whether it found any. To get set behaviour, call has before add.

The sorted array, and where it stops

The first thing to reach for is the plain sorted array, and the two chapters named above already give you the complete class: a binary search for the lower and upper bound, splice to insert and delete. Through the lens of the five primitives it is almost free. rank(x) is the lower bound, at(i) is items[i], countAtMost(x) is the upper bound, so every query in the table costs O(log n) or better. The only slow operations are add and remove, and the reason is mechanical: splice(i, 0, x) must move every item after position i one place to the right. For a random position that is about n/2 items. Inserting n items one at a time moves about n²/4 items in total, so the total cost grows with the square of n even though each search is logarithmic.

The cost per moved item is small, because the shift runs inside the built-in splice and not in your own loop, and that is why the sorted array is such a strong default. Measured here, inserting random integers one at a time into a sorted array took about 5 ms for 10,000 items, about 0.5 s for 100,000 and about 4.7 s for 300,000 (Node 24 on an Apple M2 Pro, median of five runs). Tripling n multiplied the time by about nine, which is the quadratic growth showing. Your numbers will differ with the machine, the Node version and the data. What carries over is the shape: fine up to tens of thousands of updates, hopeless at hundreds of thousands.

The treap: a balanced tree from two small functions

When the array's shift is too slow, the next candidate is a balanced binary search tree, since a tree changes a few pointers instead of moving a block. The trouble, as the BST chapter showed, is balance: a plain tree fed sorted keys turns into a linked list, and AVL or red-black trees repair it with rotations and a list of cases that is easy to get wrong in a live interview. The structure below is balanced with high probability, is short enough to write from memory, and gets rank and select almost for free. It is called a treap: a tree ordered by key, and a heap ordered by a random priority.

The idea, in three steps

Step 1: two orders at once. Give every key a priority. Demand that the tree be a binary search tree by key (smaller keys on the left) and, at the same time, a max-heap by priority (a parent's priority is at least its children's). For distinct keys and distinct priorities there is exactly one such tree: the root must be the key with the highest priority, everything smaller goes to the left, everything larger to the right, and the same rule applies inside each side. The shape is decided by the keys and priorities alone, and not by the order in which the keys were inserted.

Step 2: random priorities give balance. If every priority is drawn at random when its key is created, then the root is a uniformly random one of the n keys, and so is the root of each subtree. That is quicksort with a random pivot, drawn as a tree. The result is the same tree you would get by inserting the keys into an ordinary BST in decreasing order of priority, and that order is a uniformly random permutation. Such a tree has expected height O(log n). The randomness comes from the priorities, so sorted input is harmless: it cannot choose the shape.

Step 3: two primitives do all the work. Keeping both orders after every change sounds like a job for rotations, but it needs only two functions.

• split(t, key) cuts the tree in two: one tree with the keys below key, one with the rest. Walk down from the root. A node smaller than key goes left, together with its whole left subtree, and the walk continues into its right subtree. Any other node goes right with its right subtree, and the walk continues into its left subtree. One root-to-leaf path is rewired, so the cost is the height.
• merge(a, b) joins two trees when every key in a is at most every key in b. Compare the two roots. The higher priority stays on top. If it is a, then b must go somewhere inside a's right subtree, so merge b into a.right; if it is b, merge a into b.left. The cost is the sum of two spine lengths, so again the height.

add(key) is then one split and two merges: cut at the key, merge the left part with the new single-node tree, and merge the result with the right part. The new node settles exactly where its random priority puts it. remove(key) is two splits (below the key, and equal to the key), a merge of the two children of the equal part's root (which drops one copy), and a merge back. No rotation appears anywhere.

Finally, every node stores size, the number of nodes in its subtree, recomputed by one small function whenever a node's children change. With sizes, "how many keys are smaller" and "which key is the i-th" are plain walks down the tree, which is why the five primitives come out so cheaply.

The code: split and merge

makeNode draws the priority once, when the node is created. refresh is the single place that knows what a node summarises, so anything you want to keep per subtree (a sum, a minimum) is added there and nowhere else. The generator walkFrom is an in-order walk with an explicit stack, the same idea as the BST iterator, and it starts at the first key at or after a bound.

function makeNode(key, value, priority = Math.random()) {
  return { key, value, priority, size: 1, left: null, right: null };
}

function sizeOf(node) {
  return node === null ? 0 : node.size;
}

function refresh(node) {
  node.size = 1 + sizeOf(node.left) + sizeOf(node.right); // the one place that knows what a node summarises
  return node;
}

function merge(a, b) {
  // every key in a must be <= every key in b
  if (a === null) return b;
  if (b === null) return a;
  if (a.priority > b.priority) {
    a.right = merge(a.right, b); // a stays on top; b joins its right side
    return refresh(a);
  }
  b.left = merge(a, b.left); // b stays on top; a joins its left side
  return refresh(b);
}

function split(node, key, compare, inclusive) {
  // returns [keys < key, the rest]; with inclusive, [keys <= key, the rest]
  if (node === null) return [null, null];
  const order = compare(node.key, key);
  if (order < 0 || (inclusive && order === 0)) {
    const [middle, right] = split(node.right, key, compare, inclusive);
    node.right = middle; // node and its left side stay in the left part
    return [refresh(node), right];
  }
  const [left, middle] = split(node.left, key, compare, inclusive);
  node.left = middle; // node and its right side go to the right part
  return [left, refresh(node)];
}

function* walkFrom(root, compare, low) {
  const stack = [];
  let node = root;
  while (node !== null) {
    if (low === undefined || compare(node.key, low) >= 0) {
      stack.push(node); // node and everything after it in its right side qualify
      node = node.left;
    } else {
      node = node.right; // node and its left side are too small
    }
  }
  while (stack.length > 0) {
    node = stack.pop();
    yield node;
    node = node.right;
    while (node !== null) {
      stack.push(node);
      node = node.left;
    }
  }
}

Dry run: add(40) to the tree with 10, 20, 30 and 50

Before the call the tree is the one in the figure without the key 40: root 30 (priority 0.9) with left child 10 (0.6, whose right child is 20 with 0.4) and right child 50 (0.8). The new node gets priority 0.5.

Only the nodes on one path were touched: 30, 50 and the new 40. Every other node, and its size, is exactly as before. The three steps would produce a valid treap whatever the priority of 40 was; a different priority would only have moved 40 to a different depth.

The class: add, remove, rank, select and neighbours

The class wraps the root and the comparator. A comparator, as in sort, lets keys be numbers, strings, pairs or objects: it returns a negative number, zero or a positive number. add and remove are the split and merge recipes above. The two counting walks are the heart of it. countBefore(key) goes down from the root: when a node is below the key, that node and its whole left subtree are before the key, so add size(left) + 1 and move right; otherwise move left. at(i) asks, at each node, how many keys are in the left subtree: if i is smaller, go left; if equal, this node is the answer; otherwise skip the left subtree and the node itself and go right with a smaller i. The four neighbour queries are then the one-line formulas from the first section.

class Treap {
  constructor(compare = (a, b) => a - b) {
    this.compare = compare;
    this.root = null;
  }

  get size() {
    return sizeOf(this.root);
  }

  add(key, value = key) {
    const [left, right] = split(this.root, key, this.compare, false); // left: keys < key
    this.root = merge(merge(left, makeNode(key, value)), right);
  }

  remove(key) {
    const [left, rest] = split(this.root, key, this.compare, false); // left: keys < key
    const [equal, right] = split(rest, key, this.compare, true); // equal: keys == key
    const kept = equal === null ? null : merge(equal.left, equal.right); // drop one node, keep the other copies
    this.root = merge(left, merge(kept, right));
    return equal !== null;
  }

  find(key) {
    let node = this.root;
    while (node !== null) {
      const order = this.compare(key, node.key);
      if (order === 0) return node;
      node = order < 0 ? node.left : node.right;
    }
    return null;
  }

  has(key) {
    return this.find(key) !== null;
  }

  get(key) {
    return this.find(key)?.value;
  }

  set(key, value) {
    const node = this.find(key);
    if (node === null) this.add(key, value);
    else node.value = value;
  }

  countBefore(key, inclusive) {
    let node = this.root;
    let count = 0;
    while (node !== null) {
      const order = this.compare(node.key, key);
      if (order < 0 || (inclusive && order === 0)) {
        count += sizeOf(node.left) + 1; // node and its whole left side come before key
        node = node.right;
      } else {
        node = node.left;
      }
    }
    return count;
  }

  rank(key) {
    return this.countBefore(key, false); // how many keys are smaller
  }

  countAtMost(key) {
    return this.countBefore(key, true);
  }

  countRange(low, high) {
    return Math.max(0, this.countAtMost(high) - this.rank(low)); // both ends included
  }

  at(index) {
    if (index < 0 || index >= this.size) return undefined; // the index-th smallest, from 0
    let node = this.root;
    while (true) {
      const leftSize = sizeOf(node.left);
      if (index < leftSize) {
        node = node.left;
      } else if (index === leftSize) {
        return node.key;
      } else {
        index -= leftSize + 1;
        node = node.right;
      }
    }
  }

  floor(key) {
    return this.at(this.countAtMost(key) - 1); // largest key <= key
  }

  lower(key) {
    return this.at(this.rank(key) - 1); // largest key < key
  }

  ceiling(key) {
    return this.at(this.rank(key)); // smallest key >= key
  }

  higher(key) {
    return this.at(this.countAtMost(key)); // smallest key > key
  }

  *keys(low) {
    for (const node of walkFrom(this.root, this.compare, low)) yield node.key;
  }

  *entries(low) {
    for (const node of walkFrom(this.root, this.compare, low)) yield [node.key, node.value];
  }

  [Symbol.iterator]() {
    return this.keys();
  }
}

Two details are worth knowing. A map comes for free: every node carries a value, set(key, value) overwrites the value of an existing key, and get reads it, which the interval problems below use. And the neighbour queries cost two descents each, one for the count and one for at, which is still O(log n). Write them as a single loop, as the BST chapter does, if the constant matters.

Dry run: rank(40) and at(3) on the tree in the figure

The two calls agree: 40 has three keys before it, so it is the key at position 3. From these two, floor(45) is at(countAtMost(45) − 1), which is at(4 − 1), which is 40, and ceiling(45) is at(rank(45)), which is at(4), which is 50.

Cost, depth and why not a skip list

add, remove, rank, at and the neighbour queries each cost the height of the tree, which is O(log n) in expectation: the expectation is over the random priorities, for any sequence of operations that does not depend on them. It is not a worst-case bound, and it is not amortised: one operation can in principle be slow, with tiny probability. Memory is one object per key. In one run in Node 24, a treap of 100,000 random keys had an average node depth of 20.7 (the root counted as depth 1), against log₂ 100,000 ≈ 16.6 for a perfect tree. The average depth in a random search tree grows like 2 ln n, which is about 1.39 log₂ n. And a treap built by adding 1,000,000 keys in ascending order, the input that ruins a plain BST, had height 48. The recursion in split and merge goes as deep as the tree is high, so a few dozen frames, far below the engine's limit.

Why this and not another structure? AVL and red-black trees give a worst-case bound, but each needs several rotation cases, and with sizes every rotation must also repair two counts. A skip list needs no rotations and is the other usual "easy" ordered structure, but rank and select need each forward pointer to remember how many bottom-level items it jumps over, kept correct through every insert and delete at every level, and the node holds an array of pointers and an array of widths. That is more code and more places for an off-by-one than the treap, whose rank and select are the two short loops above. The treap's weaknesses are real: a random-number call per insert, one small object per key, and a bound that is only expected. The measurements below show it is not the fastest structure here. It is the one that is short, correct and easy to extend.

Sqrt buckets: many short arrays instead of one long one

The sorted array's problem is one long memory move. Cut the long array into consecutive pieces and the move shrinks. Keep the sorted sequence as a list of buckets, each a sorted array of at most load items, so that every item of bucket k is at most every item of bucket k + 1. An insert finds its bucket, inserts into that one short array, and shifts at most load items. When a bucket grows past load, split it into two halves, which happens once for about every load / 2 inserts.

The other operations follow from the layout. To find where x lives, binary search the buckets using each bucket's last item (the first bucket whose last item is at least x holds the answer), then binary search inside that bucket. Floor and ceiling only need the position and one step back, which may cross into the previous bucket. Rank and select need counts of items, and here the structure is blunt: add up the lengths of the buckets before the position, one by one. That scan is why buckets lose to the treap on rank-heavy workloads, and why the size of a bucket is a real choice.

With bucket size B and n items there are about n / B buckets. An insert costs about B for the shift in one bucket, plus an occasional split that costs O(B + n / B). A rank or select costs about n / B for the scan. Setting B near √n balances the two terms, so every operation costs about √n. The name "sqrt decomposition" comes from this trade (the Sparse table chapter derives the same balance for block sums). Choosing B is the one tuning decision, and a fixed value of a few hundred, like the 512 below, is a sound default for inputs up to a few million items.

class BucketList {
  constructor(load = 512) {
    this.load = load;
    this.buckets = [];
    this.size = 0;
  }

  locate(x, strict) {
    // [bucket, index] of the first item >= x (or > x when strict); [bucket count, 0] if none
    let lo = 0;
    let hi = this.buckets.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      const bucket = this.buckets[mid];
      const last = bucket[bucket.length - 1]; // the bucket's largest item decides where x lives
      if (strict ? last <= x : last < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === this.buckets.length) return [lo, 0];
    // inside the chosen bucket the answer exists, because its last item qualifies
    const bucket = this.buckets[lo];
    let from = 0;
    let to = bucket.length - 1;
    while (from < to) {
      const mid = (from + to) >> 1;
      if (strict ? bucket[mid] <= x : bucket[mid] < x) from = mid + 1;
      else to = mid;
    }
    return [lo, from];
  }

  before(bucketIndex, index) {
    // the item just before a position, possibly in the previous bucket
    if (index > 0) return this.buckets[bucketIndex][index - 1];
    return bucketIndex > 0 ? this.buckets[bucketIndex - 1].at(-1) : undefined;
  }

  add(x) {
    let [bucketIndex, index] = this.locate(x, true);
    if (this.buckets.length === 0) {
      this.buckets.push([x]);
      this.size = 1;
      return;
    }
    if (bucketIndex === this.buckets.length) {
      bucketIndex -= 1; // x is larger than everything: append to the last bucket
      index = this.buckets[bucketIndex].length;
    }
    const bucket = this.buckets[bucketIndex];
    bucket.splice(index, 0, x); // shifts at most load items
    this.size += 1;
    if (bucket.length > this.load) {
      this.buckets.splice(bucketIndex + 1, 0, bucket.splice(bucket.length >> 1)); // split in two halves
    }
  }

  remove(x) {
    const [bucketIndex, index] = this.locate(x, false);
    if (bucketIndex === this.buckets.length || this.buckets[bucketIndex][index] !== x) return false;
    const bucket = this.buckets[bucketIndex];
    bucket.splice(index, 1);
    this.size -= 1;
    if (bucket.length === 0) this.buckets.splice(bucketIndex, 1); // never keep an empty bucket
    else this.mergeSmall(bucketIndex);
    return true;
  }

  mergeSmall(bucketIndex) {
    // keeps any two neighbours holding more than load / 2 items between them
    const small = this.load >> 1;
    const bucket = this.buckets[bucketIndex];
    const next = this.buckets[bucketIndex + 1];
    if (next !== undefined && bucket.length + next.length <= small) {
      bucket.push(...next);
      this.buckets.splice(bucketIndex + 1, 1);
      return;
    }
    const previous = this.buckets[bucketIndex - 1];
    if (previous !== undefined && previous.length + bucket.length <= small) {
      previous.push(...bucket);
      this.buckets.splice(bucketIndex, 1);
    }
  }

  has(x) {
    const [bucketIndex, index] = this.locate(x, false);
    return bucketIndex < this.buckets.length && this.buckets[bucketIndex][index] === x;
  }

  ceiling(x) {
    const [bucketIndex, index] = this.locate(x, false);
    return this.buckets[bucketIndex]?.[index];
  }

  higher(x) {
    const [bucketIndex, index] = this.locate(x, true);
    return this.buckets[bucketIndex]?.[index];
  }

  floor(x) {
    const [bucketIndex, index] = this.locate(x, true);
    return this.before(bucketIndex, index);
  }

  lower(x) {
    const [bucketIndex, index] = this.locate(x, false);
    return this.before(bucketIndex, index);
  }

  rank(x) {
    const [bucketIndex, index] = this.locate(x, false);
    let count = index;
    for (let i = 0; i < bucketIndex; i++) count += this.buckets[i].length; // a scan over the buckets
    return count;
  }

  at(index) {
    if (index < 0 || index >= this.size) return undefined;
    for (const bucket of this.buckets) {
      if (index < bucket.length) return bucket[index];
      index -= bucket.length;
    }
  }
}

locate is the one search everything shares: it returns the position of the first item at least x, or, with strict set, the first item greater than x. Then ceiling reads that position, higher reads the strict one, floor and lower step back from them, and rank adds up the buckets before it. add uses the strict position so equal items stay together, and mergeSmall is the clean-up that stops many removals from leaving a long list of nearly empty buckets: after a removal, a bucket and a neighbour that fit together within load / 2 items are joined. That rule keeps every pair of neighbouring buckets holding more than load / 2 items between them, so there are at most about 4n / load + 1 buckets.

Dry run: load 4, adding 5, 1, 9, 3, 7, 4, 8, 2, 6 and then removing four items

How big should the bucket be? The table below is one run in Node 24 on an Apple M2 Pro, with 1,000,000 random integers inserted and then 100,000 calls to rank plus 100,000 to at (median of five runs; the treap row is the class from the last section for comparison). The machine will change every number. The pattern is the lesson: a small load makes updates cheap and queries slow, a large one the reverse, and the middle of the range is flat.

Offline: a Fenwick tree over compressed coordinates

Sometimes the whole set of values is known before the first operation: the numbers come from the input array, or from prefix sums you can compute up front. Then you do not need a tree that finds places for new keys at all. Sort the distinct values once, number them 0 to m − 1 (this is coordinate compression), and keep one count per number in a Fenwick tree. A key's position in the sorted order is its slot, so the five primitives are:

• add(x) and remove(x): add +1 or −1 at the slot of x, found by binary search in the sorted values.
• rank(x): the prefix sum over the slots before the first value that is at least x. x need not be a stored value, so queries may use numbers outside the universe.
• countAtMost(x): the same, up to the last value that is at most x.
• at(i): the Fenwick binary descent from the Segment and Fenwick trees chapter, which finds the smallest slot whose prefix count exceeds i in one O(log m) walk.

The neighbour queries come from the formulas in the first section. Only add is restricted: a value that is not in the universe has no slot, so it throws a RangeError instead of corrupting a count.

class FenwickMultiset {
  constructor(universe) {
    // universe: every value that will ever be added, duplicates allowed
    this.values = [...new Set(universe)].sort((a, b) => a - b);
    this.m = this.values.length;
    this.tree = new Int32Array(this.m + 1); // Fenwick tree over the counts, 1-based
    this.counts = new Int32Array(this.m); // how many copies of each value
    this.size = 0;
    this.top = this.m === 0 ? 0 : 1 << (31 - Math.clz32(this.m)); // largest power of two <= m
  }

  lowerBound(x) {
    let lo = 0;
    let hi = this.m;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.values[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  upperBound(x) {
    let lo = 0;
    let hi = this.m;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.values[mid] <= x) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  bump(x, by) {
    const slot = this.lowerBound(x);
    if (this.values[slot] !== x) throw new RangeError(`${x} is not in the universe`);
    this.counts[slot] += by;
    this.size += by;
    for (let i = slot + 1; i <= this.m; i += i & -i) this.tree[i] += by; // the usual Fenwick update
  }

  add(x) {
    this.bump(x, 1);
  }

  remove(x) {
    const slot = this.lowerBound(x);
    if (this.values[slot] !== x || this.counts[slot] === 0) return false;
    this.bump(x, -1);
    return true;
  }

  prefix(slots) {
    // how many items sit in the first slots compressed positions
    let total = 0;
    for (let i = slots; i > 0; i -= i & -i) total += this.tree[i];
    return total;
  }

  rank(x) {
    return this.prefix(this.lowerBound(x)); // x need not be in the universe
  }

  countAtMost(x) {
    return this.prefix(this.upperBound(x));
  }

  at(index) {
    if (index < 0 || index >= this.size) return undefined;
    let position = 0; // descend the tree: skip every block whose total is still too small
    let remaining = index + 1;
    for (let step = this.top; step > 0; step >>= 1) {
      const next = position + step;
      if (next <= this.m && this.tree[next] < remaining) {
        position = next;
        remaining -= this.tree[next];
      }
    }
    return this.values[position]; // position is the 1-based slot of the last block skipped
  }

  floor(x) {
    return this.at(this.countAtMost(x) - 1);
  }

  lower(x) {
    return this.at(this.rank(x) - 1);
  }

  ceiling(x) {
    return this.at(this.rank(x));
  }

  higher(x) {
    return this.at(this.countAtMost(x));
  }
}

Dry run: universe [3, 5, 5, 8, 10, 12], then add 5, 5, 12, 3, 8

The sorted distinct values are [3, 5, 8, 10, 12], so m = 5 and top = 4. After the five adds the counts per slot are [1, 2, 1, 0, 1] and the Fenwick array (positions 1 to 5) is [1, 3, 1, 4, 1]: position 2 covers slots 1 and 2 (1 + 2 = 3), and position 4 covers all of slots 1 to 4 (1 + 2 + 1 + 0 = 4). The multiset in order is 3, 5, 5, 8, 12.

Each operation is O(log m): one binary search over the values and one Fenwick walk, after an O(m log m) sort. Memory is a few arrays of length m, with no per-key objects, and in the insert timings below it has the fastest inserts: 1,000,000 of them took about 0.2 s, not counting that sort. The price is the limitation in its name. If the next value depends on an earlier answer (an online stream, or a problem where you insert what you just computed), you cannot compress in advance and you need the treap or the buckets. If you only ever query a number, as in the bounds of a range query, it still need not be in the universe; only the numbers you add must be.

Interval maps: My Calendar I, II and III

A set of disjoint intervals, kept in a map from start to end, is an ordered structure, and a handful of problems reduce to asking it for neighbours. The key fact: if the intervals are disjoint, the only one that can reach over a point x is the one with the largest start at or before x, which is floor(x). An earlier interval ends before that one starts, so it cannot reach x either. And the only one that can start inside a range is found by ceiling, and then by repeating the question.

My Calendar I

book(start, end) accepts the half-open range [start, end) if it overlaps no earlier booking. The Intervals chapter shows the O(k) scan. With the bookings in an ordered map keyed by start, only two of them can overlap the new one. The booking with the largest start at or before start overlaps if it ends after start. The booking with the smallest start at or after start overlaps if it begins before end. Any other overlapping booking would have to be one of those two: an overlapping booking that starts at or before start and is not the floor would have to end after the floor's start, and so would overlap the floor too, which disjointness forbids. One that starts after start and before end is at or after the ceiling, which therefore starts before end as well.

class MyCalendar {
  constructor() {
    this.ends = new Treap();
  }

  book(start, end) {
    // bookings are half-open [start, end), keyed by start, with the end as the value
    const before = this.ends.floor(start); // the last booking that starts at or before start
    if (before !== undefined && this.ends.get(before) > start) return false; // it runs past start
    const after = this.ends.ceiling(start); // the first booking that starts at or after start
    if (after !== undefined && after < end) return false; // it begins before the new one ends
    this.ends.set(start, end);
    return true;
  }
}

Dry run: book(10, 20), (15, 25), (20, 30), (5, 10), (8, 12)

A booking costs two descents plus the insert, O(log n) expected, against O(n) for the scan; n bookings cost O(n log n) in total instead of O(n²). Note the strictness: with half-open ranges, "ends exactly where the other starts" is not an overlap, which is why the tests are > and <, not >= and <=.

My Calendar II and III: boundary counts in order

My Calendar II allows a double booking but refuses a triple one. My Calendar III accepts everything and, after each booking, reports the largest number of bookings that overlap at one moment. Disjoint intervals no longer describe the state, since bookings overlap. Store a different set of facts: a map from a time to the number of bookings that start there minus the number that end there. Walking the map in key order and keeping a running total gives the number of bookings active just after each boundary, which is the sweep line from the Intervals chapter. The ordered map's contribution is that the keys are already sorted, with no sort per call.

class MyCalendarTwo {
  constructor() {
    this.delta = new Treap(); // time -> how many bookings start there minus how many end there
  }

  bump(time, by) {
    const next = (this.delta.get(time) ?? 0) + by;
    if (next === 0) this.delta.remove(time); // keep the map free of zero entries
    else this.delta.set(time, next);
  }

  book(start, end) {
    this.bump(start, 1);
    this.bump(end, -1);
    let active = 0;
    for (const [, change] of this.delta.entries()) { // in time order, with no sort
      active += change;
      if (active >= 3) {
        this.bump(start, -1); // undo the tentative booking
        this.bump(end, 1);
        return false;
      }
    }
    return true;
  }
}

class MyCalendarThree {
  constructor() {
    this.delta = new Treap();
  }

  book(start, end) {
    this.delta.set(start, (this.delta.get(start) ?? 0) + 1);
    this.delta.set(end, (this.delta.get(end) ?? 0) - 1);
    let active = 0;
    let most = 0;
    for (const [, change] of this.delta.entries()) {
      active += change;
      most = Math.max(most, active);
    }
    return most;
  }
}

Dry run: the six bookings (10, 20), (50, 60), (10, 40), (5, 15), (5, 10), (25, 55) in My Calendar II

In My Calendar III the same six bookings report 1, 1, 2, 3, 3, 3: the highest total ever seen in the walk. Each call walks the whole map, so it costs O(n) for n boundaries; the ordered map saves the sort, nothing more, so this is honest linear time per booking, the same as a simple list. To get O(log n) there are two routes. One is the dynamic segment tree in the Segment and Fenwick trees chapter. The other uses the treap itself: let refresh also keep, for every subtree, the sum of its changes and the highest running total reached inside it. A node's best is the larger of its left subtree's best, the left sum plus its own change, and that plus the right subtree's best. Key the nodes by the pair (time, change), so that at one moment the −1 of an ending booking sorts before the +1 of a starting one, and the answer to III is the root's best after each insert. It is not worth writing out unless you are asked, but it shows what refresh is for: every extra field is recomputed from the children there.

Intervals that merge as they arrive

Two classic problems keep a set of merged intervals that changes over time. The invariant is the same in both: the stored intervals are disjoint and do not touch, keyed by start, so every question is "look at the floor, then walk forward with ceiling".

Data stream as disjoint intervals

Numbers arrive one at a time with addNum(value), and getIntervals() returns the merged closed intervals so far, sorted: after 1, 3, 7, 2, 6 the answer is [[1, 3], [6, 7]]. A new value does one of five things: it is already covered, it extends the interval on its left, it extends the interval on its right, it joins the two (when it fills a gap of exactly one), or it stands alone. The floor of value is the only interval that can cover it or end right before it. The only interval that can begin right after it is the one with the smallest start above value, and it matters only if that start is exactly value + 1.

class SummaryRanges {
  constructor() {
    this.ends = new Treap();
  }

  addNum(value) {
    // closed intervals [start, end] that are disjoint and never touch, keyed by start
    let start = value;
    let end = value;
    const left = this.ends.floor(value);
    if (left !== undefined) {
      const leftEnd = this.ends.get(left);
      if (leftEnd >= value) return; // already covered
      if (leftEnd === value - 1) start = left; // value extends the interval on its left
    }
    const right = this.ends.higher(value);
    if (right === value + 1) { // an interval begins right after value: absorb it
      end = this.ends.get(right);
      this.ends.remove(right);
    }
    this.ends.set(start, end);
  }

  getIntervals() {
    return [...this.ends.entries()];
  }
}

Dry run: addNum 1, 3, 7, 2, 6

addNum costs O(log n) expected; getIntervals costs O(k) for k intervals, the size of its answer. If numbers repeat, nothing changes, which is what the early return does. The merging shortens the map, so the interval count never exceeds the count of distinct numbers.

Range module: add, remove and query a range

The Range Module tracks half-open ranges [left, right) with addRange, removeRange and queryRange, which asks whether every number in the range is tracked. Keep disjoint, non-touching intervals keyed by start. queryRange is one floor: the only interval that can cover left starts at or before it, and it covers the whole range only if it also reaches right. addRange merges: take the floor if it overlaps or touches left, then absorb every interval that starts inside the growing range, asking ceiling again after each removal. removeRange cuts: the floor may need to be shortened, and it may also stick out past right, in which case its tail survives as a new interval starting at right; then every interval that starts inside [left, right) is removed, again keeping a tail if it sticks out.

class RangeModule {
  constructor() {
    this.ends = new Treap();
  }

  addRange(left, right) {
    // half-open [start, end), disjoint, and never touching, keyed by start
    let start = left;
    let end = right;
    const first = this.ends.floor(left);
    if (first !== undefined && this.ends.get(first) >= left) { // overlaps or touches on the left
      start = first;
      end = Math.max(end, this.ends.get(first));
      this.ends.remove(first);
    }
    for (let next = this.ends.ceiling(start); next !== undefined && next <= end; next = this.ends.ceiling(start)) {
      end = Math.max(end, this.ends.get(next)); // absorb every interval that starts inside [start, end]
      this.ends.remove(next);
    }
    this.ends.set(start, end);
  }

  queryRange(left, right) {
    const start = this.ends.floor(left); // only the interval starting at or before left can cover it
    return start !== undefined && this.ends.get(start) >= right;
  }

  removeRange(left, right) {
    const first = this.ends.floor(left);
    if (first !== undefined && this.ends.get(first) > left) {
      const firstEnd = this.ends.get(first);
      if (first < left) this.ends.set(first, left); // keep the part before left
      else this.ends.remove(first);
      if (firstEnd > right) this.ends.set(right, firstEnd); // keep the part from right on
    }
    for (let next = this.ends.ceiling(left); next !== undefined && next < right; next = this.ends.ceiling(left)) {
      const nextEnd = this.ends.get(next);
      this.ends.remove(next); // it starts inside the removed range
      if (nextEnd > right) this.ends.set(right, nextEnd);
    }
  }
}

Dry run: the stored intervals after each call

Each loop iteration deletes an interval, and every call creates at most two new ones, so the loop work over a whole sequence of calls is bounded by twice the number of calls, and every call costs O(log n) expected amortised. The interval count never exceeds the number of calls made so far.

Exam room: a set of seats and a set of gaps

n seats stand in a row. seat() places a student in the seat that maximises the distance to the closest student, with ties going to the lowest seat number (an empty room gives seat 0), and returns it. leave(p) removes the student in seat p. The seat count can be up to 10⁹ with up to 10⁴ calls, so scanning the row is out.

A first solution keeps the occupied seats in an ordered set and, on seat(), walks all of them in order, measuring the gap before each one. That is O(k) per call for k students, which is acceptable at ten thousand calls and is the answer to give first. The faster idea is that the best seat only changes where something changed. seat() splits one gap into two, leave() joins two gaps into one, and every other gap stays exactly as it was. So store the gaps in a second ordered set whose order is "best first": larger distance first, and the lower seat on a tie. The first element is the answer to seat(), and every update is a few O(log k) operations.

A gap sits between two occupied seats a and b, where −1 stands for the wall before seat 0 and n for the wall after the last seat. Its best seat and distance:

The gap keys are objects, so this is where the comparator earns its keep: (x, y) => y.distance − x.distance || x.seat − y.seat. Two different gaps never share a best seat, so the comparator returns 0 only for the same gap, and remove can find a gap by rebuilding it from a and b, which always gives the same distance and seat.

class ExamRoom {
  constructor(n) {
    this.n = n;
    this.seats = new Treap(); // occupied seats
    this.gaps = new Treap((x, y) => y.distance - x.distance || x.seat - y.seat); // best gap first, ties to the lower seat
    this.addGap(-1, n);
  }

  gapBetween(a, b) {
    // the gap between occupied seats a and b (-1 and n stand for the walls), or null if no seat is free in it
    if (a === -1 && b === this.n) return { a, b, seat: 0, distance: this.n };
    if (a === -1) return b > 0 ? { a, b, seat: 0, distance: b } : null;
    if (b === this.n) return a < this.n - 1 ? { a, b, seat: this.n - 1, distance: this.n - 1 - a } : null;
    return b - a >= 2 ? { a, b, seat: a + ((b - a) >> 1), distance: (b - a) >> 1 } : null;
  }

  addGap(a, b) {
    const gap = this.gapBetween(a, b);
    if (gap !== null) this.gaps.add(gap);
  }

  dropGap(a, b) {
    const gap = this.gapBetween(a, b);
    if (gap !== null) this.gaps.remove(gap);
  }

  seat() {
    const { a, b, seat } = this.gaps.at(0); // the best gap is the smallest key
    this.dropGap(a, b);
    this.seats.add(seat);
    this.addGap(a, seat);
    this.addGap(seat, b);
    return seat;
  }

  leave(p) {
    const a = this.seats.lower(p) ?? -1;
    const b = this.seats.higher(p) ?? this.n;
    this.dropGap(a, p); // the two gaps next to p disappear...
    this.dropGap(p, b);
    this.seats.remove(p);
    this.addGap(a, b); // ...and one wider gap replaces them
  }
}

Dry run: n = 10, then seat, seat, seat, seat, leave(4), seat

After the second seat() the students are at 0 and 9, so the single gap (0, 9) has its best seat at 0 + ⌊9 / 2⌋ = 4. Each call is a handful of O(log k) operations on two treaps, against O(k) for the scan. The brute-force check I ran on random sequences compared every returned seat with a direct search over all free seats.

Sliding window median

Given nums and a window size k, return the median of every window of k consecutive numbers. Sorting each window costs O(k log k), so the whole thing costs O(n k log k). But consecutive windows differ by one number leaving and one entering. Keep the window's numbers in an ordered multiset: add the new number, remove the one that left, and read the middle with at. The median of an odd window is at((k − 1) / 2); of an even window it is the average of at(k / 2 − 1) and at(k / 2). The two indices (k − 1) >> 1 and k >> 1 cover both cases, because for odd k they are the same position, so one formula averages a number with itself.

function medianSlidingWindow(nums, k) {
  const window = new Treap();
  const medians = [];
  for (let i = 0; i < nums.length; i++) {
    window.add(nums[i]); // the new number enters
    if (i >= k) window.remove(nums[i - k]); // the number that fell out of the window leaves
    if (i >= k - 1) {
      const low = window.at((k - 1) >> 1); // the same element as high when k is odd
      const high = window.at(k >> 1);
      medians.push((low + high) / 2);
    }
  }
  return medians;
}

Dry run: [1, 3, −1, −3, 5, 3, 6, 7] with k = 3

The answer is [1, −1, −1, 3, 5, 6]. For k = 2 on [1, 4, 2, 3] the answers are 2.5, 3 and 2.5. The cost is O(n log k) expected with the treap: n additions and n removals on a set of at most k + 1 items. The window briefly holds k + 1 numbers because the new one is added before the old one is removed, which is harmless.

There are three other ways, and which is best depends on k. A sorted array costs O(k) per slide for the shift, O(nk) overall, but with a small constant. On 100,000 random numbers, one run in Node 24 took about 19 ms (sorted array) against about 83 ms (treap) for k = 100, about 90 ms against about 150 ms for k = 5,000, and about 630 ms against about 190 ms for k = 50,000. The array wins while the window is small. Two heaps with lazy deletion (a max-heap for the lower half, a min-heap for the upper half, a count of numbers waiting to be thrown away, and a rebalance after every step) also give O(n log n) in the worst case, because buried dead entries can pile up and the heaps are bounded by n, not k, and the Heaps and priority queues chapter covers the two-heap median and lazy deletion, but the bookkeeping for stale entries is the error-prone part. A Fenwick set over the compressed values is cheaper per operation still, since all the numbers are known up front.

Contains duplicate III: an ordered set, or buckets

Is there a pair of different indices i and j with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff? Compare every number with the previous indexDiff: O(n · indexDiff). Better: keep the previous indexDiff numbers in an ordered set. A close-enough partner for x exists exactly when some stored value lies in [x − valueDiff, x + valueDiff], and the smallest stored value that is at least x − valueDiff is ceiling(x − valueDiff). If even that one is above x + valueDiff, none exists. Then add x, and once the set holds more than indexDiff numbers, remove the oldest. Time: O(n log indexDiff).

function containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff) {
  const window = new Treap();
  for (let i = 0; i < nums.length; i++) {
    const candidate = window.ceiling(nums[i] - valueDiff); // the smallest value that is close enough from below
    if (candidate !== undefined && candidate <= nums[i] + valueDiff) return true;
    window.add(nums[i]);
    if (window.size > indexDiff) window.remove(nums[i - indexDiff]); // keep the last indexDiff numbers
  }
  return false;
}

Dry run: [1, 5, 9, 1, 5, 9], indexDiff = 2, valueDiff = 3

The loop ends with no pair, so the answer is false. Every near miss is a difference of exactly 4, one more than valueDiff.

The bucket trick

This question asks only whether a close pair exists, not for the nearest value, a count or a median, and that permits something cheaper than an ordered set. Cut the number line into buckets of width valueDiff + 1, so bucket b holds the values from b · w to b · w + w − 1. Three facts finish it:

• Two values in the same bucket differ by at most w − 1 = valueDiff, so they are a match.
• Values in buckets that are two or more apart differ by at least w + 1, which is more than valueDiff, so they are never a match.
• Values in adjacent buckets might match, and must be checked by their actual difference.

So the window is a hash map from bucket number to the one value in it. If a bucket would receive a second value, the answer is already true; hence each bucket holds at most one value, and checking the two neighbouring buckets is two lookups. Total time O(n) expected, with no ordered structure.

function containsNearbyAlmostDuplicateBuckets(nums, indexDiff, valueDiff) {
  const width = valueDiff + 1; // two numbers in one bucket differ by at most valueDiff
  const bucketOf = (x) => Math.floor(x / width); // floor, not truncation, so negatives land correctly
  const buckets = new Map();
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    const id = bucketOf(x);
    if (buckets.has(id)) return true; // same bucket: close enough by construction
    if (buckets.has(id - 1) && x - buckets.get(id - 1) <= valueDiff) return true;
    if (buckets.has(id + 1) && buckets.get(id + 1) - x <= valueDiff) return true;
    buckets.set(id, x); // at most one number per bucket, or we would have returned
    if (i >= indexDiff) buckets.delete(bucketOf(nums[i - indexDiff]));
  }
  return false;
}

Dry run: [2, 9, 5], indexDiff = 2, valueDiff = 3, so the width is 4

The values 2 and 5 sit in adjacent buckets, which is exactly the case that needs the real difference. On the earlier input [1, 5, 9, 1, 5, 9] the neighbouring buckets always differ by 4, so it also answers false.

Counting pairs: range sums and reverse pairs

A whole family of problems asks "count the pairs i < j where some condition holds between a value at i and one at j". Sweep j from left to right, keep everything seen so far in an ordered multiset, and for each j ask a rank question: how many earlier values lie in the range this j allows?

Count of range sum. Count the subarrays whose sum lies in [lower, upper]. With prefix sums P (see Prefix sums), the subarray ending at j and starting after i has sum P[j] − P[i]. It counts when lower ≤ P[j] − P[i] ≤ upper, which is P[j] − upper ≤ P[i] ≤ P[j] − lower. So for each new prefix, count the earlier prefixes in that range, then insert the new one. The empty prefix 0 goes in first.

function countRangeSum(nums, lower, upper) {
  const prefixes = new Treap();
  prefixes.add(0);
  let sum = 0;
  let count = 0;
  for (const x of nums) {
    sum += x;
    count += prefixes.countRange(sum - upper, sum - lower); // earlier prefixes P with lower <= sum - P <= upper
    prefixes.add(sum);
  }
  return count;
}

Dry run: [−2, 5, −1] with lower = −2 and upper = 2

The total is 3. Reverse pairs is the same sweep with a different range: for each j, the earlier values larger than 2 · nums[j] number seen.size − seen.countAtMost(2 * nums[j]). Write 2 * x and not x << 1: the shift works on 32-bit integers, and 2147483648 << 1 is 0.

There are three standard ways to count such pairs, and they are all O(n log n).

All three give the same answers; the treap version costs O(n log n) in expectation while the other two are deterministic. Choose by what the problem gives you. A prefix-sum range or "twice as large" condition fits all three. A condition that depends on the inserted values in other ways, or that needs the elements as well as their count, pushes you towards the ordered structure.

Max sum of a rectangle no larger than K

Given an m × n matrix and an integer k, find the largest sum of any rectangular block whose sum is at most k. The all-rectangles scan is O(m² n²) with prefix sums. Kadane's algorithm does not apply, since it finds the best sum without a cap, and with negative numbers a longer subarray is not always bigger.

Reduce to one dimension. Fix a top row and a bottom row; add up each column between them to get a single array of n column sums. A rectangle with those rows is a contiguous subarray of that array. So the problem becomes: the largest subarray sum that is at most k in a one-dimensional array. Take prefix sums P. A subarray ending at index j has sum P[j] − P[i], and we want the largest value that is at most k, so we want the smallest earlier prefix P[i] that is still at least P[j] − k. That is exactly ceiling(P[j] − k) among the earlier prefixes, including the empty prefix 0.

function bestSubarrayAtMost(nums, k) {
  const seen = new Treap();
  seen.add(0);
  let prefix = 0;
  let best = -Infinity;
  for (const x of nums) {
    prefix += x;
    const smallest = seen.ceiling(prefix - k); // the smallest earlier prefix that keeps prefix - P <= k
    if (smallest !== undefined) best = Math.max(best, prefix - smallest);
    seen.add(prefix);
  }
  return best;
}

function maxSumSubmatrix(matrix, k) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const wide = cols >= rows; // pair up the shorter side, scan along the longer one
  const outer = wide ? rows : cols;
  const inner = wide ? cols : rows;
  const cell = (o, i) => (wide ? matrix[o][i] : matrix[i][o]);
  let best = -Infinity;
  for (let top = 0; top < outer; top++) {
    const strip = new Array(inner).fill(0);
    for (let bottom = top; bottom < outer; bottom++) {
      for (let i = 0; i < inner; i++) strip[i] += cell(bottom, i); // strip[i] = column i summed over rows top..bottom
      best = Math.max(best, bestSubarrayAtMost(strip, k));
      if (best === k) return k; // nothing can beat k
    }
  }
  return best;
}

Dry run: the one-dimensional core on [2, 2, −1] with k = 3

The best subarray sum not above 3 is 3, the whole array. For the matrix [[1, 0, 1], [0, −2, 3]] with k = 2, the first pair of rows (the top row alone) gives the strip [1, 0, 1], whose best sum at most 2 is 2, and since nothing can beat k the function returns at once. Time is O(min(m, n)² · max(m, n) · log max(m, n)): there are about min(m, n)² pairs on the shorter side, and each costs one pass of max(m, n) steps with an O(log) set operation. That is why the code pairs up the shorter side. If no rectangle has sum at most k, the code returns −Infinity.

When the language has no TreeMap: what to say

The code in this chapter is the easy part. The harder part, in an interview, is what you say before you write any of it, because the interviewer is listening for whether you know what you need, what your language lacks, and what each way of closing the gap costs. A good answer has four moves.

1. Name the interface, not the library. "I need an ordered multiset with insert, delete and ceiling, each in O(log n)." That sentence shows you know why a hash set is wrong and a heap is not enough.
2. Say what is missing. JavaScript's Set and Map iterate in insertion order and have no floor or ceiling. Sorting the keys on every query costs O(n log n), and an object's keys are not an ordered map either. If you need the neighbour of a key, there is no built-in way to ask for it.
3. Offer the ladder, cheapest first. A sorted array with binary search and splice: short, correct, and O(n) per insert, which is fine for tens of thousands of updates. If the updates are many more, buckets, or a treap, behind the same four methods. If every value is known in advance, a Fenwick tree over the compressed values. State the cost of what you pick, including that an array insert is O(n).
4. Ask before you build. "May I assume an ordered set with these methods, and fill it in if we have time?" is a fair question. If the answer is yes, write against a class with a clear name and do not pretend it exists in the language. If the answer is no, you already have the ladder ready.

Be honest about time. A treap is a few dozen lines for split and merge and about a hundred and fifty with its class, and it is easy to get wrong the first time, so it is worth writing only when the structure is the whole problem, and only if you have practised it. For most problems in this chapter a sorted array with a stated cost is a perfectly good answer, and a sorted array plus a clear sentence on how you would upgrade it is often a better answer than a half-written tree.

How to choose, with numbers

The table below was measured on one machine: Node 24 on an Apple M2 Pro, random integers below 10⁹, median of five runs, times for inserting n values one at a time. The Fenwick column leaves out building its universe; in a separate run that sort and deduplication took about 30 ms for 100,000 values and about 340 ms for 1,000,000, so counted in, the bucket list is ahead of it. Treat the ratios as the lesson, since the milliseconds will not carry over to your machine, your Node version or other data.

The treap is slower than the bucket list and the Fenwick set at these sizes, because each insert does more work: it allocates a node and runs a split and two merges. It is the right default when the problem needs more than the interface: extra aggregates in the nodes, or O(log n) expected cost on rank-heavy workloads, where the bucket list's scan grows with n.

Recognizing it in an unseen problem

• Check what the question needs before choosing: rank and k-th call for sizes (treap, Fenwick), while floor and ceiling alone are satisfied by a sorted array or the bucket list.
• Read the statement for strictness (floor against lower, ceiling against higher) and for duplicates (a set or a multiset) before you write the first call.
• If the data is known in advance, try the offline version first; it is shorter and faster, and it avoids random numbers.