Sorted List — SWE Playbook

01 / 02

Introduction

SortedList is a heap on steroids. With a heap, you can only access the min/max. With SortedList, you can access ANY element by index, add/remove in O(log n), and do binary search.

Import: from sortedcontainers import SortedList

SortedList maintains elements in sorted order automatically. When you add or remove, it rebalances itself (implemented as a balanced BST).

KEY INSIGHT

When to use SortedList:
- Dynamic collection with frequent add/remove
- Need kth smallest/largest element
- Sliding window needing min/max efficiently
- Binary search on a mutable collection

vs Heap: Heap only gives min/max in O(1). SortedList gives ANY index in O(log n).
vs Segment Tree: Often simpler to implement for the same problems.

TimeO(log n) add, O(log n) remove, O(log n) index

SpaceO(n)

SortedList API

Core operations for SortedList.

pythonREFERENCE

from sortedcontainers import SortedList

sl = SortedList([3, 1, 2])  # Creates [1, 2, 3]

# Add/Remove - O(log n)
sl.add(x)           # Add x, maintains sorted order
sl.discard(x)       # Remove x if exists, else do nothing
sl.remove(x)        # Remove x if exists, else raise error

# Indexing - O(log n)
sl[i]               # Get ith element (0-indexed)
sl[-1]              # Get max element
sl[0]               # Get min element
sl.pop(i)           # Remove and return element at index i

# Binary Search - O(log n)
sl.bisect_left(x)   # First index with value >= x
sl.bisect_right(x)  # First index with value > x

Bisect Cheatsheet

Finding elements relative to a value x.

pythonREFERENCE

# If index is -1 or len(sl), the element doesn't exist

# Find LARGEST number < x
idx = sl.bisect_left(x) - 1
val = sl[idx] if idx >= 0 else None

# Find LARGEST number <= x
idx = sl.bisect_right(x) - 1
val = sl[idx] if idx >= 0 else None

# Find SMALLEST number >= x
idx = sl.bisect_left(x)
val = sl[idx] if idx < len(sl) else None

# Find SMALLEST number > x
idx = sl.bisect_right(x)
val = sl[idx] if idx < len(sl) else None

Tuple Sorting Trick

Control sort order with negative values.

pythonREFERENCE

# Tuples sort by first element, then second, etc.
# (1, 'a') < (1, 'b') < (2, 'a')

# To sort by first ASCENDING, second DESCENDING:
# Negate the second value!
sl = SortedList()
sl.add((score, -timestamp))  # Higher timestamp first for same score

# Remember to negate when retrieving
score, neg_ts = sl[0]
timestamp = -neg_ts

02 / 02

Problems

Practice problems using SortedList.

WORKED PROBLEMS3

01Longest Continuous Subarray With Absolute Diff <= LimitMedium

Find longest subarray where max - min <= limit.

pythonREFERENCE

def longestSubarray(self, nums: List[int], limit: int) -> int:
    from sortedcontainers import SortedList

    window = SortedList()
    left = 0
    result = 0

    for right in range(len(nums)):
        window.add(nums[right])

        # Shrink window while invalid
        while window[-1] - window[0] > limit:
            window.remove(nums[left])
            left += 1

        result = max(result, right - left + 1)

    return result

TimeO(n log n)

SpaceO(n)

WHY IT WORKS

Classic sliding window + SortedList. window[0] is min, window[-1] is max. Shrink from left when constraint violated.

Open practice view →Open original problem ↗

02Sequentially Ordinal Rank TrackerHard

Track rankings with add() and get(). The ith call to get() returns the ith best player.

pythonREFERENCE

class SORTracker:
    def __init__(self):
        from sortedcontainers import SortedList
        self.players = SortedList()
        self.query_count = 0

    def add(self, name: str, score: int) -> None:
        # Negate score for descending order
        # For same score, smaller name comes first (ascending)
        self.players.add((-score, name))

    def get(self) -> str:
        result = self.players[self.query_count][1]
        self.query_count += 1
        return result

TimeO(log n) add, O(log n) get

SpaceO(n)

WHY IT WORKS

Use (-score, name) tuple: negate score for descending sort, name for ascending tiebreaker. Track query count for sequential access.

Open practice view →Open original problem ↗

03Finding MK AverageHard

Maintain a stream of integers and return the average of the last m values after removing the k smallest and k largest values. Return -1 until at least m values have arrived.

pythonREFERENCE

from collections import deque
from sortedcontainers import SortedList

class MKAverage:
    def __init__(self, m: int, k: int):
        self.m = m
        self.k = k
        self.window = deque()
        self.sorted_window = SortedList()

    def addElement(self, num: int) -> None:
        self.window.append(num)
        self.sorted_window.add(num)
        if len(self.window) > self.m:
            old = self.window.popleft()
            self.sorted_window.remove(old)

    def calculateMKAverage(self) -> int:
        if len(self.window) < self.m:
            return -1
        middle = self.sorted_window[self.k:self.m - self.k]
        return sum(middle) // len(middle)

TimeO(log m) add, O(m) calculate in this direct version

SpaceO(m)

WHY IT WORKS

The source idea is to maintain the last m values in both arrival order and sorted order. A production version keeps separate bottom/middle/top SortedLists plus a middle sum so calculateMKAverage is O(1).

Open practice view →Open original problem ↗

NEXT PATTERNSegment Tree→