Some problems need more than a hashmap: “give me the smallest key ≥ x”, “count elements less than x”, “iterate in order”.
That’s the job of ordered containers — balanced BSTs under the hood, O(log n) per operation.
Focus on recognizing:
floor/ceiling/rank/in-order iteration = ordered map or sorted set
The Idiom Per Language
The invariant underneath every ordered structure — insert without ever breaking sort order:
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Ordered Insert (Binary Search)
Insert a key into a sorted array keeping it sorted.
Binary-search the insertion point (upper_bound) in O(log n), then shift the tail right by one and write the key. This bisect idiom underlies ordered sets/maps and lower_bound/upper_bound.
1
pos = upper_bound(sorted, key)
2
# first index with value > key
3
shift elements [pos..end] right by 1
4
sorted[pos] = key
5
# lookups stay O(log n), inserts O(n)
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a");
map.floorKey(7); // greatest key ≤ 7 (null if none)
map.ceilingKey(7); // smallest key ≥ 7
map.lowerKey(7); // strictly below
map.higherKey(7); // strictly above
TreeSet<Integer> set = new TreeSet<>();
set.floor(7); set.ceiling(7);from sortedcontainers import SortedList
sl = SortedList([10])
sl.add(5)
i = sl.bisect_right(7) - 1 # index of greatest element ≤ 7
floor = sl[i] if i >= 0 else None
j = sl.bisect_left(7) # index of smallest element ≥ 7
ceiling = sl[j] if j < len(sl) else None
# stdlib fallback: bisect over a plain sorted liststd::map<int, std::string> m;
m[10] = "a";
auto it = m.lower_bound(7); // first key ≥ 7
if (it != m.begin())
auto floorIt = std::prev(it); // greatest key < 7 (careful at begin)
m.upper_bound(7); // first key > 7
std::set<int> s; // same member functions// No native sorted map. Keep a sorted array + binary search:
function floor(arr, x) { // greatest element ≤ x
let lo = 0,
hi = arr.length - 1,
ans = null;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (arr[mid] <= x) {
ans = arr[mid];
lo = mid + 1;
} else hi = mid - 1;
}
return ans;
}
// insert keeps order: O(n) via splice — fine at interview scale.
// For heavy workloads: segment tree / Fenwick over value ranges.Pattern: Sliding Window Median
Classic consumer of ordered structures — keep the window’s contents in a sorted container; median is a rank lookup:
insert outgoing element's removal + incoming element each step
median = element at rank ⌊k/2⌋ → O(log n) per stepSame skeleton works with two heaps (see Heap section) — but the ordered-container version generalizes to any percentile.
Ordered structure = hashmap’s operations + rank/neighbor queries.
Common Mistakes
Using a hashmap then sorting per query.
Sorting on every query is O(n log n). If queries repeat, maintain order incrementally.
Off-by-one between bisect_left and bisect_right.
bisect_left → first ≥ x · bisect_right − 1 → last ≤ x. Mixing them silently skips duplicates.
C++ prev(begin()).
Calling prev before checking it != begin() is undefined behavior — guard the boundary.
Complexity
| Operation | Time |
|---|---|
| insert / delete | O(log n) |
| floor / ceiling | O(log n) |
| in-order iteration | O(n) total |
| JS sorted-array insert | O(n) |
Premium Content
Unlock Ordered Data Structures and all premium lessons with a subscription.
From ₹199.99/year — See plans