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
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.