Quick reference for solving algorithm problems in Python.
Small language tricks that save time.
list(path) or path[:] both create a copy of the path. Useful in backtracking problems: appending path itself stores a reference, so later changes to path would change the saved answer too.
| 1 | result.append(path[:]) # or: result.append(list(path)) |
A list can't go in a set (it isn't hashable), but a tuple can. Store each path as a tuple to drop duplicates, then turn the tuples back into lists when returning.
| 1 | result = set() |
| 2 | # To add a list path: |
| 3 | result.add(tuple(path)) |
| 4 | |
| 5 | # To return a list from a set |
| 6 | return [list(item) for item in result] |
In Python, path[-1] refers to the last element of the list path.
| 1 | path = [1, 4, 6] |
| 2 | path[-1] # 6 |
In Python, the check if path: evaluates whether the path list contains any items.
| 1 | path = [] |
| 2 | if path: # [] is falsy: skipped |
| 3 | print(path[-1]) |
| 4 | |
| 5 | path = [4] |
| 6 | if path: # [4] is truthy: runs |
| 7 | print(path[-1]) # 4 |
In Python, if run: will evaluate to False only for 0. Negative numbers evaluate to True.
| 1 | run = 0 |
| 2 | if run: |
| 3 | print("This will NOT print because 0 is False.") |
| 4 | |
| 5 | run = -1 |
| 6 | if run: |
| 7 | print("This WILL print because -1 is True.") |
| 8 | |
| 9 | run = 5 |
| 10 | if run: |
| 11 | print("This WILL print because 5 is True.") |
If you specifically want to check if a number is strictly greater than zero (ignoring both 0 and negative numbers), you must write the explicit comparison: if run > 0:.
In Python you can write an if on one line almost anywhere a value is expected: a if condition else b gives a when the condition is truthy and b otherwise. It works inside function arguments, string building, return, list comprehensions and assignments.
| 1 | # Inside a recursive call (Generalized Abbreviation): |
| 2 | # append the count only when it is non-zero |
| 3 | backtrack(i + 1, path + (str(run) if run else "") + word[i], 0) |
| 4 | |
| 5 | # Pick one of two values |
| 6 | step = 1 if ch == "(" else -1 |
| 7 | best = a if a > b else b |
| 8 | |
| 9 | # Turn "not found" into -1 on return |
| 10 | return dist if dist != float("inf") else -1 |
| 11 | |
| 12 | # Inside a list comprehension |
| 13 | labels = ["even" if x % 2 == 0 else "odd" for x in nums] |
Use it for choosing between two values. If a branch needs to run statements (append, pop, recurse), write a normal if block.
In Python, you cannot press Enter immediately after an equals sign (=) to start an expression on the next line without using a line continuation character. Because the opening curly brace { is on the next line, Python thinks the lettermap = statement is incomplete and will throw a SyntaxError.
| 1 | # SyntaxError: invalid syntax |
| 2 | lettermap = |
| 3 | { |
| 4 | "2": "abc", |
| 5 | } |
| 6 | |
| 7 | # Fixed: open the brace on the = line |
| 8 | lettermap = { |
| 9 | "2": "abc", |
| 10 | "3": "def", |
| 11 | } |
A set holds unique, unordered items. Build an empty one with set(), never {} (that is an empty dict). Passing any iterable to set(...) drops duplicates.
| 1 | s = set() # empty set |
| 2 | d = {} # careful: this is an empty DICT |
| 3 | s = {1, 2, 3} # literal |
| 4 | s = set([3, 1, 3, 2]) # {1, 2, 3} duplicates dropped |
| 5 | s = set("hello") # {'h', 'e', 'l', 'o'} |
| 6 | s = {x * x for x in range(4)} # set comprehension: {0, 1, 4, 9} |
add(x) inserts one item; adding something already there does nothing. update(...) (or |=) adds every item from one or more iterables.
| 1 | s = {1, 2} |
| 2 | s.add(3) # {1, 2, 3} |
| 3 | s.add(3) # still {1, 2, 3}, no error |
| 4 | s.update([4, 5], (6,)) # {1, 2, 3, 4, 5, 6} |
| 5 | s |= {7} # same as s.update({7}) |
remove(x) raises KeyError if x is missing; discard(x) does nothing instead, so reach for it when you are not sure the item is there. pop() removes and returns an arbitrary item (not the smallest, not the last added).
| 1 | s = {1, 2, 3} |
| 2 | s.remove(2) # {1, 3} |
| 3 | s.remove(99) # KeyError: 99 |
| 4 | s.discard(99) # no error, s unchanged |
| 5 | x = s.pop() # removes and returns some item |
| 6 | s.clear() # set() |
| 7 | set().pop() # KeyError: 'pop from an empty set' |
x in s is O(1) on average, versus O(n) for x in some_list. When a loop keeps asking "have I seen this?", turn the list into a set once, before the loop.
| 1 | seen = {3, 5, 8} |
| 2 | 5 in seen # True |
| 3 | 4 not in seen # True |
| 4 | |
| 5 | allowed = set(words) # O(n) once... |
| 6 | for w in queries: |
| 7 | if w in allowed: # ...then O(1) per lookup |
| 8 | ... |
s[0] raises TypeError: sets are unordered, so there is no first or i-th item. Iterate, peek with next(iter(s)), or sort when you need an order.
| 1 | s = {10, 20, 30} |
| 2 | s[0] # TypeError: 'set' object is not subscriptable |
| 3 | x = next(iter(s)) # peek at some item without removing it |
| 4 | x = next(iter(s), None) # same, but None when s is empty |
| 5 | for x in s: ... # visit every item (order not guaranteed) |
| 6 | min(s), max(s) # 10, 30 O(n) |
| 7 | sorted(s) # [10, 20, 30] a new list |
Operators need both sides to be sets; the method forms (a.union(...), a.intersection(...)) accept any iterable. The |=, &=, -=, ^= forms update a in place.
| 1 | a, b = {1, 2, 3}, {2, 3, 4} |
| 2 | a | b # {1, 2, 3, 4} union: in either |
| 3 | a & b # {2, 3} intersection: in both |
| 4 | a - b # {1} difference: in a, not in b |
| 5 | a ^ b # {1, 4} symmetric difference: in exactly one |
| 6 | a.union([5]) # method form takes any iterable |
| 7 | |
| 8 | {1, 2} <= a # True subset (a.issubset) |
| 9 | a >= {1, 2} # True superset (a.issuperset) |
| 10 | {1, 2} < a # True proper subset (not equal) |
| 11 | a.isdisjoint({7, 8}) # True no items in common |
| 12 | |
| 13 | a &= {2, 3, 9} # in place: a is now {2, 3} |
Comparing len(set(nums)) with len(nums) tells you whether anything repeats. list(set(nums)) removes duplicates but loses the original order; list(dict.fromkeys(nums)) keeps it.
| 1 | nums = [3, 1, 3, 2, 1] |
| 2 | len(set(nums)) != len(nums) # True: has duplicates |
| 3 | list(set(nums)) # [1, 2, 3] in some order |
| 4 | list(dict.fromkeys(nums)) # [3, 1, 2] original order kept |
Only hashable (immutable) values: numbers, strings, tuples. Lists, dicts and sets cannot go in a set. Convert a list to a tuple, and use frozenset when you need a set of sets.
| 1 | {[1, 2]} # TypeError: unhashable type: 'list' |
| 2 | {(0, 1), (2, 3)} # tuples are fine: grid cells, pairs |
| 3 | {tuple(path)} # store a path as a tuple |
| 4 | {{1}} # TypeError: unhashable type: 'set' |
| 5 | groups = {frozenset({1, 2})} # frozenset is hashable |
| 6 | frozenset({2, 1}) in groups # True: order does not matter |
Adding or removing items while a for loop walks the same set raises RuntimeError: Set changed size during iteration. Loop over a copy, or build a new set.
| 1 | for x in s: |
| 2 | if x % 2 == 0: |
| 3 | s.discard(x) # RuntimeError |
| 4 | |
| 5 | for x in list(s): # loop over a copy |
| 6 | if x % 2 == 0: |
| 7 | s.discard(x) # fine |
| 8 | |
| 9 | s = {x for x in s if x % 2} # or build a new set |
The most common set pattern: walk the input, check whether you have met the item before, then record it. Loading everything into a set up front also makes "does n - 1 exist?" an O(1) question, which is the trick behind Longest Consecutive Sequence.
| 1 | # Duplicate check |
| 2 | seen = set() |
| 3 | for x in nums: |
| 4 | if x in seen: |
| 5 | return True |
| 6 | seen.add(x) |
| 7 | return False |
| 8 | |
| 9 | # Longest Consecutive Sequence: only start counting at a run's first number |
| 10 | num_set = set(nums) |
| 11 | best = 0 |
| 12 | for n in num_set: |
| 13 | if n - 1 not in num_set: # n starts a run |
| 14 | length = 1 |
| 15 | while n + length in num_set: |
| 16 | length += 1 |
| 17 | best = max(best, length) |
Backtracking: add before the recursive call and remove right after, so the set only holds what is on the current path. A fresh used set created inside the call skips repeated values at the same depth. Grids: store cells as (r, c) tuples.
| 1 | # Permutations: indices on the current path |
| 2 | if i in used: |
| 3 | continue |
| 4 | used.add(i) |
| 5 | path.append(nums[i]) |
| 6 | backtrack() |
| 7 | path.pop() |
| 8 | used.remove(i) |
| 9 | |
| 10 | # Same-depth dedup (Non-decreasing Subsequences, Permutations II) |
| 11 | used = set() # new set for this call only |
| 12 | for i in range(start, len(nums)): |
| 13 | if nums[i] in used: |
| 14 | continue |
| 15 | used.add(nums[i]) |
| 16 | ... |
| 17 | |
| 18 | # Grid: cells as tuples |
| 19 | visited = {(0, 0)} |
| 20 | if (r, c) not in visited: |
| 21 | visited.add((r, c)) |
Average-case costs (hash collisions can make the worst case slower).
| 1 | x in s, s.add(x), s.remove(x), s.discard(x) # O(1) |
| 2 | set(iterable) # O(n) |
| 3 | a | b # O(len(a) + len(b)) |
| 4 | a & b # O(min(len(a), len(b))) |
| 5 | a - b # O(len(a)) |
| 6 | a <= b # O(len(a)) |
| 7 | min(s), max(s) # O(n) |
| 8 | sorted(s) # O(n log n) |
ord(c) gives a character's code number and chr(n) turns the number back into a character. Letters are consecutive, so 'a' to 'z' are 97 to 122 and 'A' to 'Z' are 65 to 90. That is what makes letter arithmetic work.
| 1 | ord("a") # 97 |
| 2 | ord("z") # 122 |
| 3 | ord("A") # 65 |
| 4 | ord("0") # 48 |
| 5 | chr(97) # 'a' |
| 6 | chr(65) # 'A' |
Subtract ord("a") to turn a lowercase letter into a position: 'a' is 0, 'b' is 1, ..., 'z' is 25. Add it back with chr to go from a position to a letter.
| 1 | idx = ord(c) - ord("a") # 'a' -> 0, 'd' -> 3, 'z' -> 25 |
| 2 | c = chr(idx + ord("a")) # 3 -> 'd' |
| 3 | |
| 4 | letters = [chr(ord("a") + i) for i in range(26)] # ['a', ..., 'z'] |
| 5 | # or: import string; string.ascii_lowercase |
When the input is only lowercase letters, a list of 26 zeros is a small, fast counter: slot ord(c) - ord("a") holds how many times c appears. Two strings are anagrams when their count arrays are equal. For any character (spaces, digits, capitals), use 128 slots and index with ord(c) directly.
| 1 | count = [0] * 26 |
| 2 | for c in s: |
| 3 | count[ord(c) - ord("a")] += 1 |
| 4 | # "banana" -> count[0] == 3 ('a'), count[13] == 2 ('n') |
| 5 | |
| 6 | # Valid Anagram: +1 for s, -1 for t, all zeros at the end |
| 7 | count = [0] * 26 |
| 8 | for a, b in zip(s, t): |
| 9 | count[ord(a) - ord("a")] += 1 |
| 10 | count[ord(b) - ord("a")] -= 1 |
| 11 | return all(x == 0 for x in count) |
| 12 | |
| 13 | # First unique character: count, then find the first count of 1 |
| 14 | for i, c in enumerate(s): |
| 15 | if count[ord(c) - ord("a")] == 1: |
| 16 | return i |
| 17 | |
| 18 | # Any ASCII character |
| 19 | count = [0] * 128 |
| 20 | count[ord(c)] += 1 |
collections.Counter(s) does the same job for any characters; the fixed array is handy when you need to compare counts (==) or use them as a key.
Words with the same letter counts are anagrams of each other. A list can't be a dict key, so convert the 26 counts to a tuple and group by it. This avoids sorting each word.
| 1 | from collections import defaultdict |
| 2 | |
| 3 | groups = defaultdict(list) |
| 4 | for word in strs: |
| 5 | key = [0] * 26 |
| 6 | for c in word: |
| 7 | key[ord(c) - ord("a")] += 1 |
| 8 | groups[tuple(key)].append(word) |
| 9 | return list(groups.values()) |
| 10 | # ["eat","tea","tan","ate","nat","bat"] -> [["eat","tea","ate"], ["tan","nat"], ["bat"]] |
To find every anagram of p inside s, keep one count array for p and one for the current window. Add the letter entering the window, subtract the one leaving, and compare the two arrays (26 slots, so each comparison is constant time).
| 1 | need, window = [0] * 26, [0] * 26 |
| 2 | for c in p: |
| 3 | need[ord(c) - ord("a")] += 1 |
| 4 | |
| 5 | res = [] |
| 6 | for i, c in enumerate(s): |
| 7 | window[ord(c) - ord("a")] += 1 # letter enters |
| 8 | if i >= len(p): |
| 9 | window[ord(s[i - len(p)]) - ord("a")] -= 1 # letter leaves |
| 10 | if window == need: |
| 11 | res.append(i - len(p) + 1) |
| 12 | # s = "cbaebabacd", p = "abc" -> [0, 6] |
Because codes are consecutive you can do math on characters: rotate a letter with % 26, read a digit character as a number, or change case (lowercase is exactly 32 above uppercase).
| 1 | # Shift a letter by k, wrapping around (Caesar cipher) |
| 2 | chr((ord(c) - ord("a") + k) % 26 + ord("a")) # 'z' + 1 -> 'a' |
| 3 | |
| 4 | # Digit character to int (same as int(c)) |
| 5 | ord("7") - ord("0") # 7 |
| 6 | num = 0 |
| 7 | for c in "305": |
| 8 | num = num * 10 + (ord(c) - ord("0")) # 305 |
| 9 | |
| 10 | # Case: lowercase = uppercase + 32 |
| 11 | ord("a") - ord("A") # 32 |
| 12 | chr(ord("q") - 32) # 'Q' (or c.upper()) |
Set bit ord(c) - ord("a") for every letter in a word, and the whole word's letter set fits in one integer. Two words share no letters exactly when mask1 & mask2 == 0, a single operation instead of comparing strings.
| 1 | def mask(word): |
| 2 | m = 0 |
| 3 | for c in word: |
| 4 | m |= 1 << (ord(c) - ord("a")) |
| 5 | return m |
| 6 | |
| 7 | mask("abc") & mask("def") == 0 # True: no shared letters |
| 8 | mask("abc") & mask("cat") != 0 # True: share 'a' and 'c' |
| 9 | bin(mask("abca")).count("1") # 3 distinct letters |
How the moving parts of a pattern change what it solves.
In backtracking algorithms, the argument passed into your recursive function—commonly named start, index, or begin—acts as a directional gatekeeper that prevents your search space from collapsing into redundant or infinite paths. Instead of hardcoding your loop to always scan from static 0, deriving the loop's starting boundary from this dynamic index dictates the fundamental nature of the problem you are solving, shifting the algorithm between combinations, permutations, and choices with or without repetition.
The mechanics of how that index controls the search space break down into distinct patterns:
| 1 | for i in range(start, len(nums)): |
The loop starts at start and only looks forward. Once an element at index i is processed, future recursive branches (backtrack(i + 1)) can never look backward to re-select elements from lower indices.
Subsets, combinations, and partition problems where order does not matter and elements cannot be reused (e.g., Subsets).
| 1 | for i in range(start, len(nums)): |
| 2 | # ... |
| 3 | backtrack(i) # Passing i instead of i + 1 |
By passing i instead of i + 1 into the next recursive call, the current element remains available to be picked again in the next branch.
Combination sum problems where the same number can be chosen an unlimited number of times (e.g., Combination Sum I).
| 1 | for i in range(0, len(nums)): |
Hardcoding the loop to start at 0 every single time means every recursive branch considers the entire array from the very beginning. To prevent infinite loops or redundant choices, you rely on a visited set or boolean array to track what's currently active in the path.
Permutations where order matters and every branch needs access to all elements (e.g., Permutations).
The passing index (start, i + 1, or i) acts as the structural gatekeeper. It defines the rules of engagement for the whole path—controlling whether you are building combinations (moving forward only), repeating choices (reusing items), or looking at the entire pool from scratch (permutations).
| 1 | def backtrack(start): |
| 2 | for i in range(start, len(nums)): # horizon scanner: which item comes next? |
| 3 | path.append(nums[i]) |
| 4 | backtrack(i + 1) # gatekeeper: i + 1, i, or a loop from 0 |
| 5 | path.pop() |
In Python, the check if path: evaluates whether the path list contains any items.
| 1 | for i in range(start, len(nums)): |
| 2 | if path and nums[i] < path[-1]: |
| 3 | continue # would break the non-decreasing order |
| 4 | path.append(nums[i]) |
| 5 | backtrack(i + 1) |
| 6 | path.pop() |
On a standard telephone keypad (and in LC 17: Letter Combinations of a Phone Number), the digit 9 maps to "wxyz", not "xywz". If you leave it as "xywz", your generated combinations will have the letters in the wrong order, causing test cases to fail.
| 1 | lettermap = { |
| 2 | "2": "abc", |
| 3 | "3": "def", |
| 4 | "4": "ghi", |
| 5 | "5": "jkl", |
| 6 | "6": "mno", |
| 7 | "7": "pqrs", |
| 8 | "8": "tuv", |
| 9 | "9": "wxyz", |
| 10 | } |