SHELL · LOOPS · LIST · STRING · DICT · SET · COLLECTIONS · SORTING · HEAPQ · ITERTOOLS

Python for LeetCode:
the building blocks every solution uses

A LeetCode solution is one Python method, and almost every line in it uses one of about twenty containers and standard-library tools. This is a reference for those tools: what each one is for, what each operation costs, and the code you type for it.

Every sample works on the same few inputs, so you can compare tools on one set of values: the list nums = [3, 1, 4, 1, 5, 9, 2, 6], the string "banana", six words (eat, tea, tan, ate, nat, bat), a 3-by-4 grid of 0s and 1s, four edges between nodes 0 to 3, four intervals and three prioritised tasks. They arrive the way LeetCode passes them: as arguments, already Python objects.

Here is the toolbox of one solution. Each container answers one question fast: the item at a position, the value for a key, or the smallest item by value. Most boxes won’t mean much yet; each chapter explains one.

MapEach blue tag names the chapter that explains that part. Solid boxes are your class and method; dashed boxes group tools by the question they answer.

You need to know Python syntax: functions, loops, and lists and dicts in passing. This is not an algorithms tutorial; the DSA tutorials build on these blocks. Samples run on Python 3.14, the version LeetCode lists, with type hints on every function and empty container, and features newer than 3.9 carry the release that added them. Tap any figure to open it full screen and zoom. are tappable. Timings come from one run of CPython 3.14.7 on an Apple M2 Pro laptop on 17 November 2026; yours will differ, and the ratios between them hold.

The solution shell: class Solution, helpers and a local harness

LeetCode shows you a class with one empty method, and its judge calls that method once for every test case. Everything you write lives inside that class: the method and the helpers it calls. Linked lists and trees arrive as small classes LeetCode defines for you, and the same file runs on your own machine only after a few more lines. What does the judge call, and what do you need to run it locally?

STEP 01 / 04

THE MAP SO FAR

Fig 1.1The accent parts are new: the judge and your harness on top, the class and method they call.

The creates one Solution object, calls one method with each test’s arguments, and compares the value the method returns with the expected answer. Anything you print appears in the console and plays no part in the verdict.

On your own machine, a local harness does the judge’s job with assert. Linked lists and trees arrive as ListNode and TreeNode objects, two small classes LeetCode defines, and helper functions live inside the method.

STEP 02 / 04

THE SIGNATURE TELLS YOU WHAT TO RETURN

Fig 1.2Two names, one list. The accent arrow writes into the judge’s list; the red one points your name elsewhere.

In def twoSum(self, nums: List[int], target: int) -> List[int], the name the input and return types; Python never checks them while running. LeetCode’s templates still print List[int] and Optional[TreeNode] from typing. This tutorial writes the built-in forms, list[int] (3.9) and TreeNode | None (3.10), which LeetCode’s Python 3.14 accepts.

Annotate empty containers, since nothing else says what goes in: seen: set[int] = set(). “Modify nums in-place” means -> None and a change to the caller’s list: nums.sort() and nums[:] = … write into it, while nums = sorted(nums) only points your local name at a new list.

AN IN-PLACE PROBLEM, TWO SPELLINGS
from typing import List


class Solution:
    # LeetCode's template prints List[int], the pre-3.9 spelling of list[int]
    def sortColors(self, nums: List[int]) -> None:
        """Do not return anything, modify nums in-place instead."""
        nums.sort()                # writes into the judge's list
        # nums[:] = sorted(nums)   # also writes into it
        # nums = sorted(nums)      # only moves your name: the judge sees no change


def sort_colors(nums: list[int]) -> None:   # the same signature, spelled for 3.9+
    nums[:] = sorted(nums)


judge_list = [2, 0, 1]
Solution().sortColors(judge_list)
assert judge_list == [0, 1, 2]
THE HINTS A SOLUTION USES
from collections import Counter, defaultdict, deque

nums: list[int] = [3, 1, 4]
grid: list[list[int]] = [[1, 0], [0, 1]]
count: dict[str, int] = {}             # empty: annotate it, nothing else says what goes in
seen: set[tuple[int, int]] = set()     # visited grid cells (row, col)
task: tuple[int, str] = (2, "test")    # fixed length, mixed types
best: int | None = None                # Optional[int] in LeetCode's templates
graph: defaultdict[int, list[int]] = defaultdict(list)
queue: deque[int] = deque()
letters: Counter[str] = Counter("banana")
heap: list[tuple[int, str]] = []


def two_sum(nums: list[int], target: int) -> list[int]:
    return []


def rotate(nums: list[int], k: int) -> None:   # in place: returns None
    nums[:] = nums[-k:] + nums[:-k]
STEP 03 / 04

A HELPER INSIDE THE METHOD SEES ITS VARIABLES

Fig 1.3Follow 1 to 3 outward from the helper. The accent hop is the method’s own variables, where nonlocal points.

A def inside the method is a : it reads the method’s variables, such as grid and rows, without taking them as arguments. Assigning to an outer name makes it local to the helper instead, so best += 1 raises UnboundLocalError: cannot access local variable 'best' where it is not associated with a value. Declare best first.

Mutating an outer object, such as seen.add(x) or grid[r][c] = 0, needs no declaration. A recursive helper stops at the , 1,000 frames by default; the deepest plain call here reached 997. sys.setrecursionlimit(10**5) raises it.

A HELPER THAT READS, MUTATES AND REASSIGNS
import sys

sys.setrecursionlimit(10**5)   # the default limit is 1,000 frames
DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]   # a module-level name


class Solution:
    def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        best = 0

        def dfs(r: int, c: int) -> int:           # reads grid, rows, cols, DIRS
            if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == 0:
                return 0
            grid[r][c] = 0                        # mutating needs no declaration
            return 1 + sum(dfs(r + dr, c + dc) for dr, dc in DIRS)

        def visit(r: int, c: int) -> None:
            nonlocal best                         # reassigning does
            best = max(best, dfs(r, c))

        for r in range(rows):
            for c in range(cols):
                visit(r, c)
        return best


assert Solution().maxAreaOfIsland([[1, 1, 0, 0], [0, 1, 0, 1], [0, 0, 1, 1]]) == 3
STEP 04 / 04

RUN IT LOCALLY WITH ASSERTS

Fig 1.4Follow 1 to 4: list notation becomes nodes, the method runs, and the accent hop compares the result.

LeetCode’s template carries ListNode and TreeNode as a comment; uncomment them locally. Two helpers turn LeetCode’s list notation into objects and back, build_list([1, 2, 3]) and to_list(head), and build_tree([1, None, 2, 3]) reads level order, where None marks a missing child.

Put the checks under if __name__ == "__main__": so the file still pastes into LeetCode unchanged. LeetCode imports most of the standard library for you; write the imports anyway, so the same file runs on your machine.

LISTNODE, AND LIST NOTATION BOTH WAYS
class ListNode:
    def __init__(self, val: int = 0, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next


def build_list(vals: list[int]) -> ListNode | None:
    head: ListNode | None = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head


def to_list(head: ListNode | None) -> list[int]:
    out: list[int] = []
    while head:
        out.append(head.val)
        head = head.next
    return out


if __name__ == "__main__":     # runs locally; ignored when pasted into LeetCode
    assert to_list(build_list([1, 2, 3])) == [1, 2, 3]
TREENODE FROM LEVEL ORDER
class TreeNode:
    def __init__(self, val: int = 0, left: TreeNode | None = None,
                 right: TreeNode | None = None) -> None:
        self.val, self.left, self.right = val, left, right


def build_tree(vals: list[int | None]) -> TreeNode | None:
    """Level order, as LeetCode prints it: None marks a missing child."""
    if not vals or vals[0] is None:
        return None
    root = TreeNode(vals[0])
    level, i = [root], 1
    for node in level:                      # level grows while the loop reads it
        left = vals[i] if i < len(vals) else None
        right = vals[i + 1] if i + 1 < len(vals) else None
        if left is not None:
            node.left = TreeNode(left)
            level.append(node.left)
        if right is not None:
            node.right = TreeNode(right)
            level.append(node.right)
        i += 2
    return root


root = build_tree([1, None, 2, 3])          # 1 has only a right child, 2; 2 has a left child, 3
assert root and root.right and root.right.left and root.right.left.val == 3

COMMON QUESTIONS

Does the judge check my type hints?
No. Hints are notes for readers and tools; passing a tuple where the hint says list[int] runs fine. Run mypy --strict locally: it caught 4 of this tutorial’s 12 watch-out bugs before the code ran.
Can I keep state on self between calls?
You can, but the judge may reuse one Solution object for several tests, so reset it at the top of the method. A nested helper avoids the question.
Why does my recursive solution fail near depth 1,000?
Python’s default recursion limit is 1,000 frames. Raise it with sys.setrecursionlimit, or rewrite the recursion as a loop with your own stack.

WHAT YOU NOW KNOW

  • The judge calls one method of Solution per test and compares its return value; prints don’t count.
  • nums[:] = … or nums.sort() changes the judge’s list; nums = … only moves your name.
  • Nested helpers read the method’s variables; reassigning one needs nonlocal, and recursion stops near 1,000 frames.
deep dive: List versus list, annotations in 3.14, what a type checker catches, self versus closures, and the recursion limit

List versus list. PEP 585 (3.9) made list[int] work; typing.List is a deprecated alias kept for old code. X | None (PEP 604, 3.10) is the newer spelling of Optional[X]. The collections classes take parameters too: defaultdict[int, list[int]], deque[int], Counter[str].

Annotations in 3.14. PEP 649 and PEP 749 evaluate annotations only when something asks for them, so next: ListNode | None inside class ListNode no longer needs quotes or from __future__ import annotations.

What a type checker catches. mypy 2.4.1 with --strict, run on this tutorial’s 12 watch-out bugs, reported 4: item assignment on a str, a list as a dict key, nums = nums.sort(), and a list passed to a cached function. It accepted the rest, including a missing nonlocal, a heap tie on dict payloads and max([]). Hints help; they don’t replace the harness.

self.best versus a closure. An attribute works without nonlocal and survives between calls, which is why it needs a reset. A closure’s variables are fresh on every call.

Why the recursion limit exists. It protects the C stack under the interpreter. Very deep recursion with a raised limit can still crash the process, so 10**5 is a ceiling, not a target; an explicit stack is the general fix, and the DSA tutorials show it.

Loops without index bugs: range, enumerate, zip and comprehensions

Inside the method, most lines loop over the input. Python’s loop tools hand you items, indexes and pairs directly, so you rarely keep a counter by hand, and a handful of built-ins replace a whole loop with one call. Off-by-one bugs live in the gaps between these tools: where a range stops, where zip stops, what a generator has left. How do you loop by index, in pairs or backwards without off-by-one bugs?

STEP 01 / 05

THE MAP SO FAR

Fig 2.1The accent parts are new: the loop tools band, and the tuple at the top of the by-position column.

The method gains a band of loop tools: range, enumerate and zip, comprehensions, and the built-ins that reduce many values to one. None of them copies the input; each hands out one item at a time.

The first member of the by-position family arrives with them. The tuple is what enumerate and zip hand you on each turn of the loop, and what you unpack into names.

STEP 02 / 05

RANGE STOPS ONE BEFORE ITS END

Fig 2.2One ruler of indexes 0 to 9. The accent ticks are range(2, 9, 3); the stop value 9 is never reached.

range(start, stop, step) is a : it includes start and stops before stop, so range(2, 9, 3) gives 2, 5 and 8. To walk backwards, write range(n - 1, -1, -1), or the easier-to-read reversed(range(n)).

A range builds no list: len(range(10**9)) answers at once, and x in range(…) is arithmetic. for i in range(len(nums)) is the right loop only when you need the index to write back into nums.

RANGE, FORWARDS AND BACKWARDS
nums = [3, 1, 4, 1, 5, 9, 2, 6]
n = len(nums)

list(range(2, 9, 3))          # [2, 5, 8]: starts at 2, stops before 9
list(range(n - 1, -1, -1))    # [7, 6, 5, 4, 3, 2, 1, 0]: every index, backwards
list(reversed(range(n)))      # the same, easier to read
list(range(5, 0, -1))         # [5, 4, 3, 2, 1]: never reaches 0
len(range(10**9))             # 1000000000, computed without building a list
7 in range(0, 10, 2)          # False, by arithmetic

for i in range(n):            # use the index when you write back
    nums[i] *= 2
STEP 03 / 05

ENUMERATE AND ZIP HAND YOU TUPLES

Fig 2.3zip pairs items left to right. The red item has no partner and is dropped without an error.

enumerate(nums) yields (index, item) pairs, and start=1 shifts the index. zip(a, b) yields items side by side and stops at the shorter input. Since 3.10, strict=True turns the mismatch into ValueError: zip() argument 2 is shorter than argument 1.

Each pair is a , and it unpacks in the loop header: for i, x in enumerate(nums). The same unpacking swaps two names, a, b = b, a, and splits a list, first, *rest = nums. zip(nums, nums[1:]) gives neighbours, and zip(*grid) turns rows into columns.

ENUMERATE, ZIP AND UNPACKING
nums = [3, 1, 4, 1, 5, 9, 2, 6]
grid = [[1, 1, 0, 0], [0, 1, 0, 1], [0, 0, 1, 1]]

for i, x in enumerate(nums, start=1):   # (1, 3), (2, 1), (3, 4), ...
    pass
list(zip([1, 2, 3], "ab"))              # [(1, 'a'), (2, 'b')]: the 3 is dropped
# zip([1, 2, 3], "ab", strict=True)     # raises ValueError instead (3.10+)
for a, b in zip(nums, nums[1:]):        # neighbours: (3, 1), (1, 4), (4, 1), ...
    pass

first, *rest = nums                     # 3 and [1, 4, 1, 5, 9, 2, 6]
lo, hi = 0, len(nums) - 1
lo, hi = hi, lo                         # swap, no temporary variable
cols = [list(col) for col in zip(*grid)]   # rows become columns
assert cols[0] == [1, 0, 0]
STEP 04 / 05

A COMPREHENSION BUILDS A CONTAINER IN ONE EXPRESSION

Fig 2.4Four brackets, four results. The accent column is the generator, the only one that can be read just once.

A takes its container from its brackets: [x * x for x in nums] builds a list, {x: i for i, x in enumerate(nums)} a dict, where a later duplicate overwrites an earlier one, and {x % 3 for x in nums} a set.

Parentheses build a , which computes items on demand: sum(x * x for x in nums) needs no extra brackets. Filter with a trailing if; choose a value with a if cond else b before the for. Several for clauses read in the order of nested loops.

FOUR BRACKETS, FOUR CONTAINERS
nums = [3, 1, 4, 1, 5, 9, 2, 6]

squares = [x * x for x in nums]                 # list
index_of = {x: i for i, x in enumerate(nums)}   # dict: the later 1 wins
remainders = {x % 3 for x in nums}              # set: {0, 1, 2}
evens = [x for x in nums if x % 2 == 0]         # filter: [4, 2, 6]
parity = ["even" if x % 2 == 0 else "odd" for x in nums]   # choose a value
cells = [(r, c) for r in range(3) for c in range(4)]       # outer loop first

gen = (x * x for x in nums)                     # lazy: nothing computed yet
assert sum(gen) == 173
assert sum(gen) == 0                            # already used up
assert index_of[1] == 3
STEP 05 / 05

BUILT-INS THAT REPLACE A LOOP

Fig 2.5What each built-in returns for an empty input. The red row is min and max, which raise instead.

sum, min, max, any, all and len take any iterable. min and max take key=, as in max(words, key=len), and default=; any and all stop at the first item that settles the answer.

On an empty input, sum gives 0, any gives False and all gives True, while min and max raise ValueError: max() iterable argument is empty. A running minimum starts at math.inf or float("inf"), which is larger than every number.

ONE CALL INSTEAD OF A LOOP
import math

nums = [3, 1, 4, 1, 5, 9, 2, 6]
words = ["eat", "tea", "tan", "ate", "nat", "bat"]

assert sum(nums) == 31 and min(nums) == 1 and max(nums) == 9
assert max(words, key=len) == "eat"                      # the first of the longest
assert max((x for x in nums if x < 0), default=0) == 0   # no match: the default
assert any(x > 8 for x in nums)                          # stops at the 9
assert all(x > 0 for x in nums)

empty: list[int] = []
assert sum(empty) == 0 and not any(empty) and all(empty)  # all() of nothing is True

lowest = math.inf                 # a running minimum starts above everything
for x in nums:
    lowest = min(lowest, x)
assert lowest == 1

COMMON QUESTIONS

Is for i in range(len(nums)) wrong?
No, but use it only when you need the index, usually to write back. enumerate gives the index and the item together.
Is a list comprehension faster than a loop with append?
Usually a little. Choose it for clarity; the difference rarely decides a LeetCode time limit.
Why do I get tuples from zip(*grid)?
zip always yields tuples. Write [list(col) for col in zip(*grid)] when you need lists.

WHAT YOU NOW KNOW

  • range(a, b) holds b - a items and never reaches b; count down with range(n - 1, -1, -1).
  • enumerate and zip hand you tuples to unpack; zip stops at the shorter input unless strict=True.
  • Brackets choose a comprehension’s container, generators are single-pass, and min and max need default= on empty input.
deep dive: range as a sequence, iterators, the walrus operator, for and else, and chained comparisons

range is a sequence. Indexing, slicing (range(10)[::2]), len and in all work without building a list, so range(10**18) costs a few bytes.

Iterators. enumerate, zip, map, filter and generators are one-pass iterators. iter() and next() read them by hand: next(iter(s)) reads one item of a set, and next(it, None) returns None instead of raising at the end.

The walrus operator. := (3.8) assigns inside an expression, which lets a while test or a comprehension filter reuse a value it just computed.

for and else. A loop’s else block runs when the loop ends without break, which replaces a found flag.

Chained comparisons. 0 <= r < rows is one comparison chain: it reads like the maths and evaluates r once.

The list: an array that grows at the end

Most inputs arrive as a list: nums, a grid, a list of intervals. A Python list is an array of references to objects, with spare room at the end so that adding an item is usually a single write. That design makes some operations take one step whatever the length, and others move or copy every item. Which list operations take one step, and which scan or copy the whole list?

STEP 01 / 04

THE MAP SO FAR

Fig 3.1The accent box is new: the list, in the by-position column under the tuple.

The list joins the by-position column. It is a : one block of slots in order, each holding a reference to an object, so reading or writing a[i] is one step for any i.

Costs in this tutorial use : O(1) is about one step whatever the length, O(n) is a step per item. The list’s design makes some operations O(1) and others O(n), and the difference is where in the list they work.

STEP 02 / 04

THE END OF A LIST IS CHEAP AND THE FRONT IS NOT

Fig 3.2Five items in eight slots. The accent arrows are the moves insert(0, x) makes; append fills slot 5.

A list keeps spare slots at its end. As a list grew one append at a time, its capacity jumped to 4, 8, 16, 24, 32, 40, 52, 64, 76 slots, so append is O(1): a spare slot is almost always there. pop() takes the last item in one step too.

insert(0, x) and pop(0) move every other reference one slot, so they are O(n). Draining 100,000 items took 0.823 s with pop(0) and 0.0026 s with pop(). A list is a ready-made stack: append to push, pop() to pop, stack[-1] to peek.

EVERY LIST OPERATION, WITH ITS COST
a = [3, 1, 4, 1, 5]

a[2]              # 4          O(1)  any index
a.append(9)       # [..., 9]   O(1)  amortized: a spare slot is usually there
a.pop()           # 9          O(1)  from the end
a.pop(0)          # 3          O(n)  every other item shifts left
a.insert(0, 3)    #            O(n)  the same shift, the other way
a.remove(1)       # first 1    O(n)  scans, then shifts
a.index(5)        # 3          O(n)  scans; ValueError when absent
5 in a            # True       O(n)  scans
a.count(4)        # 1          O(n)
a.extend([2, 6])  #            O(k)  k = items added
a.sort()          #            O(n log n), in place, returns None
a.reverse()       #            O(n), in place
b = a.copy()      #            O(n)  a shallow copy, same as a[:]

stack: list[int] = []      # a list is a stack: push and pop at the end
stack.append(1)
stack.append(2)
top = stack[-1]            # 2: peek (test emptiness first: if stack)
STEP 03 / 04

A SLICE IS A COPY, AND NEGATIVE INDEXES COUNT FROM THE END

Fig 3.3nums with positive indexes above and negative below. The accent span is nums[1:4]: three items, 1 to 3.

a[-1] is the last item and a[-2] the one before. a[i:j] copies j - i references into a new list; a[:] and a.copy() are , a[::-1] is a reversed copy, and a.reverse() reverses in place.

A slice stops at the end of the list, so a[5:100] is fine where a[100] raises IndexError: list index out of range. Assigning to a slice replaces that range, even with a different number of items: a[1:3] = [7].

INDEXES AND SLICES ON NUMS
nums = [3, 1, 4, 1, 5, 9, 2, 6]

nums[-1], nums[-2]    # (6, 2): counted from the end
nums[1:4]             # [1, 4, 1]: indexes 1, 2, 3, so 4 - 1 items
nums[:3], nums[5:]    # ([3, 1, 4], [9, 2, 6])
nums[::-1]            # [6, 2, 9, 5, 1, 4, 1, 3]: a reversed copy
nums[::2]             # [3, 4, 5, 2]: every second item
copy = nums[:]        # a shallow copy, same as nums.copy()
nums[5:100]           # [9, 2, 6]: a slice stops at the end of the list
# nums[100]           # IndexError: list index out of range

nums[1:3] = [7]       # replace a range: [3, 7, 1, 5, 9, 2, 6]
nums.reverse()        # in place, returns None
assert copy[1] == 1   # the copy didn't change
STEP 04 / 04

A GRID IS A LIST OF SEPARATE ROWS

Fig 3.4Left, three references to one row, in red. Right, the accent: three rows, built one by one.

[[0] * 4] * 3 repeats one reference three times, so all three rows are an of one list: g[0][0] = 1 changes every row. [[0] * cols for _ in range(rows)] runs the inner expression once per row and builds separate rows.

Grid code repeats a few lines: rows, cols = len(grid), len(grid[0]), neighbours from DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)], the bounds check 0 <= r < rows and 0 <= c < cols, and a copy that copies rows too, [row[:] for row in grid].

A GRID, ITS NEIGHBOURS AND ITS BOUNDS
rows, cols = 3, 4
shared = [[0] * cols] * rows           # trap: three references to one row
shared[0][0] = 1                       # every row now starts with 1
grid = [[0] * cols for _ in range(rows)]   # three separate rows
grid[0][0] = 1                         # only row 0 changes

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def neighbours(r: int, c: int) -> list[tuple[int, int]]:
    out: list[tuple[int, int]] = []
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:   # stay on the grid
            out.append((nr, nc))
    return out


assert neighbours(0, 0) == [(1, 0), (0, 1)]
snapshot = [row[:] for row in grid]    # copy every row, not only the outer list

COMMON QUESTIONS

Is x in nums fast?
It scans from the front, so it is O(n). Fine once; inside a loop over the same list it becomes O(n²). Chapter 06’s set answers it in about one step.
What does sorted(nums) cost compared with nums.sort()?
Both are O(n log n). sorted returns a new list; .sort() sorts in place and returns None.
When do I need copy.deepcopy?
When a list holds lists and you will change the inner ones. For a grid of numbers, [row[:] for row in grid] is enough and faster.

WHAT YOU NOW KNOW

  • a[i], append and pop() take one step; insert(0, x), pop(0), x in a and remove touch every item.
  • a[i:j] copies j - i items, negative indexes count from the end, and a[::-1] is a reversed copy.
  • [[0] * cols] * rows links all rows; build a grid with a comprehension.
deep dive: the growth formula, what a list stores, and the array module

The growth formula. list_resize in CPython’s Objects/listobject.c allocates the new size plus an eighth of it plus 6, rounded down to a multiple of 4. That gives the 4, 8, 16, 24, 32, 40, 52, 64, 76 sequence measured above.

What a list stores. An empty list is 56 bytes, and each slot is an 8-byte reference on a 64-bit build. The ints themselves are separate objects of 28 bytes for small values, and CPython shares one object for each of −5 to 256.

array and bytearray. The array module stores numbers of one machine type without separate objects, which saves memory. It rarely matters on LeetCode, where inputs fit in a list.

Strings: text you cannot change

Strings arrive as s, as words, or as a sentence to split. A Python str is a sequence of characters you can read at any position in one step and never change: there is no separate character type, and every method that seems to edit returns a new string. The patterns in this chapter are the ways around that. How do you change, count and split text you cannot edit in place?

STEP 01 / 04

THE MAP SO FAR

Fig 4.1The accent box is new: str, under list in the by-position column.

str joins the by-position column. A string is : you can read any position in one step and never change one. s[i] is itself a string of length 1, because Python has no separate character type, and len(s) is stored, not counted.

STEP 02 / 04

TO CHANGE A STRING, BUILD A LIST AND JOIN

Fig 4.2The red hop is item assignment, refused. Follow the accent path: list, edit, join.

s[0] = 'b' raises TypeError: 'str' object does not support item assignment, and mypy reports the line before it runs. Convert instead: chars = list(s), change the list, then ''.join(chars). To build output, collect pieces in a list and join once at the end, which takes one pass.

+= in a loop copies the whole string so far each time. CPython often avoids the copy, and PEP 8 says not to rely on it. s[::-1] reverses a string, so s == s[::-1] tests a palindrome.

CHANGE BY BUILDING A NEW STRING
s = "cat"
chars = list(s)                  # ['c', 'a', 't']: a list you can change
chars[0] = "b"
s = "".join(chars)               # 'bat': a new string

parts: list[str] = []
for word in ["eat", "tea", "tan"]:
    parts.append(word.upper())   # collect pieces, join once at the end
line = " ".join(parts)           # 'EAT TEA TAN'

shout = s.upper()                # every method returns a new string: keep it
assert "racecar" == "racecar"[::-1]   # a palindrome reads the same reversed
assert (s, line, shout) == ("bat", "EAT TEA TAN", "BAT")
STEP 03 / 04

A CHARACTER IS A NUMBER: ORD AND CHR

Fig 4.3Letters a to z on one ruler with their codes. The accent tick is e: code 101, slot 4.

Each character is a Unicode : ord('a') is 97, ord('z') is 122, ord('A') is 65 and ord('0') is 48. chr goes the other way: chr(97 + 4) is 'e'.

ord(c) - ord('a') maps the lowercase letters to 0 to 25, the index into a 26-slot count list, count = [0] * 26. For tests, use c.isdigit(), c.isalpha(), c.isalnum() and c.islower(); string.ascii_lowercase holds a to z.

COUNTING LETTERS IN 26 SLOTS
import string

count = [0] * 26
for ch in "banana":
    count[ord(ch) - ord("a")] += 1     # 'a' -> 0, 'b' -> 1, ..., 'z' -> 25
assert count[:3] == [3, 1, 0]          # a: 3, b: 1, c: 0

assert chr(ord("a") + 4) == "e"
assert ord("A") == 65 and ord("0") == 48
assert int("7") == ord("7") - ord("0")
key = tuple(count)                     # hashable, so usable as a dict key
assert string.ascii_lowercase[:5] == "abcde"
assert "7".isdigit() and "x".isalpha() and "x7".isalnum() and "x".islower()
STEP 04 / 04

SPLIT, STRIP, JOIN AND FIND

Fig 4.4Each row is one call on the same sentence. The accent row is split() with no argument; the red one is split(" ").

split() with no argument splits on any run of whitespace and drops the empty pieces at the ends. split(' ') splits on every single space and keeps the empty pieces. strip, lstrip and rstrip trim; ', '.join(words) glues a list back together.

s.find('z') returns -1 when nothing matches, while s.index('z') raises ValueError: substring not found. For numbers, int('101', 2) parses base 2 and bin(5)[2:] prints it.

THE STRING METHODS YOU USE MOST
s = "  a  b "

s.split()                    # ['a', 'b']: any whitespace, empty pieces dropped
s.split(" ")                 # ['', '', 'a', '', 'b', '']: every single space
s.strip()                    # 'a  b'; lstrip() and rstrip() trim one side
", ".join(["a", "b"])        # 'a, b'
"banana".find("z")           # -1 when absent, and -1 is a valid index
# "banana".index("z")        # ValueError: substring not found
"banana".count("an")         # 2
"banana".startswith("ban")   # True
"banana".replace("a", "o")   # 'bonono', a new string
"Hello".lower()              # 'hello'
int("101", 2)                # 5: parse base 2
bin(5)[2:]                   # '101'
f"{5:b}", f"{7:03d}"         # ('101', '007')

COMMON QUESTIONS

Is s[i] O(1)?
Yes. CPython stores a string at 1, 2 or 4 bytes per character, one width for the whole string, so it can jump to any index.
How do I compare two strings ignoring case?
a.lower() == b.lower(), or a.casefold() == b.casefold() for text beyond English.
Does in work on strings?
Yes, as a substring test: "nan" in "banana" is True. It scans the string.

WHAT YOU NOW KNOW

  • Strings never change: build a list of parts and join it, and assign the result of every method.
  • ord(c) - ord("a") maps a to z onto 0 to 25, the index into a 26-slot count list.
  • split() drops empty pieces where split(" ") keeps them, and find returns -1 where index raises.
deep dive: how CPython stores a string, the += shortcut, f-string formats and the int-to-str digit limit

How CPython stores a string. PEP 393 stores each string at 1, 2 or 4 bytes per character, chosen by its widest character. An empty str is 41 bytes.

The += shortcut. CPython extends a string in place when no other reference holds it. A second reference, or another interpreter such as PyPy, makes each += a full copy, which is why PEP 8 recommends join.

f-string formats. f"{x:>5}" pads to 5 on the left, f"{x:05d}" pads with zeros, f"{x:.2f}" keeps two decimals, f"{n:b}" prints binary and f"{n:,}" adds thousands separators.

More methods. str.translate maps characters in one pass, and removeprefix and removesuffix (3.9) drop a fixed prefix or suffix.

The 4,300-digit limit. Since 3.11, converting an int of more than 4,300 decimal digits to or from str raises ValueError. sys.set_int_max_str_digits(0) lifts the limit.

The dict: a value for every key

Many problems come down to one question asked over and over: have I seen this value before, and where? Scanning a list answers it with a pass over every item. A dict answers it in about one step, because it turns the key into a position in a table. That speed has two conditions, and breaking either raises an error: the key must be hashable, and it must be there. How does a dict find a key in one step, and what if it’s missing?

STEP 01 / 04

THE MAP SO FAR

Fig 5.1The accent box is new: dict, the first member of the by-key column.

The by-key column opens with the dict, a that maps keys to values. Reading d[k], writing it, testing k in d and deleting with del d[k] each take about one step, however many keys the dict holds.

STEP 02 / 04

A KEY’S HASH PICKS WHERE IT LIVES

Fig 5.2Follow 1 to 4 from the key "eat" to its value. The accent hop is the slot its hash picks.

hash(key) turns the key into an integer, the key’s . Its low bits choose a slot in a table, the slot points at an entry holding the hash, the key and the value, and the stored key is compared to confirm the match.

So a key must be , which for built-in types means immutable: str, int, a tuple of hashable values, frozenset. d[[1, 2]] = 0 raises TypeError: cannot use 'list' as a dict key (unhashable type: 'list'). For anagram groups, tuple(sorted(word)) or a tuple of 26 counts makes a good key.

KEYS THAT HASH, AND GROUPING KEYS
cost: dict[tuple[int, ...], int] = {}
cost[(0, 1)] = 5                 # a tuple of ints is hashable
cost[0, 2] = 7                   # the parentheses are optional
path = [0, 1, 3]
cost[tuple(path)] = 9            # a list is not hashable: convert it first

groups: dict[tuple[str, ...], list[str]] = {}
for w in ["eat", "tea", "tan", "ate", "nat", "bat"]:
    key = tuple(sorted(w))       # ('a', 'e', 't') for eat, tea and ate
    groups.setdefault(key, []).append(w)
assert list(groups.values()) == [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]
STEP 03 / 04

A MISSING KEY: KEYERROR, GET OR SETDEFAULT

Fig 5.3Five ways to read a key that isn’t there. The accent row returns a default; the red row raises.

d[k] on a missing key raises KeyError: 'z'. d.get(k) returns None and d.get(k, 0) returns 0, and neither inserts anything. d.setdefault(k, []) inserts the empty list and returns it, ready to append to. k in d tests keys only, never values.

Counting is one line: d[x] = d.get(x, 0) + 1. Many problems need the value-to-index pattern: store seen[x] = i as you loop, and look up the index you need in one step instead of scanning back.

READING KEYS THAT MAY BE MISSING
d: dict[str, int] = {"a": 1}
# d["z"]                     # KeyError: 'z'
assert d.get("z") is None    # no default: None
assert d.get("z", 0) == 0    # neither call inserts "z"
assert "z" not in d          # in checks keys

counts: dict[str, int] = {}
for ch in "banana":
    counts[ch] = counts.get(ch, 0) + 1   # {'b': 1, 'a': 3, 'n': 2}

groups: dict[int, list[str]] = {}
groups.setdefault(3, []).append("eat")   # inserts [] the first time

nums, target = [3, 1, 4, 1, 5], 9
seen: dict[int, int] = {}                # value -> the index it appeared at
for i, x in enumerate(nums):
    if target - x in seen:
        print(seen[target - x], i)       # 2 4: nums[2] + nums[4] == 9
    seen[x] = i
STEP 04 / 04

A DICT KEEPS INSERTION ORDER

Fig 5.4Entries in the order they were added. The red row is a delete inside the loop over them.

Since 3.7, for k in d, d.items() and d.values() follow insertion order, guaranteed. Updating a value keeps its place; deleting a key and adding it again moves it to the end.

Changing the dict’s size inside that loop raises RuntimeError: dictionary changed size during iteration. Loop over list(d) instead, or build a new dict with a comprehension. max(d, key=lambda k: d[k]) finds the key with the largest value, d1 | d2 (3.9) merges, and chapter 08 sorts items by value.

LOOPING OVER A DICT SAFELY
d = {"eat": 3, "tea": 1, "tan": 2}
assert list(d) == ["eat", "tea", "tan"]      # insertion order (3.7+)
d["tea"] = 5                                 # an update keeps its place
for word, n in d.items():                    # (key, value) pairs, in order
    pass

best = max(d, key=lambda w: d[w])            # 'tea': the key with the largest value
for word in list(d):                         # loop over a copy of the keys
    if d[word] < 3:
        del d[word]                          # safe: d itself isn't being iterated

kept = {w: n for w, n in d.items() if n >= 3}   # or build a new dict
merged = d | {"bat": 1}                      # 3.9+: a new, merged dict
inverted = {n: w for w, n in merged.items()}
assert inverted == {3: "eat", 5: "tea", 1: "bat"}
EVERY DICT OPERATION, WITH ITS COST
d: dict[str, int] = {"a": 1, "b": 2}

d["c"] = 3              #       O(1)  insert or update
d["a"]                  # 1     O(1)  KeyError when missing
d.get("z", 0)           # 0     O(1)  never inserts
"a" in d                # True  O(1)  keys only
del d["c"]              #       O(1)  KeyError when missing
d.pop("b")              # 2     O(1)  remove and return
d.pop("z", None)        # None  O(1)  no error with a default
d.setdefault("x", 0)    # 0     O(1)  inserts when missing
len(d)                  # 2     O(1)
list(d.items())         # [('a', 1), ('x', 0)]   O(n)
d.copy()                #       O(n)  shallow
d.update({"y": 1})      #       O(k)  k = items merged
d.keys() & {"a", "q"}   # {'a'}       keys behave like a set

COMMON QUESTIONS

Is a dict lookup always O(1)?
On average. Many keys with colliding hashes would degrade it toward O(n); built-in str and int keys don’t do that in practice.
Can a dict key be a float?
Yes, but 1, 1.0 and True are the same key, because they are equal and hash alike.
Is OrderedDict still needed?
Rarely. Its move_to_end and popitem(last=False) are the reason to use it; chapter 07’s deep dive shows them.

WHAT YOU NOW KNOW

  • The key’s hash picks a slot in about one step, so keys must be hashable: tuples yes, lists no.
  • d[k] raises KeyError on a missing key, get returns a default, and setdefault inserts one.
  • Iteration follows insertion order, and changing the dict’s size inside that loop raises RuntimeError.
deep dive: the compact layout, probing and resizing, hash randomisation, and key views

The compact layout. Since 3.6, a dict is a small table of indexes plus a dense array of entries in insertion order. The order guarantee comes from that array.

The index table stays sparse; the accent entries array is dense and in insertion order.

Probing and resizing. When a slot is taken, the next slot to try comes from a perturbation of the hash. The table grows when it is about two thirds full, which keeps probes short.

Hash randomisation. String hashes change from one run to the next (PYTHONHASHSEED), so never rely on a set’s order. hash(-1) == hash(-2), because CPython reserves -1 as an error value.

Key views. d1.keys() & d2.keys() is a set operation on two dicts’ keys, with no copy. An empty dict is 64 bytes.

The set: is it there?

Often you need only one answer about a value: is it there? A set is a dict with keys and no values, so it answers in about one step, and it adds operators that compare whole collections at once: what two inputs share, and what one has that the other lacks. Its rules for what it can hold are the dict’s rules for keys. When is a set the right container, and what can it hold?

STEP 01 / 03

THE MAP SO FAR

Fig 6.1The accent box is new: set, under dict in the by-key column.

The set joins the by-key column: a hash table of keys with no values. add, discard, remove and x in s each take about one step, and every rule from chapter 05 about hashable keys applies to what a set can hold.

STEP 02 / 03

IN ON A SET TAKES ONE STEP, IN ON A LIST SCANS

Fig 6.2Two bars on one scale. The list bar is the full width; the accent set bar is too short to see.

1,000 lookups of a value that isn’t there, among 100,000 items, took 0.697 s on a list and 19 µs on a set, about 37,000 times less. The list compares every item; the set hashes the value and looks in one slot.

The seen-set pattern follows: if x in seen: … then seen.add(x). len(set(nums)) != len(nums) tests for duplicates in one line, and a set of (r, c) tuples records visited grid cells.

SEEN, DUPLICATES AND VISITED CELLS
nums = [3, 1, 4, 1, 5, 9, 2, 6]

seen: set[int] = set()            # {} would be an empty dict
for x in nums:
    if x in seen:                 # about one step on a set; a scan on a list
        print("first repeat:", x)  # first repeat: 1
        break
    seen.add(x)

has_duplicates = len(set(nums)) != len(nums)    # True

visited: set[tuple[int, int]] = {(0, 0)}        # grid cells as (row, col)
visited.add((0, 1))
assert (0, 1) in visited and (1, 1) not in visited
STEP 03 / 03

SET OPERATORS COMPARE WHOLE COLLECTIONS

Fig 6.3Each row is one operator on A and B. The accent row is A & B, the items both share.

With a = {1, 2, 3, 4} and b = {3, 4, 5}: a & b is {3, 4}, a | b is 1 to 5, a - b is {1, 2} and a ^ b is {1, 2, 5}. a <= b tests a subset, and a.isdisjoint(b) tests for no overlap.

Members must be hashable: a set of tuples works, a set of lists or of sets fails. A frozenset is a set that can never change, so it can be a dict key or a set member. remove raises KeyError on a missing item where discard doesn’t, and dict.fromkeys(nums) removes duplicates while keeping their order.

SET OPERATORS AND FROZENSET
a, b = {1, 2, 3, 4}, {3, 4, 5}

a & b                  # {3, 4}           in both
a | b                  # {1, 2, 3, 4, 5}  in either
a - b                  # {1, 2}           in a and not in b
a ^ b                  # {1, 2, 5}        in exactly one
a <= b                 # False            is a a subset of b?
a.isdisjoint(b)        # False            they share 3 and 4
a.discard(9)           # no error when absent; a.remove(9) raises KeyError

weights = {frozenset((1, 2)): 0.5}   # a frozenset can be a key; a set can't
assert frozenset((2, 1)) in weights  # order doesn't matter
unique_in_order = list(dict.fromkeys([3, 1, 3, 2, 1]))   # [3, 1, 2]

COMMON QUESTIONS

How do I take one item from a set?
s.pop() removes an arbitrary one; next(iter(s)) reads one without removing it.
How do I get a set in order?
sorted(s) returns a sorted list. A set has no index.
Is set(nums) O(n)?
Yes: one pass, with one hash per item.
What goes wrong with a set inside a set?
It raises TypeError: cannot use 'set' as a set element (unhashable type: 'set'). Use a frozenset for the inner one.

WHAT YOU NOW KNOW

  • x in set takes about one step where x in list scans: 19 µs against 0.697 s for 1,000 lookups here.
  • &, |, - and ^ compare whole sets, and <= tests a subset.
  • Members must be hashable, {} is a dict, and a set keeps no order.
deep dive: how sets differ inside, set comprehensions, and frozensets as keys

How sets differ inside. A set probes a few neighbouring slots before jumping elsewhere, which suits the membership tests sets are used for. An empty set is 216 bytes, against an empty dict’s 64.

Set comprehensions. {c.lower() for c in s if c.isalpha()} builds a set in one expression, the same way a list comprehension builds a list.

frozenset keys. frozenset((a, b)) makes an unordered pair a dict key, since the pair a, b and the pair b, a hash the same.

Counting, grouping and queues: Counter, defaultdict and deque

Three patterns come up so often that the collections module ships a class for each: counting items, grouping items under a key, and taking items from the front of a queue. The first two are dicts with one behaviour changed; the third is a sequence built for both ends. Each replaces several lines of dict or list code, and each has one behaviour that surprises people. Which collections class fits counting, grouping and queues, and what does each do differently?

STEP 01 / 05

THE MAP SO FAR

Fig 7.1The accent boxes are new: Counter and defaultdict under set, and deque under str.

Three classes, one import from collections. Counter and defaultdict join the by-key column; both are dicts with one behaviour changed. deque joins the by-position column: a sequence built for adding and removing at both ends.

STEP 02 / 05

COUNTER COUNTS IN ONE CALL

Fig 7.2Counter("banana") as a table. The accent row is the most common letter; reading c["z"] gives 0.

Counter('banana') counts every item in one call: a 3, n 2, b 1. A Counter, a dict that counts, reads 0 for a missing key and doesn’t insert it. most_common(1) returns [('a', 3)], and Counter(a) == Counter(b) tests whether two words are anagrams.

c1 + c2 adds counts, c1 - c2 subtracts and keeps only the positive ones, & takes the smaller count of each item and | the larger. c.total() (3.10) gives 6 for banana; update and subtract change counts in place.

COUNTING, COMPARING AND SUBTRACTING
from collections import Counter

c = Counter("banana")                    # Counter({'a': 3, 'n': 2, 'b': 1})
assert c["z"] == 0 and "z" not in c      # a missing key reads 0, nothing inserted
assert c.most_common(1) == [("a", 3)]
assert c.total() == 6                    # 3.10+
assert Counter("listen") == Counter("silent")            # anagrams
assert Counter("ab") - Counter("abb") == Counter()       # drops counts <= 0
assert Counter("ab") & Counter("abb") == Counter("ab")   # the smaller of each
c.update("an")                           # adds: a 4, n 3
c.subtract("bbb")                        # keeps negatives: b -2
assert c["b"] == -2
STEP 03 / 05

DEFAULTDICT BUILDS A VALUE THE FIRST TIME YOU READ A KEY

Fig 7.3Follow 1 to 3 on a key that isn’t there yet. The accent hop stores the new empty list.

A defaultdict, a dict with a factory, calls the factory when you read a missing key: defaultdict(list) calls list(), stores the empty list under the key and returns it. So g[u].append(v) works on the first edge, and four edges build a whole adjacency list.

defaultdict(int) counts, since int() is 0, and defaultdict(set) collects unique items. Grouping anagrams is one loop: groups[tuple(sorted(w))].append(w) gives eat, tea and ate in one group, tan and nat in another, and bat alone.

ADJACENCY LISTS, DEGREES AND GROUPS
from collections import defaultdict

edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
graph: defaultdict[int, list[int]] = defaultdict(list)   # list, not list()
for u, v in edges:
    graph[u].append(v)           # a missing key gets a new empty list
    graph[v].append(u)
assert graph[0] == [1, 2] and graph[3] == [1, 2]

degree: defaultdict[int, int] = defaultdict(int)   # a missing key reads 0
for u, v in edges:
    degree[u] += 1

groups: defaultdict[tuple[str, ...], list[str]] = defaultdict(list)
for w in ["eat", "tea", "tan", "ate", "nat", "bat"]:
    groups[tuple(sorted(w))].append(w)

assert 7 not in graph            # trap: "if graph[7]:" would insert key 7
STEP 04 / 05

A DEQUE ADDS AND REMOVES AT BOTH ENDS IN ONE STEP

Fig 7.4Three bars on one scale for 100,000 items. The accent popleft bar matches pop() from the end.

A stores its items in a chain of blocks of 64 slots, so append, appendleft, pop and popleft each take one step. Reading an item in the middle, d[i], walks the blocks, and a deque has no slicing.

Draining 100,000 items took 0.0026 s with popleft() and 0.823 s with list.pop(0), about 315 times longer. Filling 100,000 at the front took 0.0025 s with appendleft and 0.863 s with insert(0, x).

EVERY DEQUE OPERATION, WITH ITS COST
from collections import deque

q: deque[int] = deque([1, 2, 3])
q.append(4)          #       O(1)  right end: [1, 2, 3, 4]
q.appendleft(0)      #       O(1)  left end: [0, 1, 2, 3, 4]
q.pop()              # 4     O(1)
q.popleft()          # 0     O(1)  list.pop(0) would shift every item
q[0], q[-1]          # 1, 3  O(1)  at either end
q[1]                 # 2     O(n)  in the middle; a deque has no slicing
q.extend([4, 5])     #       O(k)
q.rotate(1)          #       O(k)  [5, 1, 2, 3, 4]

last3: deque[int] = deque(maxlen=3)
for x in range(5):
    last3.append(x)  # once full, each append drops one from the left
assert list(last3) == [2, 3, 4]
STEP 05 / 05

THE QUEUE LOOP: POP LEFT, PUSH RIGHT

Fig 7.5Items leave at the left and join at the right. Follow 1 to 3; the accent hop is popleft.

The queue loop is a skeleton later tutorials build on: q = deque([start]), then while q: take x = q.popleft() and q.append(…) each new item. Items leave in the order they arrived, and a seen set keeps any item from joining twice.

To process one level at a time, put for _ in range(len(q)): inside the while: it handles only the items queued before this pass. deque(maxlen=3) keeps the last 3 items, and rotate(k) shifts everything k places.

THE QUEUE LOOP, LEVEL BY LEVEL
from collections import deque

graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}

q: deque[int] = deque([0])
seen = {0}
levels: list[list[int]] = []
while q:
    level: list[int] = []
    for _ in range(len(q)):        # only the items queued before this pass
        x = q.popleft()            # the oldest item first
        level.append(x)
        for y in graph[x]:
            if y not in seen:
                seen.add(y)
                q.append(y)        # the newest at the back
    levels.append(level)
assert levels == [[0], [1, 2], [3]]

COMMON QUESTIONS

Counter or a 26-slot list for letter counts?
Both work. The list is a little faster and fixed to a to z; Counter handles any character and compares with ==.
Is defaultdict slower than a dict?
Barely. The factory runs only for missing keys.
Can I use queue.Queue instead of deque?
It works, but it adds locks for threads that a LeetCode solution doesn’t need. deque is faster.

WHAT YOU NOW KNOW

  • Counter counts in one call, reads 0 for missing keys, and its minus drops non-positive counts.
  • defaultdict(list) creates the group on first read, which also means a read inserts.
  • deque.popleft() is one step where list.pop(0) shifts everything: 0.0026 s against 0.823 s for 100,000 items.
deep dive: Counter arithmetic, OrderedDict for an LRU cache, how a deque stores items, and ChainMap

Counter arithmetic. Unary +c drops counts at or below zero, c.elements() repeats each item by its count, and most_common(k) with a small k uses a heap instead of a full sort.

OrderedDict for an LRU cache. move_to_end(key) marks a key as just used, and popitem(last=False) removes the oldest one, which are the two moves an LRU cache needs. Two OrderedDicts compare equal only when their order matches too.

How a deque stores items. A doubly linked list of blocks of 64 slots each, BLOCKLEN in CPython’s Modules/_collectionsmodule.c. Both ends are a block away from the deque object, which is why they cost one step.

Blocks linked both ways. The accent block is where popleft reads.

ChainMap. collections.ChainMap searches several dicts in order as if they were one, which suits nested scopes.

Order by value: sorted, keys and bisect

Some problems need the items in order: intervals by start, words by length, scores from high to low. Python sorts with one function and a key that says what to compare. Once a list is sorted, bisect finds where any value belongs in about 20 steps for a million items, where in would scan them all. How do you sort by any rule, and search the sorted result fast?

STEP 01 / 03

THE MAP SO FAR

Fig 8.1The accent boxes are new: sorted and bisect, the first two in the by-value column.

The by-value column opens with sorted and list.sort, which put every item in order by any rule you give them, and bisect, which searches the sorted result. Sorting costs O(n log n) once; every search after that costs O(log n).

STEP 02 / 03

SORTED TAKES A KEY, AND TUPLES SORT FIELD BY FIELD

Fig 8.2One input, three keys. The accent column sorts by (-score, name): score down, ties by name.

sorted(x) returns a new list; x.sort() sorts in place and returns None. A says what to compare: key=len, key=str.lower, or key=lambda iv: iv[0] to order intervals by their start.

Tuples compare field by field, so key=lambda p: (-p[1], p[0]) sorts by score down, then name up. The sort is a : equal keys keep their input order. For a rule that compares two items, such as “a + b before b + a”, wrap it with functools.cmp_to_key.

SORTING BY A KEY
intervals = [[8, 10], [1, 3], [2, 6], [15, 18]]
players = [("dee", 70), ("ana", 90), ("ben", 85), ("cy", 90)]

by_start = sorted(intervals, key=lambda iv: iv[0])   # a new list
intervals.sort()                                     # in place; returns None
assert by_start == intervals == [[1, 3], [2, 6], [8, 10], [15, 18]]

by_len = sorted(["eat", "a", "tea", "be"], key=len)  # ['a', 'be', 'eat', 'tea']
ranked = sorted(players, key=lambda p: (-p[1], p[0]))   # score down, then name
assert [name for name, _ in ranked] == ["ana", "cy", "ben", "dee"]
desc = sorted([3, 1, 2], reverse=True)               # [3, 2, 1]

counts = {"a": 3, "n": 2, "b": 1}
by_value = sorted(counts.items(), key=lambda kv: kv[1])   # [('b', 1), ('n', 2), ('a', 3)]
A TWO-ITEM RULE THROUGH CMP_TO_KEY
from functools import cmp_to_key


def largest_number(nums: list[int]) -> str:
    def compare(a: str, b: str) -> int:
        # Negative puts a first: "9" + "34" beats "34" + "9".
        if a + b > b + a:
            return -1
        return 1 if a + b < b + a else 0

    parts = sorted(map(str, nums), key=cmp_to_key(compare))
    return "".join(parts).lstrip("0") or "0"


assert largest_number([3, 30, 34, 5, 9]) == "9534330"
STEP 03 / 03

BISECT FINDS A POSITION IN LOG N STEPS

Fig 8.3sorted(nums) on one ruler. The accent span runs from bisect_left to bisect_right: every 1.

On sorted(nums), [1, 1, 2, 3, 4, 5, 6, 9]: bisect_left(a, 1) is 0, the first index holding a value of at least 1, and bisect_right(a, 1) is 2, the first index holding more than 1. Their difference counts the 1s. insort(a, x) inserts in order, and still costs O(n), because the insert shifts items.

Since 3.10, key= applies to the list’s items. 1,000 lookups in a sorted list of 1,000,000 items took 0.23 ms with bisect_left and 6.66 s with in, which scans.

POSITIONS IN A SORTED LIST
import bisect

a = [1, 1, 2, 3, 4, 5, 6, 9]                 # sorted(nums): bisect needs this
assert bisect.bisect_left(a, 1) == 0          # the first index with a[i] >= 1
assert bisect.bisect_right(a, 1) == 2         # the first index with a[i] > 1
assert bisect.bisect_right(a, 1) - bisect.bisect_left(a, 1) == 2   # copies of 1
assert bisect.bisect_left(a, 4) == 4
assert bisect.bisect_left(a, 7) == 7          # where 7 would go
bisect.insort(a, 7)                           # O(n): the insert still shifts
assert a[7] == 7

tasks = [(1, "read"), (2, "test"), (3, "ship")]
i = bisect.bisect_left(tasks, 2, key=lambda t: t[0])   # 3.10+: key applies to items
assert tasks[i][1] == "test"

COMMON QUESTIONS

What does Python’s sort cost?
O(n log n), and close to O(n) on input that is already mostly sorted.
How do I sort a dict by value?
sorted(d.items(), key=lambda kv: kv[1]) gives (key, value) pairs in order; add reverse=True for the largest first.
How do I sort one string field down and another up?
Negation works only for numbers. Sort twice, by the second field first, and let stability keep that order.
Is there a sorted map like Java’s TreeMap?
Not in the standard library. LeetCode installs sortedcontainers, whose SortedList and SortedDict keep order with about log n steps per change.
What happens if I pass a comparison function directly?
It raises TypeError: sort() takes no positional arguments.

WHAT YOU NOW KNOW

  • key= says what to compare, a tuple key breaks ties field by field, and .sort() returns None.
  • The sort is stable, and cmp_to_key turns a two-item comparison into a key.
  • bisect_left and bisect_right find positions in O(log n): 0.23 ms against 6.66 s for 1,000 lookups.
deep dive: Powersort, how often key is called, itemgetter, and keeping a list sorted

Powersort. CPython’s list sort is an adaptive merge sort that finds the runs already in order. Since 3.11 it decides which runs to merge with Munro and Wild’s Powersort rule (bpo-34561).

How often key is called. Once per item, before any comparison, so an expensive key is computed n times, never n log n times.

Faster keys. operator.itemgetter(0) and operator.attrgetter do the work of a lambda in C.

Keeping a list sorted. insort costs O(n) per insert because of the shift. LeetCode installs sortedcontainers for this case: SortedList adds, removes and finds in about log n steps. It is not in the standard library, so a plain interview pad lacks it, and it ships no type hints, so no sample here uses it.

The smallest item first: heapq

Sorting once is enough when the input is fixed. When items keep arriving and you always want the smallest one next, sorting again after each arrival costs n log n every time. The heapq module keeps a plain list arranged so that the smallest item is always at index 0, and each push or pop costs about log n steps. How does heapq keep the smallest item first, and how do you get the largest?

STEP 01 / 04

THE MAP SO FAR

Fig 9.1The accent box is new: heapq, under bisect in the by-value column.

heapq joins the by-value column. It is a set of functions, not a class: they rearrange an ordinary list you own into a , and every call takes that list as its first argument.

STEP 02 / 04

A HEAP KEEPS ONLY THE SMALLEST IN PLACE

Fig 9.2heapify(nums) drawn as a tree with list indexes. Follow the accent path a pushed 0 takes up to index 0.

Every item in a heap is no larger than its two children, at indexes 2i + 1 and 2i + 2, so heap[0] is always the smallest. heapify(nums) rearranges the list in place in O(n), giving [1, 1, 2, 3, 5, 9, 4, 6]: smallest first, the rest only partly ordered.

heappush adds at the end and swaps up; heappop moves the last item to the top and swaps down. Each costs O(log n). nsmallest(3, nums) gives [1, 1, 2] and nlargest(3, nums) gives [9, 6, 5].

HEAPIFY, PUSH AND POP
import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = list(nums)
heapq.heapify(heap)               # O(n), in place: [1, 1, 2, 3, 5, 9, 4, 6]
assert heap[0] == 1               # the smallest, always at index 0
heapq.heappush(heap, 0)           # O(log n)
assert heapq.heappop(heap) == 0   # O(log n): removes the smallest
assert heapq.heappop(heap) == 1
assert heapq.nsmallest(3, nums) == [1, 1, 2]
assert heapq.nlargest(3, nums) == [9, 6, 5]
# heap[-1] is not the largest: only heap[0] is in its final place
STEP 03 / 04

PUSH TUPLES TO ORDER BY PRIORITY

Fig 9.3Three ways to push two equal-priority items. The red row reaches the dicts; the accent row stops at the counter.

Push (priority, item): tuples compare field by field, so the lowest priority pops first. The three tasks pop as read, test, ship. On equal priorities the comparison moves on to the next field.

If that field is a dict or a node object, the push raises TypeError: '<' not supported between instances of 'dict' and 'dict'. Put a counter second, (priority, n, item), and every tie stops at the counter.

PRIORITIES AND A TIEBREAKER
import heapq

tasks: list[tuple[int, str]] = []
for priority, name in [(2, "test"), (1, "read"), (3, "ship")]:
    heapq.heappush(tasks, (priority, name))      # compared field by field
assert [heapq.heappop(tasks)[1] for _ in range(3)] == ["read", "test", "ship"]

# Payloads that can't be compared (dicts, nodes) need a tiebreaker second.
jobs: list[tuple[int, int, dict[str, str]]] = []
n = 0
for priority, job in [(1, {"id": "a"}), (1, {"id": "b"})]:
    heapq.heappush(jobs, (priority, n, job))     # equal priorities compare n
    n += 1
assert heapq.heappop(jobs)[2]["id"] == "a"
STEP 04 / 04

A MAX-HEAP: NEGATE, OR THE 3.14 FUNCTIONS

Fig 9.4Two ways to pop 9 first from nums. The accent column uses the 3.14 functions on the values as they are.

heapq is a min-heap. For the largest first, push -x and negate what you pop, which works for numbers only. Python 3.14 adds heapify_max, heappush_max, heappop_max, heappushpop_max and heapreplace_max, which work on any comparable items; LeetCode runs 3.14.

For the k largest items, keep a min-heap of size k: once it is full, heappushpop adds the new item and drops the smallest, in O(n log k) for the whole input.

LARGEST FIRST, AND THE TOP K
import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6]

neg = [-x for x in nums]          # any Python version: negate the numbers
heapq.heapify(neg)
assert -heapq.heappop(neg) == 9

big = list(nums)                  # 3.14+: real max-heap functions, any comparable items
heapq.heapify_max(big)
assert heapq.heappop_max(big) == 9
heapq.heappush_max(big, 7)

top: list[int] = []               # the 3 largest: a min-heap of size 3
for x in nums:
    if len(top) < 3:
        heapq.heappush(top, x)
    else:
        heapq.heappushpop(top, x) # push x, then drop the smallest
assert sorted(top) == [5, 6, 9]

COMMON QUESTIONS

Why is heapify O(n) and not O(n log n)?
Most items sit near the bottom of the tree and move a step or two at most, so the total work adds up to about 2n swaps.
How do I remove an item from the middle of a heap?
heapq has no such function. Mark the item removed, and skip it when it reaches the top.
Should I use queue.PriorityQueue?
It wraps heapq with thread locks, so it is slower. Use heapq directly.

WHAT YOU NOW KNOW

  • heap[0] is always the smallest; heappush and heappop cost O(log n) and heapify O(n).
  • Push (priority, counter, item) so ties never compare the items themselves.
  • Negate numbers for a max-heap, or use the _max functions from Python 3.14.
deep dive: why heapify is linear, heappushpop versus heapreplace, merge, and lazy deletion

Why heapify is linear. It sifts items down starting from the middle of the list. Half the items are leaves and never move, a quarter move at most one level, and so on.

heappushpop versus heapreplace. heappushpop pushes first, so it can return the item you just pushed. heapreplace pops first, so it can return something larger than the new item.

Merging sorted inputs. heapq.merge(a, b) merges sorted iterables lazily, one item at a time.

Lazy deletion. Keep a set of removed items; on each pop, discard tops that are in it. Each item is still pushed and popped once, so the costs stay O(log n).

The loops you don’t write: itertools, functools and integers

The last pieces replace loops you would otherwise write by hand: prefix sums, neighbouring pairs, combinations, a cache in front of a recursive helper. They live in itertools, functools and math. The int type belongs here too, because its division and size rules differ from C and Java in ways that change answers. Which library call replaces each loop, and how does Python’s int differ?

STEP 01 / 04

THE MAP SO FAR

Fig 10.1The accent band is new: itertools, functools.cache and math, under the three columns.

The library helpers band fills the bottom of the method: itertools for loops over combinations and runs, functools.cache for remembering results, and math with the int operators. Each replaces a loop of five to ten lines with one call.

STEP 02 / 04

ITERTOOLS: PREFIX SUMS, PAIRS AND COMBINATIONS

Fig 10.2nums above, its prefix sums below. The accent span shows sum(nums[2:5]) as P[5] minus P[2].

accumulate(nums, initial=0) gives the prefix sums [0, 3, 4, 8, 9, 14, 23, 25, 31], so the sum of nums[i:j] is P[j] - P[i] in one step: nums[2:5] sums to 10. accumulate(nums, max) gives a running maximum instead.

pairwise(nums) (3.10) yields neighbours; combinations('abc', 2) yields ab, ac and bc; permutations yields every order. product(range(rows), range(cols)) yields every grid cell, groupby('aaabbc') yields runs of equal neighbours, and chain.from_iterable flattens one level.

LOOPS ITERTOOLS WRITES FOR YOU
from itertools import accumulate, chain, combinations, groupby, pairwise, product

nums = [3, 1, 4, 1, 5, 9, 2, 6]
P = list(accumulate(nums, initial=0))        # [0, 3, 4, 8, 9, 14, 23, 25, 31]
assert P[5] - P[2] == sum(nums[2:5]) == 10   # any range sum in one step
assert list(accumulate(nums, max))[:4] == [3, 3, 4, 4]   # running maximum
assert list(pairwise(nums))[:2] == [(3, 1), (1, 4)]      # 3.10+
assert ["".join(c) for c in combinations("abc", 2)] == ["ab", "ac", "bc"]
cells = list(product(range(3), range(4)))    # every (row, col) of a 3-by-4 grid
assert len(cells) == 12
runs = [(k, len(list(g))) for k, g in groupby("aaabbc")]
assert runs == [("a", 3), ("b", 2), ("c", 1)]   # neighbours only: sort first
flat = list(chain.from_iterable([[1, 2], [3]]))   # [1, 2, 3]
STEP 03 / 04

FUNCTOOLS.CACHE REMEMBERS EVERY CALL

Fig 10.3Calls made by fib(30), on one scale. The accent bar is the cached version: 31 calls.

@cache (3.9, or lru_cache(maxsize=None) before it) stores each call’s result under its arguments. This is : fib(30) makes 2,692,537 calls without it and 31 with it, one per distinct argument.

Define the cached helper inside the method, so each test starts with an empty cache. Arguments must be hashable: a list raises TypeError, and mypy reports it first, so pass a tuple or an index. The recursion limit still applies to the first call of each argument.

A CACHED HELPER INSIDE THE METHOD
from functools import cache


class Solution:
    def climbStairs(self, n: int) -> int:
        @cache                        # defined per call: each test starts empty
        def ways(i: int) -> int:      # arguments must be hashable
            if i <= 1:
                return 1
            return ways(i - 1) + ways(i - 2)

        result = ways(n)
        print(ways.cache_info())      # CacheInfo(hits=28, misses=31, ...)
        return result


assert Solution().climbStairs(30) == 1346269
STEP 04 / 04

INTEGERS: FLOOR DIVISION, NO OVERFLOW, BITS

Fig 10.4Each row is one expression and its result. The accent row is -7 // 2, which rounds down to -4.

// is floor division, rounding down: 7 // 2 is 3 but -7 // 2 is -4, and -7 % 2 is 1, because the sign follows the divisor. int(-7 / 2) is -3, truncating like C, through a float. Ceiling division without floats is -(-a // b).

Ints never overflow: 2 ** 100 is exact, so a problem that says “fits in 32 bits” needs an explicit check. pow(2, 10, 1000) is 24, computed fast for huge exponents. For bits, (13).bit_count() (3.10) is 3, x & (x - 1) clears the lowest set bit, and 1 << 4 is 16.

INTEGER ARITHMETIC AND BITS
import math

7 // 2, -7 // 2           # (3, -4): floor division rounds down
-7 % 2                    # 1: the sign follows the divisor
int(-7 / 2)               # -3: truncates toward zero, like C and Java
-(-7 // 2)                # 4: ceiling division without floats
divmod(-7, 2)             # (-4, 1)
2 ** 100                  # 1267650600228229401496703205376: exact, no overflow
pow(2, 10, 1000)          # 24: (2 ** 10) % 1000, fast for huge exponents
math.gcd(12, 18), math.lcm(4, 6)    # (6, 12)
math.comb(5, 2), math.isqrt(17)     # (10, 4)
(13).bit_count()          # 3: 0b1101 has three 1 bits (3.10+)
12 & 11                   # 8: x & (x - 1) clears the lowest set bit
1 << 4, 13 >> 1           # (16, 6)
math.inf > 10 ** 100      # True, and math.inf is a float

COMMON QUESTIONS

@cache or a dict I manage myself?
@cache for a recursive helper with hashable arguments; a dict when you need to inspect or reset entries.
Does math.inf compare with ints?
Yes: math.inf > 10 ** 100 is True. It is a float, so don’t return it where an int is expected.
How do I count set bits before Python 3.10?
bin(x).count("1") gives the same answer.

WHAT YOU NOW KNOW

  • accumulate(initial=0) builds prefix sums, pairwise yields neighbours, combinations yields subsets, and groupby needs sorted input.
  • @cache on a helper inside the method cut fib(30) from 2,692,537 calls to 31.
  • -7 // 2 is -4, ints never overflow, and bit_count, & and << cover the common bit tricks.
deep dive: the rest of itertools, bounded caches, more of math, floats, and more bit tricks

The rest of itertools. count, cycle, repeat, islice, takewhile, dropwhile, zip_longest, starmap, compress and batched (3.12) cover most other loops over sequences.

Bounded caches. lru_cache(maxsize=1024) keeps only the most recent results; cache_info() reports hits and misses, and cache_clear() empties it.

More of math. prod, perm, factorial and dist; the operator module’s functions work as keys and with functools.reduce.

Floats. A float holds integers exactly up to 2**53. When exactness matters past that, use fractions.Fraction or decimal.Decimal, and remember that str() of an int over 4,300 digits raises ValueError.

More bit tricks. x & -x isolates the lowest set bit, x.bit_length() counts the bits needed, and ~x == -x - 1.

The whole picture

Here is every tool from the ten chapters on one map, numbered to match the table below.

Numbers match the table below. Dashed columns group the containers by the question they answer fast.
  1. 1LeetCode judge

    does the return value match?

    from
    LeetCode
    one step
    —
    scans
    —
    when wrong
    Wrong Answer after printing the right value: you printed instead of returning
  2. 2class Solution and its method

    what goes in, what comes out?

    from
    your file
    one step
    —
    scans
    —
    when wrong
    an in-place problem still failing: nums = … moved your name, not the list
  3. 3ListNode, TreeNode

    how do lists and trees arrive?

    from
    the template’s comment
    one step
    node.next, node.left
    scans
    walking the whole list
    when wrong
    AttributeError: 'NoneType' object has no attribute 'next': a missing None check
  4. 4nested helper

    how does a helper read the method’s state?

    from
    inside the method
    one step
    reading outer names
    scans
    —
    when wrong
    UnboundLocalError: an outer name reassigned without nonlocal
  5. 5local harness

    does it pass before I submit?

    from
    if __name__ == "__main__":
    one step
    —
    scans
    —
    when wrong
    your asserts running on LeetCode: they weren’t under the guard
  6. 6range, enumerate, zip

    which index, which pair?

    from
    built-in
    one step
    each step of the loop
    scans
    —
    when wrong
    index 0 never visited: range(n, 0, -1)
  7. 7tuple

    a fixed group of values

    from
    built-in
    one step
    t[i], unpacking, hashing
    scans
    comparing two tuples field by field
    when wrong
    ValueError: too many values to unpack (expected 2, got 3)
  8. 8comprehensions

    a container in one expression

    from
    syntax
    one step
    —
    scans
    one pass to build
    when wrong
    a second sum(gen) returning 0
  9. 9min, max, sum, any, all

    one value from many

    from
    built-in
    one step
    —
    scans
    one pass
    when wrong
    ValueError: max() iterable argument is empty
  10. 10list

    the item at a position

    from
    built-in
    one step
    a[i], append, pop(), len
    scans
    insert(0, x), pop(0), x in a, remove, slices
    when wrong
    every grid row changing at once: [[0] * n] * m
  11. 11str

    text, read by position

    from
    built-in
    one step
    s[i], len
    scans
    every method (a new string), +=, in
    when wrong
    TypeError: 'str' object does not support item assignment
  12. 12dict

    the value for a key

    from
    built-in
    one step
    d[k], get, in, del
    scans
    iterating, copy
    when wrong
    KeyError, or TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
  13. 13set

    is it there?

    from
    built-in
    one step
    add, discard, in
    scans
    &, |, -, ^
    when wrong
    {} turning out to be a dict
  14. 14Counter

    how many of each?

    from
    collections
    one step
    c[x], c[x] += 1
    scans
    most_common(), ==
    when wrong
    counts vanishing after a minus
  15. 15defaultdict

    the group for a key

    from
    collections
    one step
    g[k].append(v)
    scans
    —
    when wrong
    keys appearing after a read: if g[x]: inserted them
  16. 16deque

    the oldest or newest item

    from
    collections
    one step
    append, appendleft, pop, popleft
    scans
    d[i] in the middle
    when wrong
    a slow queue: list.pop(0) used instead
  17. 17sorted, list.sort

    everything in order

    from
    built-in
    one step
    —
    scans
    O(n log n) per sort
    when wrong
    None where a list should be: x = x.sort()
  18. 18bisect

    where does x go?

    from
    bisect
    one step
    an O(log n) search
    scans
    insort’s shift
    when wrong
    positions that make no sense: the list wasn’t sorted
  19. 19heapq

    the smallest next

    from
    heapq
    one step
    heap[0]; push and pop in O(log n)
    scans
    heapify, O(n)
    when wrong
    TypeError: '<' not supported between instances of 'dict' and 'dict'
  20. 20itertools

    the loops you don’t write

    from
    itertools
    one step
    each item yielded
    scans
    one pass
    when wrong
    groupby splitting one key into several groups: the input wasn’t sorted
  21. 21functools.cache

    each call computed once

    from
    functools
    one step
    a repeated call
    scans
    the first call per argument
    when wrong
    TypeError on a list argument, which isn’t hashable
  22. 22math and int

    exact arithmetic

    from
    built-in, math
    one step
    //, %, &, <<
    scans
    big-number arithmetic grows with the digits
    when wrong
    answers off by one on negatives: // rounds down
  23. ·sys.setrecursionlimit

    deeper recursion

    from
    sys
    one step
    —
    scans
    —
    when wrong
    RecursionError: maximum recursion depth exceeded
  24. ·frozenset

    a set that can be a key

    from
    built-in
    one step
    as for a set
    scans
    as for a set
    when wrong
    TypeError: cannot use 'set' as a set element (unhashable type: 'set')
  25. ·cmp_to_key

    sorting by a two-item rule

    from
    functools
    one step
    —
    scans
    O(n log n) comparisons
    when wrong
    TypeError: sort() takes no positional arguments
  26. ·OrderedDict

    a dict you can reorder

    from
    collections
    one step
    move_to_end, popitem(last=False)
    scans
    —
    when wrong
    equality failing on the same items in another order

A file to start every problem from: a typed method, a cached helper inside it, and a local check that LeetCode ignores. Below it, one import block that covers every tool on the map.

A SOLUTION TO START FROM
from functools import cache


class Solution:
    def maxSum(self, nums: list[int], k: int) -> int:
        n = len(nums)

        @cache
        def best(i: int, left: int) -> int:      # largest sum of at most left items from i on
            if i == n or left == 0:
                return 0
            take = nums[i] + best(i + 1, left - 1)
            return max(take, best(i + 1, left))

        return best(0, k)


if __name__ == "__main__":
    assert Solution().maxSum([3, 1, 4, 1, 5], 2) == 9
EVERY IMPORT ON THE MAP
import bisect
import heapq
import math
import sys
from collections import Counter, OrderedDict, defaultdict, deque
from functools import cache, cmp_to_key
from itertools import accumulate, combinations, groupby, pairwise, permutations, product

sys.setrecursionlimit(10**5)

THREE THINGS TO KEEP

  • Every container answers one question fast: the item at a position, the value for a key, or the smallest item by value. Choose by the question your loop asks most.
  • The slow operations hide behind short syntax: pop(0), x in list, a slice in a recursive call, += on a string.
  • Most surprises are defaults: get returns None, defaultdict inserts on read, heapq is a min-heap, // rounds down, and dicts keep insertion order.

Keep this page in the next tab: the DSA tutorials assume every block on it.