Python Idioms and Tricks for CP

Two solutions can have identical Big-O and still differ by 20 lines and a subtle bug. Idiomatic Python is shorter to write under time pressure and avoids some of the most common contest bugs. This page is a reference you’ll come back to constantly.

What you’ll learn

• Comprehensions and generator expressions — and when to use which.
• Slicing and reversal without extra loops.
• Tuple packing/unpacking, enumerate, zip, and * unpacking.
• divmod for the pair every base-conversion problem needs.
• Bit tricks: lowest set bit, bit_count(), bit_length().
• Fast string building with join, and float("inf") as a sentinel.
• The 2D-array aliasing bug — the single most common silent bug in CP Python.

Comprehensions and generator expressions

A comprehension builds the whole collection in one expression; a generator expression (parentheses instead of brackets) produces items lazily, one at a time, without materializing the full list.

comprehensions.py

nums = [1, 2, 3, 4, 5, 6, 7, 8]
 
squares = [x * x for x in nums]                 # list comprehension
evens_squared = [x * x for x in nums if x % 2 == 0]
lookup = {x: x * x for x in nums}                # dict comprehension
unique_mods = {x % 3 for x in nums}               # set comprehension
 
# generator expression: no intermediate list — great for sum()/any()/all()
total_of_squares = sum(x * x for x in nums)
 
print(squares)
print(evens_squared)
print(lookup)
print(unique_mods)
print(total_of_squares)

Which to use

Need the actual list (to index into it, reuse it, or print it) → list comprehension. Just feeding it straight into sum/max/any/all → generator expression, it skips building the intermediate list entirely.

Visual intuition

Most of these idioms are shorthand for a loop you would otherwise write by hand. a[::-1] is the clearest case — it is this, in one expression and at C speed:

arrayWhat `a[::-1]` and `reversed(a)` are doing for youtwo pointers, one pass

102132435465

lohi

1def reverse(arr):2    lo, hi = 0, len(arr) - 13    while lo < hi:4        arr[lo], arr[hi] = arr[hi], arr[lo]5        lo += 16        hi -= 17    return arr

setupStart with pointers at both ends. Reversal swaps 3 pairs and allocates nothing.

Play‹›1/8⟲

Worth stepping through once so the idiom stops being magic: two cursors move inward swapping as they go. Note the difference the idioms hide -- a[::-1] builds a new list (O(n) extra space), a.reverse() mutates in place, and reversed(a) is a lazy iterator that allocates nothing. Picking the wrong one is a memory bug, not a style choice.

Slicing and reversal

Slicing is one of Python’s biggest CP advantages — no manual index loops.

slicing.py

arr = [10, 20, 30, 40, 50]
 
print(arr[1:4])       # middle chunk
print(arr[::-1])      # reversed copy, O(n)
print(arr[:3])        # first 3
print(arr[-2:])       # last 2
print(arr[::2])       # every other element
 
s = "competitive"
print(s[::-1])        # reverse a string just as easily
print(s == s[::-1])   # palindrome check in one line

Tuple packing/unpacking, enumerate, zip, *

unpacking_tour.py

# tuple packing / unpacking
point = (3, 4)
x, y = point
print("x:", x, "y:", y)
 
# swap without a temp variable
a, b = 1, 2
a, b = b, a
print("swapped:", a, b)
 
# enumerate: index + value, no manual range(len(...))
for i, val in enumerate(["a", "b", "c"]):
    print(i, val)
 
# zip: walk two sequences together
names = ["Ann", "Bo", "Cy"]
scores = [90, 85, 77]
for name, score in zip(names, scores):
    print(name, score)
 
# * unpacking: grab "the rest" of a sequence
first, *middle, last = [1, 2, 3, 4, 5]
print("first:", first, "middle:", middle, "last:", last)
 
# * to spread arguments
def add3(a, b, c):
    return a + b + c
 
nums = [1, 2, 3]
print(add3(*nums))

divmod: quotient and remainder together

divmod_tour.py

q, r = divmod(17, 5)
print("quotient:", q, "remainder:", r)
 
# classic use: base conversion
def to_base(n, base):
    digits = []
    while n:
        n, rem = divmod(n, base)
        digits.append(str(rem))
    return "".join(reversed(digits)) or "0"
 
print(to_base(26, 2))   # binary
print(to_base(255, 16)) # hex-ish (digits only, no a-f mapping here)

Bit tricks

bit_tricks.py

x = 44   # 0b101100
 
lowest_set_bit = x & -x
print("x:            ", bin(x))
print("lowest set bit:", bin(lowest_set_bit))
 
print("bit_count():  ", x.bit_count())    # number of 1 bits (Python 3.10+)
print("bit_length(): ", x.bit_length())   # bits needed to represent x
 
# power of two check, using the lowest-set-bit trick
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
 
print("16 is power of two:", is_power_of_two(16))
print("18 is power of two:", is_power_of_two(18))

bit_count on older Python

int.bit_count() needs Python 3.10+. On older versions, bin(x).count("1") does the same thing, just a bit slower.

Fast string building

Strings are immutable, so s += chunk in a loop silently creates a new string every time — $O(n)$ per concatenation, $O(n^2)$ total over a loop. Build a list of pieces and join once instead.

string_join.py

parts = []
for i in range(6):
    parts.append(str(i))
 
# one join at the end: O(n) total, not O(n^2)
result = "-".join(parts)
print(result)

float("inf"): the universal “worse than anything” sentinel

inf_sentinel.py

distances = {"a": 4, "b": 2, "c": 9}
 
best_node, best_dist = None, float("inf")
for node, dist in distances.items():
    if dist < best_dist:
        best_node, best_dist = node, dist
 
print("closest:", best_node, best_dist)

float("inf") (or math.inf) compares as larger than every real number, so it’s the standard starting value for a running minimum — no need for a sentinel like -1 that could collide with a real distance.

The 2D-array aliasing bug

This is the single most common silent bug in competitive Python: building a grid with [[0] * cols] * rows looks reasonable but creates rows aliases of the same inner list — mutate one row, and every row changes.

aliasing_bug.py

# THE BUG: all three rows are the SAME list object
grid_wrong = [[0] * 3] * 3
grid_wrong[0][0] = 9
print("wrong:", grid_wrong)   # every row shows the 9 — not what you wanted!
 
# THE FIX: build each row independently with a comprehension
grid_right = [[0] * 3 for _ in range(3)]
grid_right[0][0] = 9
print("right:", grid_right)  # only row 0 changed

Why this happens

[[0] * cols] * rows first builds one inner list [0] * cols, then repeats the reference to that same object rows times — Python doesn’t copy it. Any mutation through one row mutates the shared object every other row also points to. [[0] * cols for _ in range(rows)] calls [0] * cols fresh, once per row, so each row is a genuinely separate list.

Dry run

The 2D aliasing bug, side by side

The single most destructive one-line mistake in competitive Python:

Construction	After g[0][0] = 9	g[0] is g[1]
[[0] * 3] * 3	[[9,0,0], [9,0,0], [9,0,0]]	True
[[0] * 3 for _ in range(3)]	[[9,0,0], [0,0,0], [0,0,0]]	False

Verified. * 3 on a list of lists copies the reference three times, so all three rows are the same object — writing to one writes to all. The comprehension evaluates [0] * 3 afresh on each iteration, producing three distinct rows.

Note [0] * 3 on its own is perfectly safe, because integers are immutable — there is nothing to share. The bug appears only when the repeated element is itself mutable. That is why the idiom looks harmless and why it is so easy to write.

The failure mode is the worst kind: no exception, a plausible-looking grid, and a wrong answer that only shows up once you write to it. DP tables, visited grids and adjacency matrices are all built this way, so it tends to appear on exactly the problems where it is hardest to debug.

Slicing copies — so a slice in a loop is quadratic

s[a:b] builds a new object of length b - a. Each line looks $O(1)$; the loop is $O(n^2)$:

Pattern	Cost
while s: head, s = s[0], s[1:]	$O(n^2)$ — a fresh copy of the tail every iteration
Advance an index i instead	$O(n)$
s[::-1] once	$O(n)$, fine
reversed(s)	$O(1)$ — returns an iterator, copies nothing

The same applies to arr[1:] in a recursive function — a very common way to write an $O(n^2)$ solution to an $O(n)$ problem while every individual line looks innocent. Pass (arr, i) instead.

float("inf") and why it beats a magic number

The universal “worse than anything” sentinel:

python

best = float("inf")            # for a minimisation
best = float("-inf")           # for a maximisation

It compares correctly against every int and float, so there is no input value that can accidentally beat it. best = 10**9 fails the moment a legitimate answer exceeds a billion, and best = 0 in a maximisation fails on all-negative input — which is exactly the Kadane trap.

Two caveats worth knowing: float("inf") makes the variable a float, so a result printed from it may read 7.0 rather than 7; and int(float("inf")) raises OverflowError. When the answer must be an integer, either cast at the end or use a provably-larger integer sentinel.

Bit tricks worth recognising

Expression	Meaning
x & 1	is x odd
x >> 1	x // 2 (floor, for non-negative x)
x & (x - 1)	clear the lowest set bit
x & -x	isolate the lowest set bit
x & (x - 1) == 0	x is a power of two (for x > 0)
bin(x).count("1") / x.bit_count()	population count — bit_count() from 3.10
1 << k	the kth bit set — subset enumeration
x ^ y	differing bits; x ^ x == 0 is the XOR-pairing trick

Careful with >> on negative numbers: Python’s integers are arbitrary precision and >> floors, so -7 >> 1 is -4, not -3. Same asymmetry as //, and it bites when translating a C++ solution.

Practice

Drill 1 — generator expression sum. Sum only the even squares without building an intermediate list.

pch.exerciseTag pch.exerciseTitle

Drill 2 — lowest set bit. Compute the lowest set bit of x using the x & -x trick.

pch.exerciseTag pch.exerciseTitle

Drill 3 — fix the aliasing bug. Build a 3x3 grid where mutating one row does not affect the others.

pch.exerciseTag pch.exerciseTitle

Complexity

Idiom	Cost	Note
[expr for x in it]	$O(n)$ time, $O(n)$ space	materialises the whole list
(expr for x in it)	$O(n)$ time, $O(1)$ space	streams — one character’s difference
s[a:b]	$O(b-a)$	copies — quadratic inside a loop
s[::-1]	$O(n)$	one copy; fine once
reversed(s)	$O(1)$	an iterator, no copy
"".join(parts)	$O(\text{total})$	the correct way to build a string
enumerate, zip	$O(1)$ per step, lazy	no intermediate list
a, b = b, a	$O(1)$	builds and unpacks a tuple, still constant
divmod(a, b)	$O(1)$	one operation instead of // and %
x & -x, x & (x-1)	$O(1)$ for machine-size ints	$O(\text{bits})$ for big integers
x.bit_count()	$O(\text{bits})$	3.10+; bin(x).count("1") builds a string first
[[0]*m for _ in range(n)]	$O(nm)$	the correct 2D construction
[[0]*m]*n	$O(n)$	and wrong — n aliases of one row

The two that change the complexity class rather than the constant:

• A comprehension where a generator would do. sum([x*x for x in data]) allocates n values; sum(x*x for x in data) allocates none. Same time, $O(n)$ against $O(1)$ space.
• Slicing inside a loop or a recursion. Every arr[1:] is a full copy, so an $O(n)$ algorithm becomes $O(n^2)$ with no visible loop nesting. Pass an index.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is [[0]*3]*3 wrong?”	Reference semantics	The outer *3 copies the reference, so all three rows are one object — verified g[0] is g[1] is True, and writing to one writes to all. Use [[0]*m for _ in range(n)]. Note [0]*3 alone is fine, because ints are immutable
“What is the complexity of arr[1:] in a recursive call?”	The hidden copy	$O(n)$ per call, so an $O(n)$ recursion becomes $O(n^2)$ — and nothing in the source looks nested. Pass (arr, i) instead
“Comprehension or generator?”	Space awareness	Generator when you only consume it once — $O(1)$ space against $O(n)$, one character’s difference. Comprehension when you need to index or re-iterate it
“Why float('inf') rather than a big number?”	Robustness	It compares correctly against every int and float, so no legitimate input can beat it. 10**9 fails on larger answers; 0 in a maximisation fails on all-negative input. Caveat: it makes the value a float, and int(inf) raises OverflowError
“What does x & -x do?”	Bit fluency	Isolates the lowest set bit — the basis of Fenwick tree traversal. x & (x-1) clears it, which is the basis of the population-count loop and the power-of-two test
“-7 >> 1 in Python?”	Language precision	-4, not -3 — Python floors where C++ truncates, the same asymmetry as // and %. It bites when porting a formula from a C++ editorial
“How do you build a string in a loop?”	The habit	Collect into a list and "".join once. CPython often optimises += in place at refcount 1, but that is fragile and not guaranteed — join is faster and unconditional
“Swap two variables”	Idiom fluency	a, b = b, a. It builds and unpacks a tuple, so still $O(1)$, and it needs no temporary
“Reverse a string or list”	Knowing the three options	s[::-1] for a reversed copy ($O(n)$), reversed(s) for an iterator ($O(1)$), list.reverse() in place. Pick by whether you need a copy

Self-check

pch.quizTag pch.quizDefaultTitle

1. `g = [[0]*3]*3`, then `g[0][0] = 9`. What is g?

   A [[9,0,0], [0,0,0], [0,0,0]] B [[9,0,0], [9,0,0], [9,0,0]] -- the outer *3 copies the reference, so all three rows are the same object C It raises a TypeError D [[9,0,0], [0,0,0], [0,0,0]] but only in Python 3.7+
   pch.quizShowAnswer

   B — [[9,0,0], [9,0,0], [9,0,0]] -- the outer *3 copies the reference, so all three rows are the same object — Verified, and `g[0] is g[1]` returns True. The comprehension form `[[0]*3 for _ in range(3)]` evaluates the inner list afresh each iteration and gives the expected result. Note `[0]*3` on its own is completely safe because ints are immutable -- the bug needs a mutable repeated element, which is why the idiom looks harmless.

2. Why is the 2D aliasing bug especially hard to debug?

   A It raises an exception far from its cause B It raises nothing at all -- you get a plausible grid and a wrong answer, and it only manifests once you write to it C It only occurs on large grids D It depends on the Python version
   pch.quizShowAnswer

   B — It raises nothing at all -- you get a plausible grid and a wrong answer, and it only manifests once you write to it — Construction succeeds, printing the grid before any writes looks correct, and reads behave normally. The corruption appears only on the first write and then spreads invisibly. Because DP tables, visited grids and adjacency matrices are all built this way, it tends to show up on exactly the problems where the state is hardest to inspect.

3. `while s: head, s = s[0], s[1:]` over a string of length n. What is the total cost?

   A O(n) -- one character per iteration B O(n^2) -- each slice copies the whole remaining tail, and nothing in the source looks nested C O(n log n) D O(1) amortised
   pch.quizShowAnswer

   B — O(n^2) -- each slice copies the whole remaining tail, and nothing in the source looks nested — Slicing constructs a new object of length b - a, so the loop copies n + (n-1) + (n-2) + ... characters. Every individual line looks constant, which is what makes this a favourite way to write a quadratic solution to a linear problem. The same trap applies to `arr[1:]` inside a recursion -- pass an index instead.

4. Why prefer `float('inf')` over `best = 10**9` as a sentinel?

   A It is faster to compare B It compares correctly against every int and float, so no legitimate input value can beat it -- whereas 10**9 fails as soon as a real answer exceeds it C It uses less memory D It works with integer division
   pch.quizShowAnswer

   B — It compares correctly against every int and float, so no legitimate input value can beat it -- whereas 10**9 fails as soon as a real answer exceeds it — The magic-number version fails silently on inputs larger than you guessed, and `best = 0` in a maximisation fails on all-negative input -- the Kadane trap. Two caveats worth naming: float('inf') makes the variable a float, so results may print as 7.0, and int(float('inf')) raises OverflowError.

5. What does `x & -x` compute?

   A Clears the lowest set bit B Isolates the lowest set bit -- the basis of Fenwick tree index traversal C Negates x D Tests whether x is a power of two
   pch.quizShowAnswer

   B — Isolates the lowest set bit -- the basis of Fenwick tree index traversal — Two's complement makes -x equal to ~x + 1, which flips every bit above the lowest set bit and leaves that bit set -- so the AND keeps exactly it. `x & (x-1)` is the one that *clears* it, and `x & (x-1) == 0` is therefore the power-of-two test for positive x. Confusing the two is easy and the Fenwick tree needs the isolating form.

6. What is `-7 >> 1` in Python?

   A -3, matching C++ B -4 -- Python floors, where C++ truncates toward zero C 3 D It raises for negative operands
   pch.quizShowAnswer

   B — -4 -- Python floors, where C++ truncates toward zero — The same asymmetry as `//`: Python floors toward negative infinity, so -7 >> 1 and -7 // 2 both give -4 while C++ gives -3. It matters when translating a formula from a C++ editorial, and `%` has the matching quirk -- Python's result takes the divisor's sign, so -7 % 2 is 1.

7. `sum([x*x for x in data])` versus `sum(x*x for x in data)`. What differs?

   A Nothing -- the brackets are optional B The generator streams in O(1) extra space; the list comprehension materialises all n values first, O(n) C The list version is asymptotically faster D The generator version cannot be summed
   pch.quizShowAnswer

   B — The generator streams in O(1) extra space; the list comprehension materialises all n values first, O(n) — One character changes the space profile from constant to linear. The list version is marginally faster for small n because generator resumption has per-item overhead, but on large data the allocation dominates. It is the cheapest space optimisation in Python, and the reverse choice -- a comprehension -- is right when you need to index or re-iterate the result.

Recall card

• [[0]*m]*n is the destructive bug: n aliases of one row, verified g[0] is g[1] == True. Use [[0]*m for _ in range(n)]. [0]*m alone is safe — ints are immutable.
• Slicing copies. s[a:b] is $O(b-a)$, so arr[1:] in a loop or recursion is a hidden $O(n^2)$. Pass an index.
• reversed(s) is $O(1)$ (an iterator); s[::-1] is $O(n)$ (a copy). Pick by whether you need a copy.
• A generator is $O(1)$ space where a comprehension is $O(n)$ — one character.
• float("inf") / float("-inf") as sentinels: they beat every real value. But they make the variable a float, and int(inf) raises OverflowError.
• Bit essentials: x & -x isolates the lowest set bit (Fenwick) · x & (x-1) clears it · x & (x-1) == 0 tests a power of two · 1 << k for subsets · x.bit_count() from 3.10.
• -7 >> 1 is -4. Python floors; C++ truncates. Same for // and %.
• Build strings with "".join(parts) — unconditional, unlike CPython’s fragile in-place +=.
• divmod(a, b) for quotient and remainder in one call; a, b = b, a to swap with no temporary.

Recap

• Comprehensions build a full collection; generator expressions feed sum/any/all/max lazily without materializing one.
• Slicing ([::-1], [a:b]) replaces most manual index loops.
• enumerate, zip, * unpacking, and divmod cut boilerplate everywhere.
• x & -x, bit_count(), bit_length() are the bit tricks worth memorizing.
• Build strings with a list + "".join(...), never += in a loop.
• Never [[0] * cols] * rows — always [[0] * cols for _ in range(rows)].

You now have the Python-specific toolkit. Next phase: Core Data Structures — arrays, linked lists, stacks, queues, trees, graphs, and heaps, built from scratch and used in practice.