For better reading experience in Chinese, please refer to: LeetCode.

Preface

This article introduces techniques to reduce runtime in competitive programming using Python, under the premise that the complexity remains correct and unchanged. Each technique is accompanied by a Speedup on CPython 3.11.5 / PyPy 3.10.13.

I/O

Use fast input

Replace the built-in input with sys.stdin.readline. Each input() call incurs prompt handling and a sys.stdin lookup, while readline() reads a line directly. The more input lines, the larger the gap.

Speedup: CPython ~×4.2; PyPy ~×16.4.

import sys
input = lambda: sys.stdin.readline().rstrip()  # strip the trailing newline
II = lambda: int(input())
LII = lambda: list(map(int, input().split()))

Read all input at once

Use sys.stdin.read().split() to read everything into memory once, then consume as needed. This avoids calling the read function repeatedly.

Speedup: CPython ~×1.7; PyPy ~×1.0, since the JIT optimizes line-by-line reading to about the same speed.

import sys
# input contains only integers
it = map(int, sys.stdin.read().split())
II = lambda: next(it)
# input contains strings
it = iter(sys.stdin.read().split())
SI = lambda: next(it)
II = lambda: int(SI())

Buffer output and print once

Store all answers in a list and print them at once with print(*output), instead of calling print each time, reducing the number of output calls. Output is usually not the bottleneck, though.

Speedup: CPython ~×1.1; PyPy ~×1.0.

output = []
for _ in range(n):
    ans = solve()
    output.append(ans)
print(*output, sep='\n')

Data Types

int

Optimizing modulo

Integer modulo is essentially division, far more expensive than addition/subtraction/multiplication. So for adding/subtracting two integers within the MOD range, conditional branches might replace modulo. However, measurement contradicts this guess entirely! % is a fast C-level operation, while conditional branches are Python-bytecode-level and carry their own overhead; PyPy's JIT optimizes straight-line % even better, so branches are slower. Wrapping it in functions adds call overhead that is not worthwhile either.

Speedup: CPython ~×1.0; PyPy ~×0.20.

# Before
def add(x, y): return (x + y) % MOD
def sub(x, y): return (x - y) % MOD
# After
def add(x, y):
    x += y
    if x >= MOD: x -= MOD
    return x
def sub(x, y):
    x -= y
    if x < 0: x += MOD
    return x

Take modulo once at the end

If intermediate results do not grow too large (e.g. within long long range), do not take modulo at every step; take it once at the end.

Speedup: CPython ~×2.0; PyPy ~×3.3.

# Before
ans = 0
for i in range(n):
    ans = (ans + comb(n, i) * pow(2, i, MOD) % MOD) % MOD
# After
ans = 0
for i in range(n):
    ans += comb(n, i) * pow(2, i, MOD)
ans %= MOD

str

Use bytearray for mutable strings

Use bytearray(s, encoding) to create a C++-like mutable string, modify it in place, then decode, avoiding the round-trip of list(s), modifying a char, and join.

Speedup: CPython ~×1.0; PyPy ~×1.75, only useful when frequently modifying characters in place.

# Before
t = list(s)
t[0] = 'a'
s = ''.join(t)
# After
t = bytearray(s, encoding='ascii')
t[0] = ord('a')
s = t.decode('ascii')

list

Prefer iterators over index access

When iterating a container, fetch values through an iterator directly rather than indexing. If a built-in (such as enumerate) or an iterator (such as reversed, zip) can do the job, do not write for i in range(len(nums)). Each nums[i] is a separate index lookup (the BINARY_SUBSCR bytecode, with a bounds check and integer unboxing), whereas direct iteration follows the iterator protocol and reads sequentially, saving bytecode and improving cache locality.

Speedup: enumerate CPython ~×1.0, PyPy ~×1.2; reversed CPython ~×1.5, PyPy ~×1.5; zip CPython ~×1.2, PyPy ~×1.0.

# Before
for i in range(len(nums)):
    x = nums[i]
    ...
for i in range(len(nums) - 1, -1, -1):
    x = nums[i]
    ...
for i in range(len(a)):
    x, y = a[i], b[i]
    ...
# After
for i, x in enumerate(nums):
    ...
for x in reversed(nums):
    ...
for x, y in zip(a, b):
    ...

Preallocate list space

When the final length is known, allocate space with [0] * n and assign by index, instead of append-ing from an empty list. append triggers resizing and copying when capacity is insufficient; preallocation avoids repeated resizes.

Speedup: CPython ~×1.6; PyPy ~×5.0.

# Before
nums = []
for _ in range(n):
    nums.append(x)
# After
nums = [0] * n
for i in range(n):
    nums[i] = x

Put the larger dimension inside

When constructing a multi-dimensional list, make the longer dimension the inner list. This both reduces the number of list objects created and improves memory continuity.

Speedup: CPython ~×1.05; PyPy ~×1.5.

n, k = 10**5, 20
# Before
dp = [[0] * k for _ in range(n)]
# After
dp = [[0] * n for _ in range(k)]

Flatten multi-dimensional indices to one dimension

Flatten a multi-dimensional array into one dimension; for a 2D array, encode/decode indices manually with i * n + j. This removes one level of list indirection and is more cache-friendly.

Speedup: CPython ~×1.1; PyPy ~×1.1.

# Before
dp = [[0] * n for _ in range(m)]
# After
dp = [0] * (m*n)
compress = lambda i, j: i*n+j
decompress = lambda k: divmod(k, n)

Use slicing

When operating on a sub-array of a list, slice out the sub-array and process it directly, instead of accessing elements one by one by index. Slicing copies out the sub-array in one C-level operation, and built-in sum / max also traverse in C, so the whole thing is far faster than a Python-bytecode index loop.

Speedup: for sum, CPython ~×2.0, PyPy ~×0.72; for max, CPython ~×2.3, PyPy ~×1.8. Note that on PyPy, the cost of slicing can outweigh the JIT's optimization of the loop.

# Before
s = sum(nums[i] for i in range(l, r))
mx = 0
for i in range(l, r): mx = max(mx, nums[i])
# After
s = sum(nums[l:r])
mx = max(nums[l:r])

Use array.array instead of list

Replace a list of fixed-length integers needing frequent access and modification with array.array('i', ...). array stores C integers compactly in memory, saving space. However, each access to an array requires converting between Python int and C integer, which can be more expensive than the list itself.

Speedup: CPython ~×0.58; PyPy ~×0.73. This holds only for the memory-footprint scenario, not for high-frequency random access.

# Before
nums = [0] * n
# After
from array import array
nums = array('i', [0] * n)

Use bytearray instead of a boolean array

Replace [False] * n with bytearray(n). A boolean array is still a list, whereas bytearray stores one byte per element, compactly.

Speedup: CPython ~×1.7; PyPy ~×0.9. PyPy's list is already highly optimized, so bytearray is slower.

# Before
vis = [False] * n
# After
vis = bytearray(bytes(n))

Use a ctypes C array instead of list

Replace list with a ctypes c_int32 array. Each index into a ctypes array is a C call, with huge overhead.

Speedup: CPython ~×0.65; PyPy ~×0.003. This is only suitable for interop with C libraries, never as a frequently-accessed container.

# Before
rank = [0] * n
pa = list(range(n))
# After
from ctypes import c_int32
rank = (c_int32 * n)()
pa = (c_int32 * n)(*range(n))

tuple

Use a structure of arrays instead of an array of structures

Instead of combining multiple fields into a tuple and putting them in a list, use multiple lists to store the fields separately.

Speedup: CPython ~×0.75; PyPy ~×1.5.

# Before
items = [(w1, v1), (w2, v2), ...]
# After
weights = [w1, w2, ...]
values = [v1, v2, ...]

dict

Use list instead of dict / set

When the data range allows, replace key-accessed dict / set with index-accessed list. Hash-table access requires hashing and may trigger resize, far slower than direct array indexing.

Speedup: CPython ~×1.8; PyPy ~×1.6.

# Before
g = defaultdict(list)
# After
g = [[] for _ in range(n)]

Use dict.items for both key and value

When iterating a dict and needing both keys and values, use for k, v in mp.items() instead of for k in mp: v = mp[k]. The latter needs an extra hash lookup each time.

Speedup: CPython ~×1.2; PyPy ~×2.9.

# Before
for k in mp:
    v = mp[k]
    ...
# After
for k, v in mp.items():
    ...

Use .get for possibly-missing keys

For a defaultdict, when querying a key that may be missing, use mp.get(k, default) instead of mp[k]. mp[k] triggers __missing__ and inserts a new entry when the key is missing; get only reads and does not insert. The difference is notable when many queried keys are missing.

Speedup: CPython ~×1.3; PyPy ~×1.35.

mp = defaultdict(int)
# Before
x = mp[k]
# After
x = mp.get(k, 0)

Functions

Use built-in functions instead of handwritten loops

For reductions like max or sum, use built-in max / sum directly, not handwritten loops. Built-ins traverse in C, far faster than Python-bytecode loops.

Speedup: max CPython ~×1.4, PyPy ~×2.1; sum CPython ~×1.5, PyPy ~×1.0, since PyPy's JIT optimizes the handwritten sum loop to match the built-in. Reductions with a transform are an exception; see the next item.

# Before
mx = 0
for x in nums:
    if x > mx: mx = x
# After
mx = max(nums)

Use a handwritten loop for reductions with a transform

For reductions with a transform or filter, use a handwritten loop instead of a built-in, e.g. sum(x*x for x in nums) or sum(x for x in nums if cond). The reason: a generator goes through the yield protocol element by element, and each element round-trips between the generator and sum, which is more expensive than a tight handwritten loop.

Speedup: sum of squares CPython ~×1.35, PyPy ~×1.14; filtered sum with if CPython ~×1.18, PyPy ~×2.30.

# Before
s = sum(x for x in nums if x & 1)
# After
s = 0
for x in nums:
    if x & 1:
        s += x

Handwritten min/max

When comparing only two numbers, use x if x < y else y instead of min(x, y), and similarly for max. Since built-in min/max handle variadic arguments and type checking with extra overhead, the guess is that handwriting is faster.

Speedup: CPython ~×1.9; PyPy ~×0.83, where in fact the JIT optimizes built-in min/max to be faster than a lambda call.

# Before
x, y = min(x, y), max(x, y)
# After
fmin = lambda x, y: x if x < y else y
fmax = lambda x, y: x if x > y else y
x, y = fmin(x, y), fmax(x, y)

Handwritten fast exponentiation

When you need modular fast exponentiation, handwrite fast exponentiation instead of using pow(x, -1, MOD) (or pow(x, MOD-2, MOD)). The built-in pow's extended-Euclidean inverse path may be slower.

Measured result: CPython ~×0.20, because pow(x, -1, MOD) are single C calls, far faster than a Python loop; PyPy ~×1.8.

MOD = 10**9+7
# Before
inv = pow(x, -1, MOD)
# After
def qpow(x, k):
    res = 1
    while k:
        if k & 1:
            res = res * x % MOD
        x = x * x % MOD
        k >>= 1
    return res
inv = qpow(x, MOD-2)

Handwritten memo instead of @cache

For memoized search, do not use functools.cache; use an explicit memo array. @cache packs parameters into a tuple, hashes them, and stores results in a hash table plus a doubly linked list (LRU), which is costly; a handwritten array can be indexed directly.

Speedup: CPython ~×1.17; PyPy ~×2.6.

# Before
@cache
def dp(i: int, pre: int, islim: bool, isnum: bool) -> int:
    ...
# After
memo = [[-1] * 10 for _ in range(n)]
def dp(i: int, pre: int, islim: bool, isnum: bool) -> int:
    if not islim and not isnum and memo[i][pre] != -1:
        return memo[i][pre]
    ...

Use yield to produce results one by one

Change a function that collects results and returns them all at once into a generator that yields results one by one, saving the intermediate list allocation.

Speedup: CPython ~×1.2; PyPy ~×14.

# Before
def all_subsets(mask):
    subs = []
    cur = mask
    while cur:
        subs.append(cur)
        cur = (cur - 1) & mask
    return subs
# After
def all_subsets(mask):
    cur = mask
    while cur:
        yield cur
        cur = (cur - 1) & mask

Pass a generator instead of a list comprehension

For functions accepting an iterable, pass a generator expression directly instead of building a list first, saving the intermediate list allocation.

Speedup: CPython ~×1.13; PyPy ~×0.48, likely because a list comprehension plus sum takes a fast path, making the generator slower.

# Before
s = sum([x**2 for x in range(n)])
# After
s = sum(x**2 for x in range(n))

Wrap the main program in a function

Write the main logic inside main() and call it, making variables local. Local variables use LOAD_FAST, globals use LOAD_GLOBAL; the former is slightly faster.

Speedup: CPython ~×1.1; PyPy ~×1.0.

def main():
    ...
main()

Classes

Declare members with slots

List member variable names with __slots__ in the class, removing each instance's __dict__; attribute access is faster and memory is saved.

Speedup: CPython ~×1.18; PyPy ~×1.43.

# Before
class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
# After
class DSU:
    __slots__ = 'parent', 'size'
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n

Cache member variables into locals

For a self.x accessed frequently inside a method, assign it to a local variable first; the former is LOAD_ATTR, the latter LOAD_FAST.

Speedup: CPython ~×1.56; PyPy ~×1.0.

# Before
class DSU:
    def find(self, u: int):
        while u != self.parent[u]:
            u = self.parent[u]
        return u
# After
class DSU:
    def find(self, u: int):
        parent = self.parent
        while u != parent[u]:
            u = parent[u]
        return u

Use arrays instead of class instances

Use arrays instead of class instances, e.g. for tries, segment trees, etc. Class-instance creation and attribute access are both slow.

Speedup: CPython ~×0.97; PyPy ~×1.83.

# Before
class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.isend = False
        self.cnt = 0
class Trie:
    def __init__(self):
        self.root = TrieNode()
    ...
# After
class StaticTrie:
    def __init__(self, lengths):
        lengths += 1
        self.children = [[-1] * lengths for _ in range(26)]
        self.isend = [False] * lengths
        self.cnt = [0] * lengths
        self.ptr = 1
    ...

Miscellaneous

Simulate recursion with an explicit stack

When recursion is deep, simulate it with an explicit stack, or use an infinite-recursion decorator[^1]; sys.setrecursionlimit is not fully reliable. The reason is that function frames have overhead, and overly deep recursion overflows the stack, causing RE or MLE. Below is a pre-order traversal of a tree; a post-order traversal is obtained by reversing the pre-order result.

Speedup: CPython ~×0.85; PyPy ~×1.36.

order = []
# Before
def dfs(u: int, pa: int):
    order.append(u)
    for v in tree[u]:
        if v != pa:
            dfs(v, u)
# After
parents = [-1] * len(tree)
stk = [root]
while stk:
    u = stk.pop()
    order.append(u)
    for v in g[u]:
        if parents[u] != v:
            parents[v] = u
            stk.append(v)

Use a chained forward star instead of an adjacency list

When building a graph, do not use g = [[] for _ in range(n)] with append; use a chained forward star with four fixed-length arrays head / to / weight / nxt and head insertion.

Speedup: CPython ~×2.6; PyPy ~×7.9.

# Before
g = [[] for _ in range(n)]
def add_edge(u: int, v: int, w: int):
    g[u].append((v, w))
# After
head = [-1] * n
to = [-1] * m
weight = [0] * m
nxt = [-1] * m
ptr = 0
def add_edge(u: int, v: int, w: int):
    nonlocal ptr
    to[ptr] = v
    weight[ptr] = w
    nxt[ptr] = head[u]
    head[u] = ptr
    ptr += 1

Summary

Seize real optimizations, avoid negative ones

Most techniques in this article are significantly effective on at least one of CPython and PyPy, and the main theme — reduce object allocation and reduce the amount of Python bytecode executed — benefits both engines. Conversely, some taken-for-granted optimizations do not hold or are even slower on both engines. The core reason is that the dominant costs at the Python-bytecode level are branches, function calls, and attribute access; any so-called optimization that increases these tends to do more harm than good.

Each engine has its strengths

CPython has no hot-loop optimization and interprets bytecode line by line, so anything that pushes work down to the C level in one shot wins. PyPy has a JIT that compiles tight, type-stable Python loops to near-machine-code speed. Therefore: techniques that replace C built-ins with handwritten loops or plain containers are often ineffective or even slower on CPython, but may be faster on PyPy; conversely, techniques that rely on C built-ins or compact structures benefit CPython, while on PyPy they are often slower due to other overhead.

On the language itself

Python's nature determines that no matter how it is optimized, it cannot pass problems with large data ranges and high complexity. Moreover, the time spent writing Python and then optimizing it afterward is not necessarily faster than directly using C++. So although Python has some excellent language features, if you want to engage in professional competitive programming, it is better to drop the obsession with Python and learn C++.

References

[^1]: PyRival. https://github.com/cheran-senthil/PyRival/blob/master/pyrival/misc/bootstrap.py