Ordered Set (TreeMap)

At a glance

The instinct

Sorting once is enough when data is static. When keys are inserted and removed between queries, re-sorting every time is O(n log n) per operation and binary search on an ArrayList still costs O(n) per insert. A self-balancing BST - Java's TreeMap and TreeSet (red-black trees) - keeps keys sorted at all times and answers "nearest neighbour" questions in O(log n):

• floorKey(x) - greatest key <= x; lowerKey(x) - strictly < x
• ceilingKey(x) - smallest key >= x; higherKey(x) - strictly > x
• firstKey() / lastKey() - current min / max; pollFirstEntry() removes it
• headMap, tailMap, subMap - range views

Think of it as a hash map that also knows which keys are next to each other.

Recognise it

Not this pattern if...

• All data is known up front - sort once and use two pointers or binary search.
• You only ever need the single min or max and never delete arbitrary elements - a heap is simpler and faster.
• You need "kth smallest" or "how many keys less than x" quickly - TreeMap cannot rank in O(log n); use a Fenwick tree, or an order-statistic tree in other languages.

Memory hack

Analogy - a parking street with numbered spots. When a new car wants to park between spots, you do not inspect every car on the street; you only glance at the car immediately in front and immediately behind. A TreeMap is that glance - it gives you the two neighbours instantly, even as cars come and go.

Say it out loud in the interview:

1. "Data changes between queries, so I keep keys in a TreeMap - O(log n) insert, delete and neighbour lookup."
2. "The only candidates that matter are floor(x) and ceiling(x) - let me check both and handle null."
3. "If values repeat, I store value to count, and remove the key when the count hits zero."

How it works

For My Calendar I, store bookings as start -> end. A new half-open booking [s, e) can only collide with the booking that starts just before it (floor of s) or just after it (ceiling of s). Two O(log n) lookups replace a scan of every booking.

flowchart TD
  A["book(s, e)"] --> B["prev = floorEntry(s)"]
  B --> C{"prev != null and prev.end > s?"}
  C -->|yes| X["reject"]
  C -->|no| D["next = ceilingEntry(s)"]
  D --> E{"next != null and next.start < e?"}
  E -->|yes| X
  E -->|no| F["put(s, e) and accept"]

Trace with bookings [10,20), [15,25), [20,30):

Java template

import java.util.*;

class OrderedSetTemplates {
    // 1) Neighbour check: insert a half-open range only if it overlaps nothing.
    private final TreeMap<Integer, Integer> booked = new TreeMap<>();

    boolean book(int start, int end) {
        Map.Entry<Integer, Integer> prev = booked.floorEntry(start);
        if (prev != null && prev.getValue() > start) return false;   // left neighbour overlaps
        Map.Entry<Integer, Integer> next = booked.ceilingEntry(start);
        if (next != null && next.getKey() < end) return false;       // right neighbour overlaps
        booked.put(start, end);
        return true;
    }

    // 2) Difference map: max overlap online (use for "at most k bookings").
    private final TreeMap<Integer, Integer> delta = new TreeMap<>();

    boolean bookAtMostK(int start, int end, int k) {
        delta.merge(start, 1, Integer::sum);
        delta.merge(end, -1, Integer::sum);
        int active = 0;
        for (int d : delta.values()) {                // keys iterate in sorted order
            active += d;
            if (active > k) {                         // roll back and reject
                delta.merge(start, -1, Integer::sum);
                delta.merge(end, 1, Integer::sum);
                return false;
            }
        }
        return true;
    }

    // 3) Sorted multiset: value -> count, supports remove-one and live min/max.
    private final TreeMap<Integer, Integer> bag = new TreeMap<>();

    void add(int v) { bag.merge(v, 1, Integer::sum); }

    void removeOne(int v) {
        Integer c = bag.get(v);
        if (c == null) return;
        if (c == 1) bag.remove(v); else bag.put(v, c - 1);
    }

    int max() { return bag.lastKey(); }               // throws if empty - guard in real code
    int min() { return bag.firstKey(); }
    Integer closestAtMost(int x) { return bag.floorKey(x); } // null when nothing <= x
}

Complexity

The difference-map walk in template 2 is O(n) per booking, which is fine for the small limits in My Calendar II; a segment tree removes that cost for large inputs.

Variations

• Neighbour conflict check - floor + ceiling around the new key. My Calendar I, nearest seat/parking spot, "contains duplicate within value distance t".
• Difference map / online sweep - counts at sorted boundaries. My Calendar II (at most double booking), car pooling with updates.
• Sorted multiset - value to count, live min/max under corrections. Stock Price Fluctuation (timestamp map + price multiset, or a heap with lazy deletion).
• Interval map merging - store disjoint ranges keyed by start; merge with floor and neighbours on insert (range module, summary ranges from a stream).
• Ordered pruning on a hand-built BST - the same "outside the range, skip that side" thinking applies to Trim a Binary Search Tree.
• Sliding window with order - window min/max/median with deletions via a counted TreeMap.

Common mistakes

• Mixing up inclusive and strict versions: floor is <=, lower is <; ceiling is >=, higher is >.
• Using a TreeSet when values can repeat - duplicates silently disappear. Use a TreeMap of counts.
• Forgetting to remove a key when its count drops to zero, so firstKey()/lastKey() report values that no longer exist.
• Modifying the map while iterating over keySet() or values() - collect changes first or use the iterator's remove().
• Reaching for a TreeMap when a heap suffices, or claiming O(log n) "kth smallest" - Java's TreeMap has no rank query.

All practice problems

4 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.