Python Cheatsheet for Algorithms

Know these before you pick a structure. Most "Time Limit Exceeded" results in Python come from an O(n) operation hiding inside a loop.

Trap: a.pop(0) and a.insert(0, x) shift every element, so each is O(n). If you pop from the front repeatedly (a queue, BFS), use collections.deque.

append vs extend vs +: a.append(x) adds x as one element, even when x is a list. a.extend(iterable) walks the iterable and adds each of its elements one by one. Both change a in place and return None.

extend costs O(k) time and O(k) extra space to grow the list by k elements.

Trap: nums = nums.extend([3, 4]) sets nums to None, because extend returns None. Call nums.extend([3, 4]) on its own line. The same holds for append, sort and reverse.

Trap: a.extend("dog") adds three characters 'd', 'o', 'g', not the word. To add the word as one element, use a.append("dog").

Full signatures

• Dicts keep insertion order (guaranteed since 3.7).
• Keys must be hashable: str, int, tuple, frozenset work, list / set / dict don't. That's why anagram keys are tuple(count) or "".join(sorted(word)).
• d1 == d2 is True when both have the same key-value pairs; insertion order doesn't matter, and the check is O(n).
• Trap: adding or removing keys while iterating over the dict raises RuntimeError. Iterate over list(d) if you need to delete as you go.

Full signatures

defaultdict(factory) calls factory() the first time you touch a missing key, so you never write "if key not in d" setup code.

Trap: just reading d[missing_key] inserts it. Use key in d to test membership without creating the key.

Full signatures

Counter (from collections) builds a frequency map in one call: Counter(iterable) counts occurrences of every element. It behaves like a dict but with .most_common(k), and missing keys default to 0 instead of raising KeyError.

More that comes up constantly:

The leftover-count line solves Ransom Note (LC 383) in one expression.

Trap in sliding windows: after c[x] -= 1 a key with count 0 still exists, so len(c) still counts it. Delete it (if c[x] == 0: del c[x]) when len(c) must mean "distinct values in the window".

Turning {key: frequency} into {frequency: key}. Top-K and bucket-sort problems need the map the other way round. Pick the form by one question: can two keys share the same frequency? They usually can, so the first four forms keep every key.

Here n is the number of items counted (len(s)) and u is the number of distinct keys (len(counts)). Forms 1, 3 and 4 make one pass over counts.items(), so they cost O(u) on top of the O(n) spent building counts; form 4 also allocates n + 1 empty lists, so it is O(n) in total. Form 2 sorts u pairs, so it costs O(u log u). Form 4 is what makes Top K Frequent Elements (LC 347) run in O(n): the last loop above walks buckets from the highest index down, and it can stop as soon as top holds k keys. The heapq section shows the same problem solved with a heap of size k.

Trap in form 5: {freq: key for key, freq in counts.items()} stores one key per frequency. When 'a' and 'c' both have count 2, the later key overwrites the earlier one and a key disappears without any error. Use form 3 or form 4 unless you know every count is different.

Trap in form 1: in on a list compares whole elements, so 3 in pairs is False even though (3, 'b') is in the list: every element is a tuple, and 3 != (3, 'b'). To ask "does any key have frequency 3?", look the frequency up in form 3 (3 in by_freq) or form 4 (buckets[3], which is a non-empty list), or scan the pairs with any(freq == 3 for freq, key in pairs).

defaultdict(int) vs Counter() — which one for frequency counting? For plain counting, counts[x] += 1 and counts[x] -= 1 behave the same on both: neither one deletes a key automatically when its count drops to 0 (that's why the trap above, and the defaultdict trap further up, both exist). The one real behavior difference is what happens on a missing-key read:

Use Counter() when you want those extra methods, or when you're building the whole frequency map in one call from an iterable (Counter(nums)). Use defaultdict(int) when the counting is a means to something else — e.g. a sliding-window frequency map you mutate key-by-key and never call .most_common() on — since a plain dict subclass with no extra methods is the more standard choice there. Either way, if your code also reads a key just to check it (not to count it), prefer defaultdict(int) only when you want that read to insert the key; otherwise reach for Counter(), or guard the read with key in counts first.

Full signatures

Full signatures

Sets. a & b (see set above) needs a set on both sides; s.intersection(any_iterable) also accepts a list or tuple: {1, 2, 3, 4}.intersection([3, 4, 5, 6]) is {3, 4}.

Lists (keep order or duplicates). A list comprehension keeps list1's order and its repeated values.

Dictionaries. keys() and items() views behave like sets, so & finds common keys or common key-value pairs.

Trap: x in list2 inside the comprehension is O(n), so the plain list version is O(n·m). Build set(list2) once first.

Full signatures

A double-ended queue with O(1) pushes and pops at both ends. Use it for every queue and every BFS.

BFS template (shortest path in steps on a grid):

Full signatures

Before Python 3.14, heapq only has min-heap functions, so for a max-heap you negate the values you push. Python 3.14 adds heapify_max, heappush_max and heappop_max; check that your judge runs 3.14 before you use them.

Example: Top K Frequent Elements (LC 347)

Heap patterns

Keep a sorted top-k list without a heap

top_k[i:-1] is a copy of the slice, so assigning it to top_k[i+1:] is safe. The last element drops off, and the list keeps its length k.

Cost: each number takes O(k) time to find its place and to shift. The whole stream takes O(n · k). A size-k heap takes O(n log k), so use this version only when k is small.

Example: Find the Kth Largest Integer in the Array (LC 1985)

The numbers arrive as strings. The size-k min-heap from the Heap patterns block above still works, but the heap must order the strings by numeric value, not alphabetically, so each push is keyed by the pair (len(s), s).

Tuples compare element by element, starting at index 0. With (len(s), s) the comparison takes two steps:

1. Length first. A positive integer with more digits is always larger, so (2, "10") beats (1, "7") on the lengths alone and the characters are never looked at.
2. The string as a tie-break. When two numbers have the same number of digits, their lengths tie and Python compares the strings. For strings of equal length, character-by-character order is the same as numeric order, so "21" > "12" is the right answer.

Each tuple comparison looks at up to L characters, so the heap work is O(n · L · log k) in total. The strings are never converted to int.

Full signatures

bisect finds insertion points in a sorted list in O(log n), so you don't have to hand-write binary search.

Example: Longest Increasing Subsequence (LC 300) in O(n log n)

tails[k] is the smallest tail of any increasing subsequence of length k + 1. Each number either extends the longest one or replaces a tail with a smaller value.

Binary search on a condition: key= over a range (3.10+)

bisect_left only needs len() and indexing, so a range works as a lazy list of candidates (nothing is built in memory). Pass a key that turns each candidate into False or True and search for True: the result is the position of the first candidate where the condition holds. This is the Lower Bound binary search in one line, and key runs only O(log n) times.

H-Index II (LC 275), Koko Eating Bananas (LC 875) and Sqrt(x) (LC 69), each in one line:

• The condition must be monotonic: all False, then all True. If it can flip back, the answer is quietly wrong.
• bisect never passes x through key: search for True (or a key value), not for a candidate.

key= on sorted records and descending lists

Full signatures

Maintain sorted order on insertion (recommended)

Use SortedList (from the sortedcontainers library) with defaultdict so every new key gets its own auto-sorted list:

SortedList.pop()

Works like a normal list's pop(), but each variant runs in O(log N):

• Use sl.pop(index) when you know the position.
• Use sl.remove(value) or sl.discard(value) when you know the value instead of its index.

More SortedList operations

sortedcontainers is available on LeetCode. It is the standard substitute for a balanced BST or C++ multiset.

Full signatures

Python doesn't take a two-argument comparator class the way some other languages do. Instead:

1. The key parameter (most common & Pythonic)

A single-argument function that transforms each item into something Python already knows how to sort.

SortedList from sortedcontainers accepts the same key: SortedList(data, key=lambda x: len(x)).

Python's sort is stable: items that compare equal keep their original order. For "descending by one field, ascending by another", negate the numeric field: key=lambda p: (-p.score, p.name).

2. functools.cmp_to_key (traditional two-argument comparator)

For logic too complex for a key transform, return -1/0/1 like a classic comparator:

Example: Largest Number (LC 179)

No single key works here: 9 must come before 34, but 3 must come after 34. Compare the two orders directly: a goes first when a + b is the bigger string.

3. Magic methods (__lt__ + @total_ordering)

For custom objects that need a default sort order everywhere:

Full signatures

The key idea from sorting works in many other functions: pass a one-argument function, and Python compares key(item) instead of item. The functions still return the original items, not the keys.

The heapq.nsmallest line below is K Closest Points to Origin (LC 973) in one call.

heapq.heappush, heappop and heapify take no key: push (key, tie_breaker, item) tuples instead (see heapq above).

Full signatures

enumerate: index + value together

Example: Two Sum (LC 1)

zip, range, any / all, grids

Full signatures

A generator (yield) produces values lazily, one at a time; wrapping it in list(...) forces it to run fully and collect every value.

A list comprehension does the same thing directly, without needing yield, when you don't need laziness:

Full signatures

With prefix sums p = list(accumulate(nums, initial=0)), the sum of nums[i..j] inclusive is p[j + 1] - p[i].

Full signatures

• Arguments to a cached function must be hashable: pass tuples, not lists.
• Inside a LeetCode class Solution, define the cached helper inside the method so the cache is fresh for every test case.

Deep recursion: three ways past the limit

A recursive DFS or backtracking whose depth can pass ~1000 (for example, a skewed tree with 10^4 nodes) hits Python's default limit of 1000 frames and raises RecursionError. In order of preference:

1. Go iterative with an explicit stack (the usual interview answer). The stack is an ordinary list, so there is no recursion limit at all.

Recursive (hits the limit):

Iterative (bypasses the limit):

Pushing the neighbors in reversed order makes the stack pop them first-to-last, so both versions process nodes in the same preorder. Both, as written, assume a tree: on a graph with cycles, add a visited set (mark a node when you push it, or skip already-visited nodes when you pop), or the loop never ends and nodes are processed more than once.

2. Raise the limit at the top of your file:

Caveat: sys.setrecursionlimit only raises Python's frame counter; it does not give the thread a bigger C stack. On an older Python that can crash the interpreter (a segfault, with no RecursionError to catch): in our test on Python 3.9, the code above crashed at a depth of 22,000 even with the limit at 200,000. Python 3.12 ran the same code to a depth of 199,990, but an @lru_cache recursion 10,000 deep still raised RecursionError there with the limit at 100,000.

3. Run the solver in a thread with a bigger stack, when the recursive form has to stay. The stack size has to be set before the thread starts:

On Python 3.9 this ran to a depth of 199,990, where the plain version crashed. It doesn't work in the in-browser Try-it: the browser's Python (Pyodide) can't start threads.

Full signatures

Bit tricks:

^= as a running parity toggle: XOR (^) outputs 1 when its two inputs differ and 0 when they're the same: 00=0, 11=0, 01=1, 10=1. A number's parity is 0 when it's even and 1 when it's odd, and parity adds the same way XOR does: even+even=even, odd+odd=even, even+odd=odd. That's why running_parity ^= value % 2 works as a toggle: it flips running_parity exactly when value is odd, and leaves it unchanged when value is even -- one ^= per step tracks a running sum's parity without ever recomputing sum(...) % 2 from scratch.

Full signatures

** means two different things, depending on where it sits.

1. Between two numbers, it is the power operator: a ** b is a raised to the power b.

• ^ is XOR, not power: 2 ^ 3 is 1.
• ** binds tighter than a leading minus and groups right to left: -2 ** 2 is -4, and 2 3 2 is 2 ** 9, i.e. 512.
• x ** 0.5 goes through a float, so it can be off by one for very large ints. For an exact integer square root, use math.isqrt(x) (see Numbers, math, and bits above).

2. In a function call or definition, it unpacks keyword arguments.

Unpacking a dict into a function call:

Capturing any number of keyword arguments inside a function:

• The dict's keys must match the function's parameter names; an unknown key raises TypeError.
• The same ** merges dicts: {a, b} (see dict above).

Full signatures

Full signatures

Longest Common Prefix (LC 14). You don't need sorting or a Trie for this. Horizontal scanning is the simplest:

How the options compare (M strings, S characters in total):

• Horizontal scanning (above): no sorting and no custom objects, just startswith and slicing. Every shrink re-checks the prefix from its start, so the worst case is O(S + L²) with L = len(strs[0]) (one very long first string and a short second one). Start from the shortest string, prefix = min(strs, key=len), to cap L at the shortest length.
• Length-sorting (O(M log M + M·N_min)): relies on sort()/enumerate, fast C-level built-ins, but pays a sorting step.
• Trie approach (O(S) to build): clean on paper, but it creates an object and a dict lookup per character, which adds real Python overhead.

Full signatures

Group Anagrams (LC 49) can be keyed two ways.

Approach 1: sort the word as the key (simpler, O(M · N log N))

All anagrams become the identical string once sorted, so use that as the dict key:

sorted(word) returns a list of characters, so join it back into a string ("aet") to use it as the key.

Approach 2: character-count tuple as the key (faster, O(M · N))

Count each letter into a fixed-size array (26 letters), then use the tuple as the key. This avoids the N log N sort cost per word:

Full signatures