Ordered Structures in Python

Java has TreeMap. C++ has std::map and std::set. Python has neither, and that gap is a genuine interview problem: a question that a Java candidate answers with one data structure requires you to know three fallbacks and to justify your choice out loud.

This page is that justification. It is short on algorithms and long on judgement, because judgement is what is actually being tested — “I would use a TreeMap” is not an available answer, and “I would sort it” is often the wrong one.

What you’ll learn

• What bisect gives you, and the precise reason it is not a TreeMap.
• The three real options, and the one question that decides between them.
• Why sortedcontainers is the competitive-Python answer and why you must say it is third-party.
• The specific problems where this gap shows up: sliding-window medians, “find the closest element”, interval overlap checks, and LC 220.

The cue

You need an ordered structure when…

• You need the predecessor or successor of a value — the largest element below x, or the smallest above it. A hash map cannot answer this at any price.
• You need range queries: how many elements lie in [lo, hi], or what is the closest value to x.
• You need the k-th smallest repeatedly, and the collection keeps changing. A heap gives you only the extremes; sorting once gives you nothing after the first insert.
• You are maintaining a sorted view of a moving window.

The question that decides your answer: are writes frequent?

• Rare writes, many queries → a plain sorted list plus bisect. Queries are $O(\log n)$; each insert is $O(n)$ because of the shift.
• Frequent writes and queries → sortedcontainers.SortedList, $O(\log n)$ for both — but it is third-party, and you must say so.
• Only the extremes matter → heapq. Do not reach for an ordered structure when a heap suffices.

Reach for something else when you only need membership or key lookup (a dict or set — do not pay for ordering you never use), or when the data is static and you can simply sort once.

Visual intuition

bisect_left is the primitive everything here is built on. It answers “where would this go”, which is strictly more useful than “is it present”:

searchbisect_left: the first index where arr[i] >= targetO(log n)

search space

103132337495

1def lower_bound(a, target):2    lo, hi = 0, len(a)            # hi is EXCLUSIVE here3    while lo < hi:                # so the test is <4        mid = (lo + hi) // 25        if a[mid] < target:6            lo = mid + 17        else:8            hi = mid              # keep mid as a candidate9    return lo   # first index where a[i] >= target

target3

setupThe exclusive-upper-bound convention. It looks like a small change from the exact-match version, but it is what makes this variant able to answer "where would it go" rather than "is it there" — and it never returns −1, so callers need no special case.

Play‹›1/5⟲

Note it never returns -1. For an absent value it returns the insertion point, which is exactly what makes it usable for predecessor and successor queries. bisect_right is the same loop with <= — and the gap between the two is the count of occurrences.

The three options, honestly

	sorted list + bisect	SortedList	heapq
search / rank	$O(\log n)$	$O(\log n)$	$O(n)$
insert	$O(n)$	$O(\log n)$	$O(\log n)$
delete	$O(n)$	$O(\log n)$	$O(\log n)$ arbitrary: $O(n)$
min / max	$O(1)$	$O(1)$	$O(1)$ min only
k-th smallest	$O(1)$	$O(\log n)$	$O(n \log n)$
predecessor / successor	$O(\log n)$	$O(\log n)$	not supported
in the standard library	yes	no	yes

The O(n) insert is the trap, and it is easy to miss

bisect.insort finds the position in $O(\log n)$ and then shifts every element after it, so the insert is $O(n)$. In a loop that is $O(n^2)$ — perfectly fine at $n = 1000$ and a time-limit exceeded at $n = 10^5$.

The bisect docs say this explicitly, and it is the single most common way this pattern goes wrong: the binary search makes the code look logarithmic.

What bisect actually gives you

Four queries, all built from two functions:

ordered_queries.py

import bisect
 
arr = [1, 3, 5, 7, 9]        # must already be sorted
 
# 1. Insertion point / rank
bisect.bisect_left(arr, 5)    # 2  -> first index where arr[i] >= 5
bisect.bisect_right(arr, 5)   # 3  -> first index where arr[i] >  5
 
# 2. Count of a value  =  the gap between them
bisect.bisect_right(arr, 5) - bisect.bisect_left(arr, 5)   # 1
 
# 3. Predecessor: largest element strictly less than x
i = bisect.bisect_left(arr, 6)
pred = arr[i - 1] if i > 0 else None          # 5
 
# 4. Successor: smallest element >= x
j = bisect.bisect_left(arr, 6)
succ = arr[j] if j < len(arr) else None       # 7
 
# 5. Count in a range [lo, hi] inclusive
bisect.bisect_right(arr, 7) - bisect.bisect_left(arr, 3)   # 3
 
# Insertion keeps it sorted -- but note the cost.
bisect.insort(arr, 4)         # O(n): binary search, then SHIFT
print(arr)                    # [1, 3, 4, 5, 7, 9]

Everything an ordered structure is asked for reduces to those two calls plus an index adjustment. Memorise the predecessor and successor idioms — the i - 1 and the bounds guards are where mistakes happen under pressure.

Dry run

LC 220 Contains Duplicate III — the canonical problem for this gap. Given nums, is there a pair within index distance k whose values differ by at most t?

nums = [1, 5, 9, 1, 5, 9], k = 2, t = 3. Maintain a sorted window of the last k values and, for each new value v, ask for the successor of v - t:

i	v	window (sorted)	look for successor of v - t	found	in range?
0	1	[]	−2	none	—
1	5	[1]	2	none	—
2	9	[1, 5]	6	none	—
3	1	[5, 9]	−2	5	5 − 1 = 4 > 3, no
4	5	[9, 1] → [1, 9]	2	9	9 − 5 = 4 > 3, no
5	9	[1, 5]	6	none	—

Answer False.

Two things worth reading off that table:

• One successor query answers the whole question. The smallest value that is at least v - t is the only candidate worth checking: anything smaller is out of range below, and if this one exceeds v + t then so does everything above it. That reduces a pairwise scan to one $O(\log k)$ lookup.
• The window must support deletion, not just insertion, because values leave as the window slides. That is what rules out a heap: heapq has no efficient removal of an arbitrary element.

With bisect on a list this is $O(n \cdot k)$ because of the shifts; with SortedList it is $O(n \log k)$. State which you are writing and why.

Complexity

Problem	With bisect on a list	With SortedList
LC 220 Contains Duplicate III	$O(n \cdot k)$	$O(n \log k)$
LC 480 Sliding Window Median	$O(n \cdot k)$	$O(n \log k)$
LC 493 Reverse Pairs	$O(n^2)$	$O(n \log n)$
Static: count in range, closest value	$O(\log n)$ per query after an $O(n \log n)$ sort	same

The pattern is consistent: bisect costs a factor of the window size on writes, and buys you standard-library availability. Whether that trade is acceptable depends entirely on the constraints, which is why reading them first matters.

The variant map

Need	Approach
Count elements < x (rank)	bisect_left(arr, x)
Count occurrences of x	bisect_right - bisect_left
Closest element to x	compare arr[i-1] and arr[i] at i = bisect_left(arr, x)
Predecessor (strictly less)	arr[bisect_left(arr, x) - 1], guarding i > 0
Successor (greater or equal)	arr[bisect_left(arr, x)], guarding i < len(arr)
Count in [lo, hi]	bisect_right(arr, hi) - bisect_left(arr, lo)
Sliding-window median	two heaps, or SortedList and index the middle
Insert keeping order	bisect.insort — $O(n)$, so beware
Sort by a key	bisect with a key= argument (Python 3.10+), or keep a parallel key list

Two heaps versus SortedList for a sliding-window median

Two heaps give $O(\log n)$ insertion but cannot delete an arbitrary element, so a sliding window needs lazy deletion — a map of pending removals, purged when the offending element reaches a heap root. That is genuinely fiddly.

SortedList supports .remove() in $O(\log n)$ directly and lets you index the middle, which makes LC 480 almost trivial. If the platform has sortedcontainers, say so and use it; if not, lazy deletion is the fallback and worth naming as such.

Pitfalls

• Assuming bisect.insort is $O(\log n)$. The search is; the insert is $O(n)$. This is the defining trap of this page.
• Using bisect on an unsorted list. It returns nonsense silently — no error, no warning. The precondition is yours to maintain.
• Off-by-one in the predecessor idiom. bisect_left gives the insertion point, so the predecessor is at i - 1 and you must guard i > 0.
• Confusing bisect_left and bisect_right on duplicates. left gives the start of a run of equal values, right gives one past its end. For a predecessor query with duplicates, left is what you want.
• Assuming sortedcontainers is importable. It is third-party. LeetCode has it; a bare CoderPad or a company’s own judge may not. Have the bisect fallback ready and say which you are relying on.
• Reaching for an ordered structure when a heap would do. If you only need the minimum, use heapq — it is simpler and in the standard library.

Interview follow-ups

They ask	What they’re checking	The answer
“Python has no TreeMap. What do you use?”	Whether you know the gap exists	A sorted list plus bisect for read-heavy work, sortedcontainers.SortedList for balanced read/write. Name that SortedList is third-party
“What is the complexity of insort?”	Whether you read the docs	$O(\log n)$ to find the position, $O(n)$ to insert because of the shift. So the operation is $O(n)$
“Then how is your solution $O(n \log n)$?”	Honesty	It is not, with bisect — it is $O(n \cdot k)$. Either accept that given the constraints, or use SortedList, or implement a Fenwick tree over compressed values
“sortedcontainers is not available”	Whether you have a fallback	bisect and accept the $O(n)$ insert; or two heaps with lazy deletion; or a Fenwick tree over coordinate-compressed values for rank queries
“Difference between bisect_left and bisect_right?”	Precision	left returns the first index where arr[i] >= x, right the first where arr[i] > x. On duplicates they bracket the run, and the gap is the count
“Count elements less than x in a changing array”	Whether you know the real tool	A Fenwick tree over compressed values: $O(\log n)$ for both update and prefix count. That is what SortedList is doing internally

Practice

5 problems

1 easy1 medium3 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○35Search Insert PositioneasyLeetCode Top Interview 150
• ○981Time Based Key-Value StoremediumNeetCode 150
• ○220Contains Duplicate IIIhard
• ○480Sliding Window Medianhard
• ○493Reverse Pairshard

Exercises

Predecessor and successor with bisect

pch.exerciseTag pch.exerciseTitle

Count in a range, and count occurrences

pch.exerciseTag pch.exerciseTitle

LC 220 — Contains Duplicate III · Hard

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag Ordered structures in Python — self-check

1. What is the time complexity of bisect.insort?

   A O(log n) — it uses binary search B O(n) — the search is O(log n) but inserting shifts every later element C O(1) amortised D O(n log n)
   pch.quizShowAnswer

   B — O(n) — the search is O(log n) but inserting shifts every later element — This is the defining trap of the pattern: the binary search makes the code LOOK logarithmic. In a loop it is O(n squared) — fine at n=1000, TLE at n=100000.

2. Python has no TreeMap. What do you tell an interviewer?

   A That the problem cannot be solved in Python B Sorted list plus bisect for read-heavy work; sortedcontainers.SortedList for balanced read/write — and note that SortedList is third-party C Use a dict, which is ordered since 3.7 D Sort the list before every query
   pch.quizShowAnswer

   B — Sorted list plus bisect for read-heavy work; sortedcontainers.SortedList for balanced read/write — and note that SortedList is third-party — A dict preserves INSERTION order, not sorted order, so it answers none of these queries. Naming the third-party caveat matters because a bare CoderPad may not have sortedcontainers.

3. bisect_left versus bisect_right — what is the difference, and what is the gap between them?

   A They are aliases B left gives the first index where arr[i] >= x, right the first where arr[i] > x — so on duplicates they bracket the run and the gap is the count C left searches the left half only D right is for descending arrays
   pch.quizShowAnswer

   B — left gives the first index where arr[i] >= x, right the first where arr[i] > x — so on duplicates they bracket the run and the gap is the count — That gap is how you count occurrences in O(log n). For a predecessor query with duplicates you want left, since it lands at the start of the run.

4. Why can two heaps not directly handle a sliding-window median?

   A Heaps cannot hold duplicates B Because a heap has no efficient removal of an arbitrary element, and a sliding window must delete the value that just left C Because heaps are unsorted D They can, with no modification
   pch.quizShowAnswer

   B — Because a heap has no efficient removal of an arbitrary element, and a sliding window must delete the value that just left — Insertion is fine; deletion is the problem. The workaround is lazy deletion with a map of pending removals purged at the roots — fiddly, which is why SortedList makes LC 480 almost trivial.

5. You need to count elements less than x in an array that keeps changing. What is the right tool?

   A bisect on a sorted list B A Fenwick tree over coordinate-compressed values — O(log n) for both update and prefix count C A hash map of counts D Re-sort before each query
   pch.quizShowAnswer

   B — A Fenwick tree over coordinate-compressed values — O(log n) for both update and prefix count — bisect gives O(log n) queries but O(n) updates. Once both are frequent you need a structure logarithmic in both, which is what SortedList uses internally and what a Fenwick tree gives you in the standard library.

Recall card

• The gap — Python has no TreeMap or std::map. Know the three fallbacks and say which you are using.
• The deciding question — are writes frequent? Rare writes → sorted list plus bisect. Frequent → SortedList (third-party). Only extremes → heapq.
• bisect_left — first index where arr[i] >= x. Never returns −1; returns the insertion point.
• insort is $O(n)$ — the search is logarithmic, the shift is not. This is the trap.
• Idioms — predecessor arr[i-1] guarding i > 0; successor arr[i] guarding i < len; count in range bisect_right(hi) - bisect_left(lo).
• Both frequent? Fenwick tree over compressed values — $O(\log n)$ either way.

Recap

• The missing TreeMap is a real interview problem in Python, and the answer is judgement rather than an algorithm.
• bisect answers rank, count, predecessor, successor and range-count in $O(\log n)$ — but insertion is $O(n)$, and saying so unprompted is the mark of someone who has actually used it.
• sortedcontainers.SortedList is the competitive-Python answer; name it as third-party and keep a fallback.
• When reads and writes are both hot, the real tool is a Fenwick tree over coordinate-compressed values.

Next: Graph Representations — choosing storage by density and by the operation you repeat.