Ordered sets & sorted containers
Overview
Data structures that maintain elements in sorted order while allowing fast (O(log n)) insertions, deletions, and lookups.
Standard arrays are O(n) to insert into. Hash sets are O(1) to insert but lose ordering. Sorted containers provide the best of both worlds for dynamic data that must remain ordered.
Where used: Leaderboards, Interval sweeping algorithms, Finding the closest value to a target dynamically
Why learn this
- It teaches you about the capabilities of Balanced Binary Search Trees (like Red-Black Trees).
- Knowing when your language has (or lacks) this built-in is crucial for interviews.
- It bridges the gap between searching and dynamic updates.
Common mistakes
- Assuming Python has a built-in Balanced BST: C++ has `std::set`, Java has `TreeSet`, but Python standard library lacks a true balanced BST. You must rely on external libraries (like `sortedcontainers`), use a heap, or use `bisect` on a list (which takes O(N) for insertion).
- Using them instead of Hash Sets for exact lookups: If you only need to check if an element exists, a Hash Set is O(1). A Sorted Set is O(log N). Don't pay the logarithmic penalty if you don't care about the ordering.
Recall questions
- What is the typical time complexity for insert, delete, and search in a Sorted Set (like C++ `std::set`)?
- What underlying data structure usually powers standard library sorted containers?
Understanding checks
You are receiving a stream of integers. At any point, you need to find the element currently in the stream that is strictly greater than `X`. Should you use a Max Heap, a Hash Set, or a Sorted Set?
A Sorted Set.
A Hash Set has no order. A Max Heap only gives you the absolute maximum, not the 'next largest after X'. A Sorted Set allows logarithmic search (e.g., `upper_bound`) for arbitrary targets.
If you use `bisect.insort` to maintain a sorted list in Python, what is the time complexity of adding a new element?
O(N).
While `bisect` finds the insertion point in O(log N) time via binary search, actually inserting the element into a contiguous array requires shifting all subsequent elements, which is O(N).
Practice tasks
My Calendar I
Design a calendar system that allows you to add new events (start, end) only if they do not double-book an existing event. (Conceptualize how a Sorted Set of intervals solves this).
Continue learning
Previous: Hash Sets vs Maps
Previous: Binary Search