When to Use an Ordered Map (Sorted Dict / TreeMap)
An ordered map maintains keys in sorted order with O(log n) insert, delete, and lookup, plus O(log n) predecessor/successor queries and O(k) range queries. Python’s sortedcontainers.SortedList / SortedDict, Java’s TreeMap, C++ map. Use when: you need the smallest/largest key, predecessor/successor of a key, or a range of keys — operations that a regular hashmap cannot do efficiently.
SortedList in Python (sortedcontainers)
from sortedcontainers import SortedList, SortedDict sl = SortedList() sl.add(5); sl.add(2); sl.add(8) # sl = [2, 5, 8] sl.bisect_left(5) # → 1 (index of first ≥ 5) sl.bisect_right(5) # → 2 (index of first > 5) sl[0] # smallest: 2 sl[-1] # largest: 8 del sl[sl.index(5)] # remove 5
O(log n) add/remove, O(log n) bisect, O(1) index access. Not a built-in — use import bisect on a regular list for simpler cases.
My Calendar / Booking Overlap (LC 729, 731, 732)
Use a SortedDict mapping start→end for booked intervals. On each new booking [s,e): find the nearest existing event before s (predecessor) and after s (successor). Check for overlap with both.
from sortedcontainers import SortedDict
class MyCalendar:
def __init__(self):
self.calendar = SortedDict() # start -> end
def book(self, start, end):
idx = self.calendar.bisect_right(start) - 1
# Check predecessor: its end must be = 0:
prev_start = self.calendar.keys()[idx]
if self.calendar[prev_start] > start:
return False
# Check successor: its start must be >= end
if idx + 1 < len(self.calendar):
next_start = self.calendar.keys()[idx + 1]
if next_start < end:
return False
self.calendar[start] = end
return True
Count of Smaller Numbers After Self (LC 315)
Use a SortedList. Process right to left: for each element, bisect_left gives the count of elements already in the list that are smaller. Add the element after querying.
from sortedcontainers import SortedList
def countSmaller(nums):
sl = SortedList()
result = []
for n in reversed(nums):
result.append(sl.bisect_left(n))
sl.add(n)
return result[::-1]
Sliding Window Maximum (LC 239) — Deque Alternative
Maintain a SortedList of the current window. On each step: add the new element, remove the expired element (at index i-k), query the maximum (last element). O(n log k).
def maxSlidingWindow(nums, k):
from sortedcontainers import SortedList
sl = SortedList()
result = []
for i, n in enumerate(nums):
sl.add(n)
if i >= k:
sl.remove(nums[i - k])
if i >= k - 1:
result.append(sl[-1])
return result
Note: monotonic deque is O(n) for this problem. SortedList is O(n log k) but is more general.
K Closest Points / K-th Order Statistics
SortedList can maintain a dynamic sorted sequence where you need both order and efficient add/remove — unlike a heap which only efficiently accesses the min/max. Use SortedList when you need the k-th element (not just min/max), or when you need both rank and value queries on the same structure.
Find Right Interval (LC 436)
For each interval, find the interval with the smallest start >= the end of the current interval. Build a SortedDict of start → index. For each interval [s,e), query bisect_left(e) to find the first start >= e.
When to Use Each Structure
- SortedList/TreeMap: predecessor/successor queries, range queries, need the k-th element, dynamic order statistics
- Heap: only need min or max, don’t need ordered iteration
- Segment tree / BIT: range sum/min/max queries with point updates
- Regular hashmap: O(1) lookup by key, don’t need ordering
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”When should you use a sorted list or TreeMap instead of a heap?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a SortedList/TreeMap when you need more than just the min or max. A heap gives you O(1) access to the single extreme value. A SortedList/TreeMap gives you: predecessor/successor of any key in O(log n), the k-th smallest element by index in O(log n), range queries returning all keys in [a, b) in O(log n + k), and efficient arbitrary removal in O(log n). Use a heap when you only need repeated min/max extraction. Use SortedList when you need order statistics, range queries, or need to find the element just before or after a given value.”}},{“@type”:”Question”,”name”:”How do you solve My Calendar (LC 729) and prevent booking overlaps?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a SortedDict mapping start_time to end_time. On each booking [s, e): find the predecessor (last interval starting before s) using bisect_right(s)-1. Check its end is <= s (no overlap). Find the successor (first interval starting at or after s) using index bisect_right(s). Check its start is >= e (no overlap). Only if both checks pass, insert the booking. This is O(log n) per booking. The key insight is that with a sorted structure you only need to check the immediate predecessor and successor — any other interval cannot overlap if those two do not.”}},{“@type”:”Question”,”name”:”How does Count of Smaller Numbers After Self (LC 315) work with a SortedList?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Process the array right to left. Maintain a SortedList of elements seen so far (elements to the right of the current position). For each element nums[i], call bisect_left(nums[i]) — this returns the count of elements in the SortedList that are strictly less than nums[i], which is exactly the count of smaller numbers to its right. Then add nums[i] to the SortedList and continue. Time complexity is O(n log n). The SortedList approach is simpler to implement than a Binary Indexed Tree (BIT/Fenwick tree) with coordinate compression, though both achieve the same asymptotic complexity.”}},{“@type”:”Question”,”name”:”How does the sliding window maximum (LC 239) work using a SortedList?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain a SortedList of the current window of size k. For each new position i: add nums[i] to the SortedList. If i >= k, remove nums[i-k] (the element sliding out of the window). The current maximum is sl[-1] (the last/largest element). Time O(n log k). Note that a monotonic deque solves the same problem in O(n) by maintaining a decreasing deque of indices. The SortedList approach is O(n log k) but applies to more general problems — for example, if you need both the max and min of the window simultaneously, a deque cannot easily do this but a SortedList handles it trivially with sl[-1] and sl[0].”}},{“@type”:”Question”,”name”:”What is the difference between SortedList, SortedDict, and SortedSet in Python sortedcontainers?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”SortedList: maintains a sorted sequence of values, allows duplicates. Methods: add(val), remove(val), discard(val), bisect_left(val), bisect_right(val), index access sl[k]. Time O(log n) for add/remove, O(log n) for bisect. SortedDict: a dictionary whose keys are always sorted. Same as a regular dict but keys() returns keys in sorted order. Supports bisect_key_left(k), bisect_key_right(k), peekitem(0) for smallest key-value pair. SortedSet (SortedKeyList with key=lambda x: x): a SortedList that discards duplicates. In practice, use SortedList for multisets (duplicates OK) and SortedDict when you need key→value mapping with sorted key order. All three have O(log n) operations and are backed by a list-of-lists structure internally.”}}]}
Google coding interviews test ordered map and tree-based data structure patterns. See common questions for Google interview: ordered map and sorted data structure problems.
Meta coding interviews cover interval scheduling and ordered data structures. Review patterns for Meta interview: sorted list and interval scheduling problems.
Amazon coding interviews test calendar booking and sorted structure patterns. See problems for Amazon interview: ordered map and calendar booking problems.