Master LeetCode Algorithms: Essential Python Templates for Interviews

Python Syntax

reduce(function, iterable[, initializer])
reduce(lambda x,y: x*y, ns)  # product of array
reduce(lambda x,y: x+y, ns)  # sum of array
@functools.lru_cache(None)
res = helper(0, N, 0)
helper.cache_clear()
tuple(ns)  # hashable for parameters
q = list(map(lambda x: -x, ns))
heapq.heapify(q)
key = -heapq.heappop(q)
filter(function, iterable)
filter(lambda x: 2 < x < 10 and x % 2 == 0, range(18))
filter(dfs, range(len(graph)))
div, mod = divmod(sum(ns), 4)
random.randint(i, len(self.ns)-1)
sorted(pss, key=lambda x: [x[0], -x[1]])
# String functions
split(sep=None, maxsplit=-1)
strip([chars])
join(iterable)
replace(old, new[, count])
count(sub[, start[, end]])
startswith(prefix[, start[, end]])
endswith(suffix[, start[, end]])
cs in chrs
# deque functions
queue = deque([iterable, maxlen])
queue.append(val)
queue.appendleft(val)
queue.clear()
queue.count(val)
queue.insert(val, start, stop)
queue.pop()
queue.popleft()
queue.reverse()
queue.remove(val)
queue.rotate(n=1)
# list functions
lst.sort(key=None, reverse=False)
lst.append(val)
lst.clear()
lst.count(val)
lst.pop(val=lst[-1])
lst.remove(val)
lst.reverse()
lst.insert(i, val)
# dict functions
d = defaultdict(lambda: value)
pop(key, default)
setdefault(key, default)
update(other)
get(key, default)
clear()
keys()
values()
items()
dict1 = dict2
# set functions
s = set(lambda: value)
add(elem)
update(*others)
clear()
discard(elem)
# heapq functions
heap = []
heapq.heappush(heap, item)
heapq.heappop(heap)
heap[0]
heapq.heapify(x)
heapq.heappushpop(heap, item)
heapq.merge(*iterables, key=None, reverse=False)
heapq.nlargest(n, iterable, key=None)
heapq.nsmallest(n, iterable, key=None)
# bisect functions
bisect.bisect_left(ps, T, L=0, R=len(ns))
bisect.bisect_right(ps, T, L=0, R=len(ns))
bisect.insort_left(a, x, lo=0, hi=len(a))
bisect.insort_right(a, x, lo=0, hi=len(a))
# Bit operations
x & y  # AND
x | y  # OR
x ^ y  # XOR
x << y  # left shift
x >> y  # right shift
~x      # bitwise NOT
# Integer set bit tricks
vstd |= (1 << i)   # add i
vstd &= ~(1 << i)  # remove i
not vstd & (1 << i)  # check absence
A | B   # union
A & B   # intersection
(1 << n) - 1   # full set
((1 << n) - 1) ^ A   # complement
(A & B) == B   # subset test
A & (A-1) == 0   # power of two check
while n:
    n &= n-1
    ret += 1
n & -n   # lowest set bit
# Regex shortcuts
^   # start of string
[\+\-]  # plus or minus
?   # optional
\d  # digit
+   # one or more
\D  # non‑digit
*   # zero or more
matches = re.match('[ ]*([+-]?\d+)', s)

Knapsack Templates

# 0‑1 knapsack (no repetition)
for n in ns:
    for i in range(T, n-1, -1):
        dp[i] = max(dp[i], dp[i-n] + ws[i])
# Complete knapsack (unlimited, unordered, weight based)
for n in ns:
    for i in range(n, T+1):
        dp[i] = max(dp[i], dp[i-n] + ws[i])
# Complete knapsack (ordered, count based)
for i in range(1, T+1):
    for n in ns:
        dp[i] = max(dp[i], dp[i-n] + ws[i])

Backtracking Templates

# Backtracking with lru_cache pruning
@functools.lru_cache(None)
def backtrack(path, choices):
    if end_condition(path):
        result.append(path)
        return
    for choice in choices:
        if visited[choice]:
            continue
        # make choice
        backtrack(path + [choice], choices)
        # undo choice

Union‑Find Template

# Virtual node for connecting a feature
parent = {}
size = collections.defaultdict(lambda: 1)
cnt = 0
def find(x):
    parent.setdefault(x, x)
    while x != parent[x]:
        x = parent[x]
    return x
def union(x, y):
    nonlocal cnt
    if connected(x, y):
        return
    xP, yP = find(x), find(y)
    if size[xP] < size[yP]:
        parent[xP] = yP
    else:
        parent[yP] = xP
    size[xP] += size[yP]
    cnt -= 1
    return size[xP]
def connected(x, y):
    return find(x) == find(y)

Topological Sort Template

ins = [0] * n
ous = collections.defaultdict(list)
for cur, pre in ps:
    ins[cur] += 1  # indegree
    ous[pre].append(cur)  # outdegree
res = [i for i in range(n) if ins[i] == 0]
q = collections.deque(res)
while q:
    pre = q.popleft()
    for cur in ous[pre]:
        ins[cur] -= 1
        if not ins[cur]:
            q.append(cur)
            res.append(cur)

Monotonic Stack Template

# Decreasing monotonic stack (store indices)
stack = []
for i in range(len(ns)):
    while stack and ns[stack[-1]] <= ns[i]:
        stack.pop()
    # business logic here
    stack.append(i)

Binary Search Templates

# Standard binary search
while L <= R:
    M = (L + R) // 2
    if nums[M] == T:
        return M
    elif nums[M] < T:
        L = M + 1
    else:
        R = M - 1

Dynamic Programming Templates

# Single‑string DP (e.g., longest palindrome)
N = len(s)
dp = [[0]*N for _ in range(N)]
for j in range(N):
    dp[j][j] = 1
    for i in range(j-1, -1, -1):
        if s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1] + 2
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1])
# Interval DP (e.g., matrix chain multiplication)
for length in range(1, N):
    for i in range(N - length):
        j = i + length
        for k in range(i, j):
            # combine dp[i][k] and dp[k+1][j]
            pass
# LCS (two‑string longest common subsequence)
dp = [[0]*(M+1) for _ in range(N+1)]
for i in range(N):
    for j in range(M):
        if t1[i] == t2[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
# DP with state compression (bitmask)
# Catalan numbers example
dp = [1] + [0]*n
for i in range(1, n+1):
    for j in range(1, i+1):
        dp[i] += dp[j-1] * dp[i-j]

Prefix Sum Templates

# 1‑D prefix sum storing position
psd = {0: -1}
for i, val in enumerate(arr):
    s += val
    if s not in psd:
        psd[s] = i
    else:
        ans = max(ans, i - psd[s])
# 1‑D prefix sum storing count
psd = {0: 1}
for i, val in enumerate(arr):
    s += val
    if s - T in psd:
        ans += psd[s - T]
    psd[s] = psd.get(s, 0) + 1
# 2‑D prefix sum for sub‑matrix sum
cnt = 0
for top in range(m):
    ps = [0]*n
    for bottom in range(top, m):
        cur = 0
        dct = {0:1}
        for k in range(n):
            ps[k] += matrix[bottom][k]
            cur += ps[k]
            cnt += dct.get(cur - T, 0)
            dct[cur] = dct.get(cur, 0) + 1

Two‑Pointer Template

def removeElement(self, nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

Depth‑First Search & Tree Traversal Templates

# Recursive binary tree traversals
class Solution:
    def preorder(self, root):
        if not root:
            return []
        return [root.val] + self.preorder(root.left) + self.preorder(root.right)
    def inorder(self, root):
        if not root:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)
    def postorder(self, root):
        if not root:
            return []
        return self.postorder(root.left) + self.postorder(root.right) + [root.val]
# Iterative preorder using stack
class Solution:
    def preorder(self, root):
        if not root:
            return []
        stack, res = [root], []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res
# Level‑order (BFS) traversal
class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        q, ans = collections.deque([root]), []
        while q:
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(level)
        return ans
# N‑ary tree preorder (recursive)
class Solution:
    def preorder(self, root):
        if not root:
            return []
        res = [root.val]
        for child in root.children:
            res.extend(self.preorder(child))
        return res
# N‑ary tree preorder (iterative)
class Solution:
    def preorder(self, root):
        if not root:
            return []
        stack, res = [root], []
        while stack:
            node = stack.pop()
            res.append(node.val)
            stack.extend(node.children[::-1])
        return res

Graph Traversal & Shortest Path Templates

# BFS for undirected graph
q = collections.deque([start])
while q:
    cur = q.popleft()
    for nxt in graph[cur]:
        if not visited[nxt]:
            visited[nxt] = True
            q.append(nxt)
# BFS for binary tree level order (same as above)
# Dijkstra's algorithm
adj = collections.defaultdict(list)
for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))
heap = [(0, source)]
dist = [-1] * (n + 1)
while heap:
    d, u = heapq.heappop(heap)
    if dist[u] < 0:
        dist[u] = d
        for v, w in adj[u]:
            heapq.heappush(heap, (d + w, v))
# Floyd‑Warshall for all‑pair shortest paths
for k in nodes:
    for i in nodes:
        for j in nodes:
            if ds[(i, k)] and ds[(k, j)]:
                ds[(i, j)] = ds[(i, k)] * ds[(k, j)]