Python for DSA — Beginner to Intermediate
(Cheatsheet + Templates)
Generated on July 29, 2025. This compact guide focuses on Python syntax and patterns you actually use
in data structures & algorithms. Bold headings and mixed fonts (Helvetica & Courier) are used for clarity.
Tip: In coding interviews/contests, stick to the Python standard library. Avoid heavy external packages.
0) Prerequisites — What to Know First
• Math & Logic: arithmetic, modulo, inequalities, basic combinatorics, logarithms.
• Complexity: Big■O, time vs space, worst/avg/best case.
• Recursion: base case + progress; understand the call stack.
1) Python Setup & Running
Environment: Prefer Python 3.11/3.12. Optional virtualenv; run files & REPL.
python -m venv .venv
# Activate:
# macOS/Linux: source .venv/bin/activate
# Windows: .venv\Scripts\activate
pip install -U pip
python main.py
python -i # interactive shell
For most DSA tasks, the built■in library is enough.
2) Python Syntax — DSA■Focused
2.1 Core Types
Type Literal examples Notes
int 0, -7, 10**9 + 7 Arbitrary precision (no overflow).
float 3.14, 1e-9 Floating■point; beware precision issues.
bool True, False Subclass of int; True == 1.
str "abc", 'x', f"{n}" Immutable; rich methods.
list [1,2,3] Dynamic array; append amortized O(1).
tuple (1,2), 1, Immutable; hashable if elements hashable.
dict {"a":1} Hash map; avg O(1) get/set.
set {1,2,3} Hash set; avg O(1) add/contains.
None None Sentinel / 'no value'.
2.2 Variables & Operators
x = 5
x += 1 # arithmetic: + - * / // % **
a, b = b, a # swap
3 <= x < 10 # chained comparisons
x = y if cond else z # ternary
# Integer division vs float division:
Python for DSA — Beginner to Intermediate Page 1
a // b, a / b
# Fast quotient & remainder:
q, r = divmod(a, b)
2.3 Strings
s = "abc"
s[i], s[-1] # index
s[1:4], s[::-1] # slice, reverse
"".join(list_of_strings)
s.count('a'); s.find('a'); s.replace("ab", "x")
Strings are immutable; build large strings with ''.join(...) for speed.
2.4 Lists & Slicing
arr = [1,2,3]
arr.append(4); arr.pop()
arr.extend([5,6])
arr.insert(0, 99) # O(n)
arr.remove(2) # remove first 2 (O(n))
arr.sort() # in-place; Timsort
sorted_arr = sorted(arr, key=lambda x: x)
sub = arr[l:r] # slicing copies
2.5 Comprehensions
squares = [x*x for x in range(10) if x%2==0]
keys = {c for c in "banana"} # set comp
index = {v:i for i,v in enumerate(arr)} # dict comp
2.6 Control Flow
if cond:
...
elif other:
...
else:
...
for i in range(n): # 0..n-1
...
while condition:
...
break; continue
2.7 Functions & Scope
def f(a, b=0, *args, **kwargs):
return a + b
from functools import lru_cache
@lru_cache(None)
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)
# Avoid mutable default args; prefer None then create inside.
2.8 Exceptions
try:
Python for DSA — Beginner to Intermediate Page 2
risky()
except ValueError:
handle()
else:
post_success()
finally:
cleanup()
2.9 Lightweight Classes
class Node:
def __init__(self, val=0, nxt=None):
self.val, self.next = val, nxt
from dataclasses import dataclass
@dataclass
class Edge:
u: int; v: int; w: int
2.10 Typing Hints
from typing import List, Dict, Tuple, Optional, Deque, Set
def two_sum(nums: List[int], target: int) -> Tuple[int,int]:
...
2.11 Fast I/O Pattern
import sys
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
arr = [int(next(it)) for _ in range(n)]
print(*arr) # space-separated
Python for DSA — Beginner to Intermediate Page 3
3) Must■Know Standard Library
Module / Type Why it matters Snippet
collections.deque O(1) pops/appends at both ends (queues, sliding
dq=deque();
window) dq.append(x); dq.popleft()
collections.Counter Frequency maps quickly cnt=Counter(s)
collections.defaultdict Auto-initialize containers (graphs) g=defaultdict(list)
heapq Binary heap / priority queue heappush(h,(prio,item)); heappop(h)
bisect Binary search on sorted lists i=bisect_left(a,x)
itertools Combinatorics, fast loops product, permutations, accumulate
functools lru_cache, cmp_to_key memoization, custom sort
math gcd, isqrt, lcm, sqrt number theory & geometry helpers
deque See collections.deque BFS queues
4) Big■O of Python Containers (Average Case)
Structure Access Insert Delete Notes
list O(1) append O(1) amort.; insert at i O(n) pop() O(1), pop(i) O(n) Dynamic array
dict — O(1) O(1) Hash map
set — O(1) O(1) Hash set
heapq min at top O(1) push O(log n) pop O(log n) Use negatives for max■heap
deque — append/appendleft O(1) popleft/pop O(1) Great for BFS
Worst cases can degrade, but average■case is what matters in practice.
Python for DSA — Beginner to Intermediate Page 4
5) Core Data Structures (Python■Friendly)
5.1 Stack / Queue / Monotonic Stack
# Stack
st = []
st.append(x); x = st.pop()
# Queue (deque)
from collections import deque
q = deque([start])
q.append(x); x = q.popleft()
# Monotonic stack (Next Greater Element pattern)
st = []
for i, x in enumerate(arr):
while st and arr[st[-1]] < x:
j = st.pop() # arr[j]'s next greater is x
st.append(i)
5.2 Linked List — Iterative Reverse
class ListNode:
def __init__(self, val=0, nxt=None):
self.val, self.next = val, nxt
def reverse(head):
prev = None
cur = head
while cur:
cur.next, prev, cur = prev, cur, cur.next
return prev
5.3 Hash Map / Set
seen = set()
for x in arr:
if target - x in seen:
# found a pair
...
seen.add(x)
5.4 Heap / Priority Queue
import heapq
h = []
heapq.heappush(h, (priority, item))
prio, item = heapq.heappop(h)
# Max-heap via negatives:
heapq.heappush(h, (-priority, item))
• Use cases: Dijkstra; k■smallest/largest; merging k lists.
5.5 Trees — Traversals
class T:
def __init__(self, val=0, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder(root):
if not root: return
inorder(root.left); print(root.val); inorder(root.right)
Python for DSA — Beginner to Intermediate Page 5
from collections import deque
def level_order(root):
if not root: return []
q, ans = 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
5.6 Graphs — BFS/DFS & Topo Sort
from collections import defaultdict, deque
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u) # undirected
def bfs(src):
q = deque([src])
seen = {src}
dist = {src:0}
while q:
u = q.popleft()
for v in g[u]:
if v not in seen:
seen.add(v); dist[v] = dist[u] + 1
q.append(v)
return dist
def dfs(u, seen=None):
if seen is None: seen = set()
if u in seen: return
seen.add(u)
for v in g[u]: dfs(v, seen)
def topo_sort(n, edges):
g = [[] for _ in range(n)]
indeg = [0]*n
for u,v in edges: g[u].append(v); indeg[v]+=1
q = deque([i for i in range(n) if indeg[i]==0])
order = []
while q:
u = q.popleft(); order.append(u)
for v in g[u]:
indeg[v]-=1
if indeg[v]==0: q.append(v)
return order if len(order)==n else [] # empty => cycle
5.7 Union–Find (Disjoint Set Union)
class DSU:
def __init__(self, n):
self.p = list(range(n))
self.r = [0]*n
Python for DSA — Beginner to Intermediate Page 6
def find(self, x):
if self.p[x]!=x: self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra==rb: return False
if self.r[ra] < self.r[rb]: ra, rb = rb, ra
self.p[rb] = ra
if self.r[ra]==self.r[rb]: self.r[ra]+=1
return True
5.8 Trie (Prefix Tree)
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
cur = self.root
for ch in word:
cur = cur.children.setdefault(ch, TrieNode())
cur.end = True
def search(self, word):
cur = self.root
for ch in word:
if ch not in cur.children: return False
cur = cur.children[ch]
return cur.end
def starts_with(self, pref):
cur = self.root
for ch in pref:
if ch not in cur.children: return False
cur = cur.children[ch]
return True
Python for DSA — Beginner to Intermediate Page 7
6) Algorithmic Patterns (Reusable Templates)
6.1 Two Pointers
# Sorted array; find pair with sum == target
i, j = 0, len(a)-1
while i < j:
s = a[i] + a[j]
if s == target:
...
break
elif s < target: i += 1
else: j -= 1
6.2 Sliding Window
# Longest subarray with sum <= K (non-negative array)
best = 0; s = 0; l = 0
for r, x in enumerate(arr):
s += x
while s > K:
s -= arr[l]; l += 1
best = max(best, r-l+1)
6.3 Binary Search (Index)
def bs(a, x):
l, r = 0, len(a)-1
while l <= r:
m = (l+r)//2
if a[m] < x: l = m+1
elif a[m] > x: r = m-1
else: return m
return -1
6.4 Binary Search on Answer (Predicate)
# Smallest T such that feasible(T) is True; feasible is monotonic
def min_true(lo, hi, feasible):
while lo < hi:
mid = (lo+hi)//2
if feasible(mid): hi = mid
else: lo = mid+1
return lo
6.5 Prefix Sum
pref = [0]
for x in arr: pref.append(pref[-1]+x)
# sum of arr[l:r] = pref[r] - pref[l]
6.6 Recursion & Backtracking
ans = []
def backtrack(path, i):
if done_condition(i, path):
ans.append(path[:]); return
for choice in choices(i, path):
apply(choice, path)
backtrack(path, i+1)
undo(choice, path)
Python for DSA — Beginner to Intermediate Page 8
6.7 Greedy — Interval Scheduling
intervals.sort(key=lambda x: x[1]) # end time
count, end = 0, -10**18
for s,e in intervals:
if s >= end:
count += 1
end = e
6.8 Dynamic Programming
# Memoization (top-down)
from functools import lru_cache
@lru_cache(None)
def dp(i, j):
if base(i,j): return base_value
return min(dp(i+1,j)+cost1, dp(i,j+1)+cost2)
# Tabulation (Fibonacci)
n = 50
dp = [0]*(n+1)
dp[1] = 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
# 0/1 Knapsack (space-optimized)
def knapsack(W, wt, val):
dp = [0]*(W+1)
for w,v in zip(wt,val):
for cap in range(W, w-1, -1):
dp[cap] = max(dp[cap], dp[cap-w]+v)
return dp[W]
# LIS O(n log n) via patience
from bisect import bisect_left
tails = []
for x in arr:
i = bisect_left(tails, x)
if i == len(tails): tails.append(x)
else: tails[i] = x
length = len(tails)
Python for DSA — Beginner to Intermediate Page 9
7) Sorting & Searching Essentials
Built■in sort: arr.sort() / sorted(arr, key=..., reverse=...) — stable, O(n log n), very fast (Timsort).
arr.sort(key=lambda x: (x.score, -x.time))
Partial sorting: use heap or nlargest/nsmallest patterns.
Educational Mergesort
def mergesort(a):
if len(a)<=1: return a
m = len(a)//2
L = mergesort(a[:m]); R = mergesort(a[m:])
i=j=0; out=[]
while i<len(L) and j<len(R):
if L[i] <= R[j]: out.append(L[i]); i+=1
else: out.append(R[j]); j+=1
out.extend(L[i:]); out.extend(R[j:])
return out
8) Problem■Solving Playbook
• Parse: restate the problem in your own words.
• Check constraints: n up to? value ranges? I/O limits.
• Brute force baseline: ensure correctness first.
• Identify pattern: two pointers / window / BFS■DFS / BS / DP / greedy / DSU / trie.
• Prove feasibility: time/space complexity.
• Implement cleanly: helpers & early exits.
• Test edges: empty, one element, duplicates, negatives, extremes.
• Refactor: readability; remove debug prints.
Prefer iterative solutions when recursion depth may be large; avoid O(n^2) for n ■ 1e5; use lru_cache for
overlapping subproblems.
9) Roadmap — Beginner → Intermediate
Stage A (1–2 weeks): Basics
• Syntax: types, loops, functions, I/O.
• Arrays/strings, hash map/set, sorting & two pointers.
• Daily: 2 array + 1 string/hash problem.
Stage B (2–3 weeks): Core Techniques
• Sliding window, binary search (index & answer), prefix sums.
• Stacks/queues/monotonic, intervals & greedy.
• Daily: 1 window + 1 binary search + 1 greedy/stack.
Stage C (2 weeks): Graphs & Trees
• BFS/DFS, connected components, topological sort.
• Shortest paths (Dijkstra), tree traversals, LCA (intro).
• Daily: 1 BFS/DFS + 1 topo/shortest path.
Python for DSA — Beginner to Intermediate Page 10
Stage D (2–3 weeks): DP & Advanced
• 1D/2D DP, knapsack, LIS, partitions.
• Trie, DSU, bit tricks (as needed).
• Daily: 1 DP tabulation + 1 memoization problem.
10) Mini■Cheatsheet — Bite■size Reminders
• Two Sum: scan once; if target■x in seen, return; then seen.add(x).
• K most frequent: Counter + heap (nlargest) or bucket sort.
• Intervals merge: sort by start; merge if cur.start ≤ last.end.
• Cycle in directed graph: DFS colors (0/1/2).
• Binary search: watch bounds; update l/r correctly.
• Sliding window: expand r; while invalid→shrink l; track best.
• Dijkstra: heap of (dist,node); skip stale pops.
• Prefix sums: range queries via pref[r]-pref[l].
• DP recipe: state → transition → base → order; compress space.
End of guide — Good luck! Revisit patterns weekly and maintain your own summary page.
Python for DSA — Beginner to Intermediate Page 11
