Ordered Set

A set that stays sorted while you add and remove: O(log n) for every operation, plus the nearest-neighbor and range queries a hash set cannot answer.

Overview

What an ordered set gives you

An ordered set keeps its elements sorted at all times. You can add and remove elements, and you can ask questions that depend on order: the smallest, the largest, the nearest element below or above a value, or how many elements are smaller than a value. Each of these takes O(log n).

Add or remove — O(1) average — O(n), shifts elements — O(log n)
Contains — O(1) average — O(log n) — O(log n)
Min or max — O(n) — O(1) — O(log n)
Nearest below or above (floor, ceiling) — Not possible — O(log n) — O(log n)
Count of elements below x (rank) — Not possible — O(log n) — O(log n) in Python's SortedList
Walk in sorted order — Sort first, O(n log n) — O(n) — O(n)

Pick it when the collection changes and you need order. If the collection never changes, sort once and binary search. If you only need the minimum, a heap is simpler.

Under the hood, by language

Java and C++ ship an ordered set backed by a balanced binary search tree. Python does not; the usual answers are the sortedcontainers library or the bisect module on a plain list.

Java — TreeSet, TreeMap — A red-black tree (TreeSet is built on TreeMap); log(n) for add, remove and contains — floor, ceiling, lower, higher, first, last
C++ — std::set, std::map — Usually a red-black tree; logarithmic search, insert and erase — lower_bound, upper_bound
Python — sortedcontainers.SortedList — A list of sorted sublists with an index of their lengths; add, remove, indexing and bisect are O(log n), stated as approximate — bisect_left, bisect_right, irange
Python, standard library — list with bisect — A plain list; the search is O(log n) but insort is O(n) because the list shifts — bisect_left, bisect_right

The four nearest-neighbor calls differ only in whether they accept an equal element. With the set {5, 10, 20, 25, 30, 40} and the query 20:

floor — Greatest element ≤ x — 20 — 10
lower — Greatest element x — 25 — 20

Pattern: a sliding window that needs its min and max

'Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit' asks for the longest window whose max minus min is at most the limit. Keep the window's elements in an ordered set: the first element is the min, the last is the max, and both are available as the window grows and shrinks.

1 — 8 — {8} — 0 — keep — 1
2 — 2 — {2, 8} — 6 > 4 — remove 8 from the left — 1
3 — 4 — {2, 4} — 2 — keep — 2
4 — 7 — {2, 4, 7} — 5 > 4 — remove 2 from the left — 2

For [8, 2, 4, 7] with limit 4 the answer is 2. Each element enters and leaves the set once, so the total is O(n log n). Two monotonic deques solve the same problem in O(n); the ordered set is the version you can write without thinking hard, and a SortedList also answers questions the deques cannot, such as the k-th smallest in the window (a TreeSet cannot index, so in Java that needs more).

Pattern: does a new interval overlap?

'My Calendar I' books intervals [start, end) and rejects a booking that overlaps one already stored. Keep the bookings in an ordered map keyed by start. A new interval can only collide with its nearest neighbors on each side.

Pattern: how many are smaller than x

The rank of x is the number of stored elements below it. In Python's SortedList, bisect_left(x) returns exactly that in O(log n). Java's TreeSet API has no rank call; when you need ranks in Java, a Fenwick tree (binary indexed tree) over the value range is the usual replacement. Ranks turn 'count the pairs with a smaller element to the right' into one ordered-set walk.

Duplicates

A set holds each value once. When the same value can appear more than once (a window over an array, for example), use a structure that counts.

Java TreeSet — No — TreeMap from value to count, and delete the key when its count reaches 0
C++ std::set — No — std::multiset
Python SortedList — Yes — SortedList itself; SortedSet is the one that rejects duplicates

What you will be able to do

Say in one sentence why a hash set is not enough for a given problem.
Name the right type in your language and its nearest-neighbor calls.
Write the sliding-window and interval-overlap patterns from memory.
Handle duplicates without a wrong answer.
Offer the simpler alternative (sort once, a heap, or a monotonic deque) when the collection never changes or only the minimum is needed.

When to use it

The collection changes (adds and removes) and you need it in sorted order at every step
You need the nearest element below or above a value (floor, ceiling, predecessor, successor)
A sliding window needs its min and max, or its k-th smallest, as it moves
Intervals are booked or scheduled and each new one must be checked against its neighbors
You need ranks: how many stored elements are smaller than a value
A problem asks for both fast updates and iteration in order, which neither a hash set nor a sorted array gives cheaply

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio