patternDSA/Ordered Set

Core Pattern → Pattern 29

Ordered Set

When you need the predecessor or successor of a value in O(log n), a sorted structure beats a dict or heap. SortedList maintains order on every insert and delete — the Python equivalent of C++'s std::set.

Frequency:★★★☆☆

·~25 min·Intermediate·4 problems

Prev Merge Intervals

The Core Shock

Hash map: O(1) exact lookup but O(n) for predecessor/successor. Sorted structure: O(log n) for everything — insert, delete, predecessor, successor, range min/max.

dict / set

O(1) lookup

Exact lookup only. 'What's the largest element smaller than x?' requires scanning all keys.

sorted list + bisect

built-in

O(log n) all

bisect_left gives predecessor position. Standard library, no install needed. O(n) remove on plain list.

SortedList

pip install

O(log n) all

sortedcontainers package. O(log n) add and remove. Predecessor via bisect_left. The Python std::set.

The pattern activates when you need to answer: "what is the nearest value smaller/larger than x in my current set?" This is the predecessor/successor query — impossible in O(log n) with a hash map, trivial with a sorted structure and bisect.

bisect + SortedList Cheatsheet

Two tools: bisect module (built-in) and sortedcontainers.SortedList (pip).

bisect module (built-in)

bisect_left(a,x)index of first elem ≥ x

bisect_right(a,x)index of first elem > x

insort(a,x)insert x keeping sorted (O(n) shift)

a[bisect_left(a,x)-1]predecessor (largest < x)

a[bisect_left(a,x)]successor (smallest ≥ x)

SortedList (sortedcontainers)

sl.add(x)O(log n) insert

sl.remove(x)O(log n), raises if absent

sl.discard(x)O(log n), safe (no error)

sl[0] / sl[-1]min / max O(log n)

sl.bisect_left(x)same semantics as bisect module

The 3-Step Framework

Sort → bisect to position → check predecessor/successor.

Choose the sorted structure

bisect on a plain list works for read-heavy problems (many queries, few inserts). SortedList is better when elements are added/removed dynamically (calendar booking, sliding window). For static data, sort once and use bisect throughout.

# Static (sort once, many queries):
nums.sort()
idx = bisect_left(nums, target)

# Dynamic (inserts + queries):
from sortedcontainers import SortedList
sl = SortedList()
sl.add(x)  # O(log n)

sortedcontainers is available in LeetCode Python environments. Always check if you need O(log n) removal — if yes, use SortedList (plain list + bisect has O(n) removal due to list shifting).

Bisect to find predecessor / successor

bisect_left(sl, x) gives the index where x would be inserted. The predecessor is at index-1 (if exists), the successor is at that index (if exists). Always bounds-check before accessing.

idx = sl.bisect_left(x)
# Predecessor: largest value < x
if idx > 0:
    pred = sl[idx - 1]
# Successor: smallest value >= x
if idx < len(sl):
    succ = sl[idx]

For interval overlap: successor.start < new.end checks right overlap. predecessor.end > new.start checks left overlap. These two checks cover all cases — intervals further out can't overlap if their immediate neighbor doesn't.

Apply the range or window constraint

Sliding window + SortedList: after adding right element, while sl[-1]-sl[0] > limit, remove the left element. The SortedList always gives O(log n) max and min via sl[-1] and sl[0]. This beats two monotonic deques when removals aren't from the ends.

sl = SortedList()
left = 0
for right, v in enumerate(nums):
    sl.add(v)
    while sl[-1] - sl[0] > limit:
        sl.remove(nums[left])
        left += 1
    result = max(result, right-left+1)

sl.remove(v) removes by VALUE not by index. If the window has duplicate values, it removes exactly one occurrence (the first found). This is exactly what you want for sliding windows where you remove nums[left] as left advances.

Pattern Recognition

'predecessor', 'nearest smaller/larger', 'sorted window' → ordered set.

Use Ordered Set When

"Is there a booking that overlaps with [s,e]?"

"Largest element smaller than x in current set"

Sliding window where max−min ≤ limit

Dynamic sorted structure (insert + delete + query)

"Find nearest value to x in evolving set"

132 Pattern: find element in range (lo, hi) in log n

Merge Similar Items: SortedDict for sorted output

"K closest points" with dynamic updates

Common Pitfalls

bisect_left vs bisect_right confusion — off-by-one on duplicates

Forgetting bounds check: idx-1 < 0 or idx >= len(sl)

Using insort on plain list for repeated inserts — O(n) shifting

sl.remove() raises ValueError if element absent — use discard

Overlap check direction: successor.start < new.END (not ≤)

Half-open [s,e): adjacent [10,20) and [20,30) don't overlap

sortedcontainers not available? Use bisect + list (slower remove)

132 Pattern: easier with monotonic stack — don't over-engineer

On this page