← Back to the 16 Patterns

The Python Toolkit

Every tool used on this site, explained from scratch: what it actually is, what problem it solves, and when to reach for it. Written for someone who can program but has not written much Python.

Interviewers do not test Python trivia. But they do watch you reach for list.pop(0) and quietly note that your O(n) algorithm just became O(n²). This page is the small set of facts that stops that happening, starting from the beginning.

Syntax you will see on these pages

Ten pieces of Python notation account for almost everything in the sixteen pattern pages. If any of these look unfamiliar, read this section first.

Blocks are indentation, not braces

def example(flag: bool) -> int:
    if flag:
        inner = 1        # indented, so it belongs to the if
        return inner
    return 0             # dedented, so it belongs to the function

There are no braces and no semicolons. A colon opens a block, and indentation, conventionally four spaces, defines it.

Type hints, which Python ignores

def total(values: list[int], factor: int = 2) -> int:
    """The docstring. Triple quotes, and it is the first thing in the body."""
    return sum(values) * factor        # O(n): sum walks the whole list

factor: int = 2 is a parameter with a default. Calling total([1, 2]) uses 2.

None, and truthiness

value = None                 # the "nothing here" object, like null or nullptr

if value is None:            # O(1). Use `is` for None, never ==
    pass

# Empty things are falsy. All of these are False in an if:
#   None, 0, 0.0, "", [], {}, set()
items: list[int] = []
if not items:                # O(1). Emptiness is a stored length, not a scan.
    pass

Slicing

data = [10, 20, 30, 40, 50]

data[1:3]      # O(2)  [20, 30]      index 1 up to but NOT including 3
data[:2]       # O(2)  [10, 20]      from the start
data[2:]       # O(3)  [30, 40, 50]  to the end
data[-1]       # O(1)  50            a single index, not a slice
data[::-1]     # O(n)  a reversed COPY

# In general a[i:j] costs O(j - i), because it builds a whole new list.

Comprehensions

squares = [x * x for x in range(5)]              # O(n)  [0, 1, 4, 9, 16]
evens = [x for x in range(10) if x % 2 == 0]     # O(n)  with a filter
lookup = {x: x * x for x in range(3)}            # O(n)  a dict {0: 0, 1: 1, 2: 4}
unique = {ch for ch in "hello"}                  # O(n)  a set {'h','e','l','o'}
grid = [[0] * 3 for _ in range(2)]               # O(rows * cols)  2 rows of 3

Read it right to left: for each x in this range, if the filter passes, produce this value. It is a for loop that builds a collection, written on one line.

Multiple assignment and unpacking

a, b = 1, 2
a, b = b, a                  # O(1)  swap; the right side is evaluated first

first, *rest = [1, 2, 3]     # O(n)  rest is a NEW list [2, 3]
for index, value in enumerate("abc"):    # O(n) total, O(1) per step
    pass
for x, y in zip([1, 2], "xy"):           # O(n) total; stops at the shorter one
    pass

_ is the conventional name for a value you do not care about, as in for _ in range(k).

f-strings

name, count = "queue", 3
message = f"{name} has {count} items"        # O(len) "queue has 3 items"
debug = f"{count=}"                          # O(len) "count=3", handy when tracing

Nested functions and nonlocal

Every DFS and backtracking solution on this site defines a helper inside the main function. Two rules govern what that helper can touch.

def collect(items: list[int]) -> list[int]:
    """Reading and MUTATING an outer variable needs nothing special."""
    out: list[int] = []

    def helper(value: int) -> None:
        out.append(value)       # O(1). Mutating the list the name points at.

    for item in items:
        helper(item)

    return out


def add_up(items: list[int]) -> int:
    """REASSIGNING an outer variable needs the nonlocal keyword."""
    total = 0

    def helper(value: int) -> None:
        nonlocal total          # without this, `total = ...` below would create
        total = total + value   # a brand new local variable and the outer one
                                # would never change
    for item in items:
        helper(item)

    return total

Classes, in the amount you need

from dataclasses import dataclass


@dataclass
class TreeNode:
    """@dataclass writes __init__, __repr__ and __eq__ for you."""

    val: int = 0
    left: "TreeNode | None" = None      # quotes: the class is not defined yet
    right: "TreeNode | None" = None


class Counterish:
    """The long form, when you need control over the constructor."""

    def __init__(self, start: int = 0) -> None:
        self.value = start              # O(1). `self` is the instance, like `this`

    def bump(self) -> None:
        self.value += 1                 # O(1). Every method takes self explicitly

self is Python’s this, and unlike most languages it is written out as the first parameter of every method. __init__ is the constructor.

The five built-in types

Everything else is built on these. Get them right and the libraries make sense.

list

If you know Java, this is ArrayList. C++: std::vector. JavaScript: Array. Go: a slice.

items = [3, 1, 2]

items.append(4)          # O(1) amortised   -> [3, 1, 2, 4]
items[0]                 # O(1)             3
items.pop()              # O(1)             removes from the END -> [3, 1, 2]
len(items)               # O(1)             3, the length is stored not counted
2 in items               # O(n)             a linear scan; use a set if this is hot
min(items)               # O(n)             so never call it inside a loop
items.sort()             # O(n log n)       IN PLACE, returns None -> [1, 2, 3]
ordered = sorted(items)  # O(n log n)       returns a NEW sorted list

# The two slow ones, and the whole reason deque exists:
items.insert(0, 0)       # O(n)  shifts every element right
items.pop(0)             # O(n)  shifts every element left

dict

If you know Java, this is HashMap. C++: std::unordered_map. JavaScript: Map.

ages = {"ann": 30, "bob": 25}

ages["ann"]                # O(1) average   30
ages["cat"] = 40           # O(1) average   insert
"bob" in ages              # O(1) average   True. Membership tests the KEYS.
ages.get("dan", 0)         # O(1) average   0, a default instead of a KeyError
len(ages)                  # O(1)
del ages["bob"]            # O(1) average

for key, value in ages.items():     # O(n) to walk. items() itself is O(1),
    pass                            # because it is a view, not a copy.

# "Average" because a pile of hash collisions can degrade one lookup to O(n).
# On interview inputs, treat all of these as O(1).

Since Python 3.7, dicts keep insertion order when you iterate them. That is guaranteed, not an accident, and several solutions on this site rely on it for deterministic output.

set

If you know Java, this is HashSet. C++: std::unordered_set.

seen = set()               # O(1)  NOTE: {} is an empty dict, not an empty set
seen.add(3)                # O(1) average
3 in seen                  # O(1) average   True
seen.discard(9)            # O(1) average   remove if present, no error if absent
len(seen)                  # O(1)

a, b = {1, 2, 3}, {2, 3, 4}
a & b                      # O(min(|a|, |b|))  {2, 3}     intersection
a | b                      # O(|a| + |b|)      {1,2,3,4}  union
a - b                      # O(|a|)            {1}        difference

tuple

Closest to a lightweight, read-only struct or a record.

point = (2, 5)
x, y = point               # O(1)  unpacking

visited: set[tuple[int, int]] = set()
visited.add((2, 5))        # O(1) average. Legal, because tuples are hashable.
# visited.add([2, 5])      # TypeError: lists are not hashable

# Hashing a tuple is O(k) in its length, but k is a small constant such as 2
# for a grid coordinate, so in practice it is O(1).

That hashability is why every grid problem on this site stores coordinates as (row, col) tuples. Tuples also compare element by element, left to right, which is what makes (priority, index, task) work in a heap.

str

text = "hello"
text[0]                    # O(1)      'h'
text[1:3]                  # O(j - i)  'el', and it COPIES
len(text)                  # O(1)      5
"ell" in text              # O(n * m)  substring search, n = text, m = needle
# text[0] = "H"            # TypeError: strings do not support assignment

parts = ["a", "b", "c"]
joined = "".join(parts)    # O(total length)  'abc', ONE allocation

# The trap: building a string with += in a loop is O(n^2), because every +=
# copies everything written so far into a brand new string.

Coming from another language

Slicing in depth

The three parts

alphabet = ["a", "b", "c", "d", "e", "f"]
#  index      0    1    2    3    4    5
# -index     -6   -5   -4   -3   -2   -1

alphabet[1:4]      # O(3)  ['b', 'c', 'd']            1, 2, 3. Not 4.
alphabet[:3]       # O(3)  ['a', 'b', 'c']            start defaults to 0
alphabet[3:]       # O(3)  ['d', 'e', 'f']            stop defaults to the end
alphabet[:]        # O(n)  a full shallow COPY
alphabet[::2]      # O(n)  ['a', 'c', 'e']            every other item
alphabet[1::2]     # O(n)  ['b', 'd', 'f']            every other, offset by one

# The length of a[i:j] is exactly j - i, once both are clamped into range.
len(alphabet[1:4])  # 3

Negative indices count from the right

alphabet = ["a", "b", "c", "d", "e", "f"]

alphabet[-1]       # O(1)  'f'                  the last item
alphabet[-2:]      # O(2)  ['e', 'f']           the last two
alphabet[:-2]      # O(4)  ['a', 'b', 'c', 'd'] everything BUT the last two
alphabet[-3:-1]    # O(2)  ['d', 'e']           still half-open
alphabet[1:-1]     # O(4)  ['b', 'c', 'd', 'e'] drop the first and the last

A negative step walks backwards

alphabet = ["a", "b", "c", "d", "e", "f"]

alphabet[::-1]     # O(n)  ['f','e','d','c','b','a']   the reverse IDIOM
alphabet[::-2]     # O(n)  ['f', 'd', 'b']             backwards, every other
alphabet[4:1:-1]   # O(3)  ['e', 'd', 'c']             from 4 down to, not including, 1
alphabet[:2:-1]    # O(3)  ['f', 'e', 'd']             from the end down to index 3

Out-of-range is safe, unlike indexing

alphabet = ["a", "b", "c", "d", "e", "f"]

# alphabet[99]     # IndexError: list index out of range
alphabet[99:]      # O(1)  []            no error, just empty
alphabet[2:99]     # O(4)  ['c','d','e','f']  clamped to the end
alphabet[-99:2]    # O(2)  ['a', 'b']    clamped to the start
alphabet[4:2]      # O(1)  []            start after stop, so empty

That forgiveness is useful. batch = queue[:size] works whether or not there are size items left, so no length check is needed. It is also how bugs hide: an empty result may mean “nothing matched” or “my indices were nonsense”, and slicing will not tell you which.

A slice copies, and the copy is shallow

import copy

rows = [[1, 2], [3, 4]]

shallow = rows[:]              # O(n)  a NEW outer list, the SAME inner lists
shallow.append([5, 6])         # rows is unaffected: the outer list is new
shallow[0].append(99)          # rows[0] IS [1, 2, 99]: the inner list is shared

deep = copy.deepcopy(rows)     # O(size)  fully independent

Slice assignment: the part people never learn

buffer = [0, 1, 2, 3, 4]

buffer[1:3] = ["a", "b"]       # same length: plain replace  -> [0,'a','b',3,4]
buffer[1:3] = ["x"]            # SHORTER: the list shrinks   -> [0,'x',3,4]
buffer[1:2] = ["p", "q", "r"]  # LONGER: the list grows      -> [0,'p','q','r',3,4]
buffer[2:2] = ["mid"]          # empty slice = INSERT at 2   -> [0,'p','mid','q','r',3,4]
buffer[0:1] = []               # assigning [] DELETES        -> ['p','mid','q','r',3,4]

del buffer[1:3]                # the explicit delete         -> ['p','r',3,4]
buffer[:] = [9, 9]             # replace CONTENTS in place   -> [9, 9]

striped = [0, 0, 0, 0]
striped[::2] = [1, 1]          # OK: 2 targets, 2 values  -> [1, 0, 1, 0]
# striped[::2] = [1, 1, 1]     # ValueError: attempt to assign sequence of
                               #             size 3 to extended slice of size 2

The idioms worth recognising on sight

def rotate_left(items: list, k: int) -> list:
    """Move the first k items to the back. O(n) time, O(n) space.

    The modulo makes k larger than the length harmless, and it also makes
    an empty list safe, which a bare k would not.

    >>> rotate_left([1, 2, 3, 4, 5], 2)
    [3, 4, 5, 1, 2]
    >>> rotate_left([1, 2, 3], 7)
    [2, 3, 1]
    >>> rotate_left([], 3)
    []
    """
    if not items:
        return []
    k %= len(items)
    return items[k:] + items[:k]


def is_palindrome(text: str) -> bool:
    """Read the same forwards and backwards. O(n) time, O(n) space.

    Clear and idiomatic. The O(1)-space version is two converging pointers,
    which is Pattern 2.

    >>> is_palindrome("racecar")
    True
    >>> is_palindrome("abc")
    False
    """
    return text == text[::-1]

Naming a slice with slice()

The bracket syntax is sugar for a slice object. Building one explicitly lets you give a recurring range a name, which beats a magic [8:12] scattered through a parser.

record = "2026-08-28T10:07"

YEAR = slice(0, 4)             # O(1) to build
MONTH = slice(5, 7)
TIME = slice(11, None)         # None means "to the end"

record[YEAR]                   # '2026'
record[MONTH]                  # '08'
record[TIME]                   # '10:07'

The cost, and the trap

def starts_bad(text: str) -> list:
    out = []
    for i in range(len(text)):
        out.append(text[i:])   # O(n - i) COPY
    return out                 # total O(n^2)

def starts_good(text: str) -> list:
    # Carry the index and read text[i]
    # directly. Slice ONCE, at the end,
    # only if a substring is really
    # needed.
    return list(range(len(text)))

The same trap appears in recursion. solve(items[1:]) looks elegant and copies the list at every level, turning an O(n) recursion into O(n²). Pass items plus a start index instead. That is exactly why every template on this site threads indices rather than slices, from backtracking to binary search.

from itertools import islice


def head_of_stream(stream, k: int) -> list:
    """You cannot slice an iterator. islice takes k items lazily. O(k).

    >>> head_of_stream(iter(range(100)), 3)
    [0, 1, 2]
    """
    return list(islice(stream, k))       # generators have no [0:k]

Slicing elsewhere

Common bugs

What each operation actually costs

Know this table. Most accidental time-limit failures are one row of it.

collections

Counter

The problem it solves

counts: dict[str, int] = {}
for ch in "mississippi":       # O(n) overall,
    if ch not in counts:       # O(1) average
        counts[ch] = 0
    counts[ch] += 1

from collections import Counter

counts = Counter("mississippi")    # O(n), same cost, one line

What you can do with it

from collections import Counter

counts = Counter("mississippi")  # O(n)  Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})

counts["s"]                      # O(1) average   4
counts["z"]                      # O(1) average   0, and NO KeyError
counts.most_common(2)            # O(n log k)     [('i', 4), ('s', 4)]
counts.most_common()             # O(n log n)     no k, so it sorts everything
sum(counts.values())             # O(d)  11, d = number of DISTINCT keys
list(counts)                     # O(d)  the distinct characters, first-seen order

# Counters compare and combine directly, which anagram problems love.
Counter("listen") == Counter("silent")      # O(d)  True
Counter("aab") - Counter("ab")              # O(d)  Counter({'a': 1})
Counter("aab") + Counter("bc")              # O(d)  Counter({'a': 2, 'b': 2, 'c': 1})

# It counts any iterable, not just strings.
Counter([1, 1, 2])                          # O(n)  Counter({1: 2, 2: 1})

defaultdict

The problem it solves

graph: dict[str, list[str]] = {}
if "a" not in graph:      # O(1) average
    graph["a"] = []       # O(1) average
graph["a"].append("b")    # O(1) average

from collections import defaultdict

graph = defaultdict(list)
graph["a"].append("b")    # O(1) average, and no guard needed

The three factories you will use

from collections import defaultdict

# list: for adjacency lists and grouping
graph: defaultdict[str, list[str]] = defaultdict(list)
graph["a"].append("b")            # O(1) average  -> {'a': ['b']}

# int: for tallies, when you want to control the counting yourself
tally: defaultdict[str, int] = defaultdict(int)
tally["x"] += 1                   # O(1) average  starts from 0

# set: for de-duplicated groups
buckets: defaultdict[str, set[str]] = defaultdict(set)
buckets["k"].add("v")             # O(1) average

deque

If you know Java, this is ArrayDeque. C++: std::deque.

The problem it solves

A plain list looks like it can be a queue: append at the end, pop(0) at the front. But pop(0) shifts every remaining element left by one, so it is O(n). Do that inside a BFS loop and a linear algorithm becomes quadratic.

queue = [1, 2, 3]
first = queue.pop(0)      # O(n)  shifts everything left
queue.append(4)           # O(1)

from collections import deque

queue = deque([1, 2, 3])
first = queue.popleft()   # O(1)  no shifting
queue.append(4)           # O(1)

What you can do with it

from collections import deque

queue = deque([1, 2, 3])

queue.append(4)            # O(1)  add at the right
queue.appendleft(0)        # O(1)  add at the left
queue.pop()                # O(1)  remove from the right
queue.popleft()            # O(1)  remove from the left
len(queue)                 # O(1)
bool(queue)                # O(1)  False when empty, so `while queue:` reads well
queue[0]                   # O(1)  the ENDS are cheap
queue[len(queue) // 2]     # O(n)  the MIDDLE is not: a deque is not an array

recent = deque(maxlen=3)   # O(1) per push. Fixed size: a 4th item drops the oldest.

heapq

If you know Java, this is PriorityQueue. C++: std::priority_queue, though that one is a max-heap by default and Python’s is a min-heap.

The problem it solves

You repeatedly need the smallest item from a changing collection. Sorting after every change is O(n log n) each time. Scanning for the minimum is O(n) each time. A heap gives you the minimum in O(1) and maintains itself in O(log n).

import heapq

heap: list[int] = []            # just a list; heapq gives it the heap property

heapq.heappush(heap, 5)         # O(log n)
heapq.heappush(heap, 1)         # O(log n)
heapq.heappush(heap, 4)         # O(log n)

heap[0]                         # O(1)      1, the smallest, WITHOUT removing it
heapq.heappop(heap)             # O(log n)  1, removes and returns the smallest
len(heap)                       # O(1)

existing = [5, 1, 4]
heapq.heapify(existing)         # O(n)      IN PLACE, cheaper than n pushes
heapq.heapreplace(existing, 9)  # O(log n)  pop then push, ONE sift not two
heapq.nlargest(2, [5, 1, 4])    # O(n log k)  [5, 4]
heapq.nsmallest(2, [5, 1, 4])   # O(n log k)  [1, 4]

# What a heap cannot do cheaply:
9 in heap                       # O(n)  no fast search; it is not a sorted list

Two things Python makes you do by hand

import heapq

# A max-heap of 3, 7, 5 by negating on the way in and out.
max_heap: list[int] = []
for value in (3, 7, 5):
    heapq.heappush(max_heap, -value)    # O(log n) each, O(n log n) for the loop
largest = -heapq.heappop(max_heap)      # O(log n)  7

# Ordering by a key, with a safe tie-break in second position.
tasks: list[tuple[int, int, str]] = []
heapq.heappush(tasks, (2, 0, "write"))  # O(log n)
heapq.heappush(tasks, (1, 1, "read"))   # O(log n)
heapq.heappop(tasks)                    # O(log n)  (1, 1, 'read') comes out first

bisect

If you know C++, bisect_left is lower_bound and bisect_right is upper_bound. Java: Collections.binarySearch, though that returns a negative encoded value when absent.

import bisect

data = [1, 3, 3, 5]

bisect.bisect_left(data, 3)     # O(log n)  1, FIRST index where data[i] >= 3
bisect.bisect_right(data, 3)    # O(log n)  3, FIRST index where data[i] >  3
bisect.bisect_left(data, 4)     # O(log n)  3, where a 4 would be inserted

bisect.insort(data, 4)          # O(n)      the search is O(log n), the INSERT
                                #           shifts everything after it

itertools

from itertools import accumulate, combinations, permutations, product, groupby, pairwise

list(accumulate([1, 2, 3, 4]))            # O(n)  [1, 3, 6, 10]  running totals
list(accumulate([3, 1, 4], max))          # O(n)  [3, 3, 4]      running maximum

list(combinations([1, 2, 3], 2))          # O(C(n,k) * k)  order ignored
list(permutations([1, 2]))                # O(n! * n)      order matters
list(product([0, 1], repeat=2))           # O(k**n * n)    the full grid

list(pairwise([1, 2, 3]))                 # O(n)  [(1, 2), (2, 3)]  adjacent pairs
[(key, len(list(run))) for key, run in groupby("aaabbc")]   # O(n)

# Creating any of these iterators is O(1). The costs above are what you pay to
# WALK them, which wrapping in list(...) forces you to do all at once.

functools and @cache

from functools import cache, lru_cache, reduce, cmp_to_key


@cache
def fib(n: int) -> int:
    """O(2**n) without the decorator. O(n) with it."""
    return n if n < 2 else fib(n - 1) + fib(n - 2)


fib(100)                                   # O(n) on the first call, O(1) on a repeat
reduce(lambda a, b: a * b, [1, 2, 3, 4])   # O(n)  24, folds the list into one value

# A cache hit is a dict lookup: O(1) average, plus O(k) to hash the arguments.
# The memory cost is O(number of distinct argument tuples).

The traps

Mutable default argument

A default value is created once, when the function is defined, not on each call. So a default list is shared by every call forever.

def add(item, bucket=[]):
    # The list is created ONCE, when
    # the function is defined. Every
    # call shares it. Same O(1) cost,
    # wrong answer.
    bucket.append(item)
    return bucket

def add(item, bucket=None):
    if bucket is None:      # O(1)
        bucket = []
    bucket.append(item)     # O(1)
    return bucket

Aliased rows in a 2D grid

* 2 on a list repeats the reference, not the contents. You end up with two names for one row.

grid = [[0] * 3] * 2
grid[0][0] = 1
# O(rows) to build, and WRONG:
# grid is now [[1,0,0], [1,0,0]]
# because both rows are the SAME
# list object.

grid = [[0] * 3 for _ in range(2)]
grid[0][0] = 1
# O(rows * cols), and correct.
# The comprehension builds a fresh
# row each time.

The rest

Idioms worth having

from collections import Counter

# Iterate with an index, or two sequences together.
for index, value in enumerate("abc"):
    pass

for a, b in zip([1, 2], "xy"):
    pass

# Sort by a computed key. sorted() returns a new list; .sort() is in place.
words = ["bbb", "a", "cc"]
by_length = sorted(words, key=len)                 # O(n log n)  ['a', 'cc', 'bbb']
by_two = sorted(words, key=lambda w: (len(w), w))  # O(n log n)  length, then A-Z

# Descending without reversing afterwards.
descending = sorted([3, 1, 2], reverse=True)       # O(n log n)

# max and min take a key too.
longest = max(words, key=len)                      # O(n)

# Unpacking, including the starred form.
first, *rest = [1, 2, 3]
head, *middle, tail = [1, 2, 3, 4]

# Swap without a temporary. The right side is evaluated first.
a, b = 1, 2
a, b = b, a

# Chained comparison, which reads exactly like the maths.
n = 5
in_range = 0 <= n < 10

# any and all short-circuit: they stop at the first decisive element.
has_even = any(x % 2 == 0 for x in [1, 3, 4])      # O(n) worst case
all_positive = all(x > 0 for x in [1, 2])          # O(n) worst case

# Dict and set comprehensions.
squares = {x: x * x for x in range(3)}             # O(n)
letters = {ch for ch in "hello"}                   # O(n)

# The walrus operator, for "compute once, test, then reuse".
values = [1, 2, 3]
if (total := sum(values)) > 5:                     # O(n), and only ONCE
    leftover = total - 5

# Counting without a loop.
most_common_char, _ = Counter("aabbbcc").most_common(1)[0]   # O(n)

# A grid of the four cardinal moves, used in every BFS and DFS on a grid.
DIRECTIONS = ((1, 0), (-1, 0), (0, 1), (0, -1))

Limits of the language