DSA Revision & Prerequisite Guide

Python Foundations for "Top 130 LeetCode for MAANG"

A self-contained refresher covering Python data structures, control flow,

recursion, OOP for DSA, and essential built-in modules (deque, heapq,
math) — complete with time/space complexity tables, dry-run
walkthroughs, and fully tested, production-ready code for every topic.

Purpose: This guide is a self-contained refresher. You should not need any other resource to understand why Python behaves the
way it does under the hood, what each operation costs in time/space, and how to write idiomatic, interview-ready Python. Read it
once start-to-finish before Day 1, then use it as a reference whenever a problem leans on a specific structure.

How to use this guide: - Each topic follows a fixed structure: Concept → Complexity → Deep-Dive → Dry-Run → Code. - All code is
tested, complete, and copy-paste runnable — no placeholders. - Time complexities assume CPython 3.x (the standard implementation
used by LeetCode and in interviews).

Table of Contents

1. Python Built-in Data Structures & Time Complexities

1.1 Lists (Dynamic Arrays)
1.2 Tuples
1.3 Sets
1.4 Dictionaries

2. Control Flow & Looping Efficiency

2.1 List Comprehensions
2.2 Slicing
2.3 Generator Expressions

3. Functions & Scope

3.1 Recursion Basics & The Call Stack
3.2 Mutability vs. Immutability in Arguments

4. Object-Oriented Programming (OOP) for DSA

4.1 Classes & Custom Nodes
4.2 Pointers / References in Python

5. Built-in Modules for DSA

5.1 [Link]
5.2 heapq
5.3 math

6. Quick-Reference Cheat Sheet Table

Section 1: Python Built-in Data Structures & Time Complexities

1.1 Lists (Dynamic Arrays)

Core Concept & Use Case: A Python list is a dynamic array — a contiguous block of memory holding references (pointers) to
objects, not the objects themselves. Unlike a raw C array, it automatically resizes when it runs out of space. In DSA, lists are your
default tool for: stacks (using append / pop from the end), arrays for sliding window / two-pointer problems, and as the backing
structure for matrices (list of lists). Lists are ordered and mutable, and allow duplicate elements.

Time & Space Complexity:

Operation Average Case Worst Case Notes

Index access lst[i] O(1) O(1) Direct memory offset calculation

Append [Link](x) O(1) O(n) Amortized O(1); worst case triggers resize

Pop from end [Link]() O(1) O(1) No shifting required

Pop from front/middle [Link](0) O(n) O(n) All subsequent elements shift left

Insert [Link](i, x) O(n) O(n) Shifts elements to make room

Delete del lst[i] O(n) O(n) Shifts elements to fill gap

Search x in lst O(n) O(n) Linear scan, no ordering assumption

Slice lst[a:b] O(k) O(k) k = size of slice; creates a new list

Sort [Link]() O(n log n) O(n log n) Timsort (stable)

Space O(n) O(n) Plus some over-allocation overhead

Deep-Dive Sub-Topics:

a) Dynamic Resizing (Amortized O(1) append): CPython lists over-allocate memory. When a list of capacity n fills up, CPython
doesn't grow by 1 slot — it grows by a factor (roughly 1.125x plus a small constant, for larger lists). This means most append() calls just
write into existing free space (O(1)), and only occasionally (when capacity is exhausted) does Python perform an O(n) reallocation+copy.
Spread across many appends, the average ("amortized") cost per append is still O(1).

b) Why pop(0) is dangerous in interviews: Removing from the front of a list requires shifting every remaining element one position to
the left to keep the array contiguous — this is O(n). If you find yourself repeatedly popping from the front of a list in a loop (e.g.,
simulating a queue), you've accidentally written an O(n²) algorithm. Use [Link] instead (see Section 5.1).

c) Lists vs. Arrays ( array module) vs. NumPy arrays: A Python list stores pointers to objects (which can be of mixed types: [1,
"two", 3.0] is legal). This adds memory overhead and an extra pointer-dereference compared to a true contiguous array of fixed-size
integers (like in C, or NumPy's ndarray ). For LeetCode, plain lists are almost always sufficient and expected.

d) 2D Lists and the Shared-Reference Trap: A classic, dangerous bug: grid = [[0] * cols] * rows creates rows references to the
same inner list. Mutating one row mutates all of them! The correct idiom is grid = [[0] * cols for _ in range(rows)] , which creates a
new inner list per row via comprehension.

Dry-Run Example: How append triggers a resize

Imagine a list with capacity 4, currently holding [10, 20, 30, 40] (full).

Step 0: list = [10, 20, 30, 40] capacity = 4, length = 4 (FULL)

Step 1: Call [Link](50)
Step 2: CPython detects length == capacity → triggers resize
Step 3: New capacity calculated (e.g., 4 -> 8, via over-allocation formula)
Step 4: Allocate a NEW contiguous memory block of size 8
Step 5: Copy all 4 existing pointers (10, 20, 30, 40) into the new block — O(n)
Step 6: Write the new pointer (50) into the next free slot
Step 7: Free the old memory block of size 4
Result: list = [10, 20, 30, 40, 50] capacity = 8, length = 5

Next 3 appends (60, 70, 80) just write directly into existing
free slots (indices 5, 6, 7) → each is O(1), no resize needed.

This is exactly why append is usually instant but occasionally slow — and why we say "amortized O(1)."

Production-Ready Sample Code:

 # ============================================================
# LIST OPERATIONS — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. Using a list as a STACK (LIFO) — O(1) push/pop from the end ---
stack = []
[Link](1) # push: O(1)
[Link](2)
[Link](3)
top = [Link]() # pop: O(1) -> removes and returns 3
print(f"Stack after pop: {stack}, popped value: {top}") # [1, 2], 3

# --- 2. The 2D list shared-reference TRAP (and the fix) ---

rows, cols = 3, 3

# WRONG: all rows point to the SAME inner list object

buggy_grid = [[0] * cols] * rows
buggy_grid[0][0] = 99
print(f"BUGGY grid (all rows affected!): {buggy_grid}")
# Output: [[99, 0, 0], [99, 0, 0], [99, 0, 0]] <-- every row changed!

# CORRECT: comprehension creates a fresh list on each iteration

correct_grid = [[0] * cols for _ in range(rows)]
correct_grid[0][0] = 99
print(f"CORRECT grid (only row 0 affected): {correct_grid}")
# Output: [[99, 0, 0], [0, 0, 0], [0, 0, 0]]

# --- 3. Why pop(0) is an O(n) anti-pattern (demonstrated via cost) ---

import time

big_list = list(range(100_000))
start = time.perf_counter()
for _ in range(1000):
big_list.pop(0) # O(n) each time -> O(n*k) total. SLOW for large n.
elapsed = time.perf_counter() - start
print(f"1000x pop(0) on 100k list took: {elapsed:.4f}s (inefficient)")

# --- 4. Safe in-place removal while iterating (common bug source) ---
nums = [1, 2, 3, 4, 5, 6]

# WRONG: mutating a list while iterating over it skips elements

# for n in nums:
# if n % 2 == 0:
# [Link](n) # DON'T DO THIS — causes index skipping

# CORRECT: iterate over a copy, or build a new list

nums = [n for n in nums if n % 2 != 0] # O(n), no mutation-while-iterating bug
print(f"Odd numbers only: {nums}") # [1, 3, 5]

# --- 5. List as a fixed-size frequency/count array (very common in DSA) ---

# e.g., counting character frequency for a-z in O(1) space relative to input
text = "leetcode"
freq = [0] * 26 # one slot per lowercase letter
for ch in text:
freq[ord(ch) - ord('a')] += 1 # O(1) index math + O(1) update
print(f"Frequency array for 'leetcode': {freq}")

1.2 Tuples

Core Concept & Use Case: A tuple is an ordered, immutable sequence. Once created, it cannot be changed in size or content
(though it can contain mutable objects, like a list — more on that below). In DSA, tuples are used for: (1) returning multiple values
from a function, (2) representing fixed coordinate pairs like (row, col) in grid problems, (3) as dictionary keys or set elements
(since they're hashable, unlike lists), and (4) for memoization keys in dynamic programming ( memo[(i, j)] = result ).

Time & Space Complexity:

Operation Average Case Worst Case Notes

Index access tup[i] O(1) O(1) Same underlying contiguous storage as a list

Search x in tup O(n) O(n) Linear scan

Slice tup[a:b] O(k) O(k) k = slice size

Concatenation t1 + t2 O(n+m) O(n+m) Creates a new tuple

Hashing hash(tup) O(n) O(n) Needed when used as a dict key / set element

Space O(n) O(n) Generally more memory-efficient than a list of the same elements

Deep-Dive Sub-Topics:

a) Why tuples are hashable but lists aren't: A hash value must never change for the lifetime of an object if it's going to be used as a
dictionary key or set member (the hash determines its "bucket"). Since lists are mutable, Python deliberately disables __hash__ for them
( hash([1,2]) raises TypeError ) to prevent the corruption that would occur if you changed a list after using it as a key. Tuples are
immutable, so their hash is computed once and is safe to rely on — as long as every element inside the tuple is also hashable. A
tuple containing a list, e.g., (1, [2,3]) , is unhashable because its content isn't fully immutable.

b) Tuple Packing/Unpacking — the Pythonic multi-return pattern: return min_val, max_val actually packs both values into a tuple
implicitly. The caller can unpack it: lo, hi = get_bounds(arr) . This eliminates the need for wrapper classes purely for returning
pairs/triples of values, which is extremely common in two-pointer and interval problems.

c) Immutability is shallow, not deep: t = (1, [2, 3]) — you cannot do t[1] = "new" (TypeError), but you can do t[1].append(4) ,
because the tuple only guarantees that the reference at each position doesn't change, not that the object being pointed to is frozen.

Dry-Run Example: Tuple as a memoization key in DP

Problem: count paths from (0,0) to (i,j) in a grid using memoization.

memo = {} # empty dict

Call count_paths(2, 2):

Step 1: key = (2, 2)
Step 2: hash((2, 2)) computed using a combination of hash(2) and hash(2)
Step 3: Check if (2,2) in memo -> NOT FOUND
Step 4: Recursively compute count_paths(1,2) + count_paths(2,1)
... (sub-calls use their own tuple keys, e.g. (1,2), (2,1)) ...
Step 5: Once result computed (say, 6), store: memo[(2,2)] = 6
Step 6: Future calls to count_paths(2,2) -> key (2,2) -> O(1) hash lookup -> instant return

Because (2, 2) is immutable and hashable, it's a safe, fast dictionary key — a plain list [2, 2] could never be used this way.

Production-Ready Sample Code:

# ============================================================
# TUPLE OPERATIONS — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. Multi-value return (extremely common in DSA helper functions) ---

def find_min_max(arr):
"""Returns (min, max) as a tuple in a single O(n) pass."""
lo, hi = arr[0], arr[0]
for num in arr[1:]:
if num < lo:
lo = num
if num > hi:
hi = num
return lo, hi # implicitly packed into a tuple

minimum, maximum = find_min_max([5, 1, 9, -2, 7])

print(f"Min: {minimum}, Max: {maximum}") # Min: -2, Max: 9

# --- 2. Tuples as dictionary keys for 2D memoization (DP on grids) ---

def count_paths(i, j, memo=None):
"""Count paths to (i, j) from (0,0) moving only right/down."""
if memo is None:
memo = {}
if i == 0 or j == 0:
return 1
key = (i, j) # tuple used as a hashable composite key
if key in memo:
return memo[key] # O(1) average lookup
memo[key] = count_paths(i - 1, j, memo) + count_paths(i, j - 1, memo)
return memo[key]

print(f"Paths to (3,3): {count_paths(3, 3)}") # 20

# --- 3. Why a list can't be a dict key / set element (TypeError demo) ---
try:
bad_set = {[1, 2, 3]} # lists are unhashable
except TypeError as e:
print(f"Expected error using a list as a set element: {e}")

# The fix: convert to a tuple first

good_set = {tuple([1, 2, 3])}
print(f"Tuple version works fine in a set: {good_set}")

# --- 4. Tuple "immutability is shallow" gotcha ---

t = (1, [2, 3])
# t[0] = 99 # Would raise TypeError: 'tuple' object does not support item assignment
t[1].append(4) # Legal! We're mutating the LIST object the tuple points to.
print(f"Tuple after mutating its inner list: {t}") # (1, [2, 3, 4])

# --- 5. Named tuples: self-documenting alternative to plain tuples ---

from collections import namedtuple

Point = namedtuple("Point", ["row", "col"])

p = Point(row=2, col=5)
print(f"Named tuple access: [Link]={[Link]}, [Link]={[Link]}, as tuple={tuple(p)}")
# Useful in DSA for representing grid cells, intervals, or graph edges
# with readable field names instead of unlabeled p[0], p[1].

1.3 Sets
 Core Concept & Use Case: A set is an unordered collection of unique, hashable elements, backed by a hash table
(conceptually similar to a dictionary that only stores keys, no values). Sets are the go-to structure in DSA whenever you need: O(1)
membership testing ( x in my_set ), deduplication, or fast set algebra (union, intersection, difference) — e.g., finding common
elements between two arrays, detecting cycles in a graph via a "visited" set, or solving anagram/duplicate problems.

Time & Space Complexity:

Operation Average Case Worst Case Notes

Add [Link](x) O(1) O(n) Worst case on hash collisions / resize

Remove [Link](x) O(1) O(n) Same caveat

Membership x in s O(1) O(n) The headline reason to use a set

Union s1 \| s2 O(len(s1)+len(s2)) O(len(s1)+len(s2)) Must visit every element once

Intersection s1 & s2 O(min(len(s1),len(s2))) O(min(len(s1),len(s2))) Iterates the smaller set, checks membership in the larger

Difference s1 - s2 O(len(s1)) O(len(s1))

Space O(n) O(n) Plus hash-table overhead (typically more than a list for the same n items)

Deep-Dive Sub-Topics:

a) Hashing requirements: Every element placed into a set must implement __hash__ (and __eq__ , for collision resolution). This is
why ints, strings, and tuples (of hashables) work fine, but lists and dicts cannot be set members. When you define a custom class and
want its instances usable in a set, you must implement both __hash__ and __eq__ consistently — two objects that are == must have the
same hash.

b) Handling Key Collisions (Open Addressing): CPython's set/dict implementation uses open addressing, not chaining (unlike many
textbook hash table descriptions, e.g., Java's HashMap). When two elements hash to the same initial slot index (a collision), Python uses
a probing sequence — a deterministic formula based on the hash — to find the next candidate slot, checking each candidate until an
empty one is found. This keeps all entries within one contiguous table (good cache locality) but means that as the table fills up (the load
factor rises), probe sequences get longer, which is the underlying cause of worst-case O(n) behavior. CPython automatically resizes
(grows) the underlying table once it's about ⅔ full, to keep the average probe length low — this is what keeps the average case O(1).

c) Sets vs. frozensets: frozenset is the immutable, hashable sibling of set — useful when you need a set of sets (e.g., tracking visited
combinations) since a plain set cannot contain other mutable sets, but it can contain frozenset s.

d) Why iteration order is "arbitrary" (but consistent within a run): Set order depends on hash values and insertion history, not
insertion order. Never rely on it for correctness — only use a set when order genuinely doesn't matter to your algorithm.

Dry-Run Example: Detecting a collision and probing to the next slot

Assume a tiny hash table of size 8 (indices 0-7).

hash(10) % 8 = 2
hash(18) % 8 = 2 <-- COLLISION! Both map to index 2.

Insert 10:
Step 1: index = hash(10) % 8 = 2
Step 2: Slot 2 is empty -> place 10 at slot 2
Table: [_, _, 10, _, _, _, _, _]

Insert 18:
Step 1: index = hash(18) % 8 = 2
Step 2: Slot 2 is OCCUPIED (by 10) -> collision detected
Step 3: Apply probing sequence (perturbation formula) to compute next candidate, e.g., index 5
Step 4: Slot 5 is empty -> place 18 at slot 5
Table: [_, _, 10, _, _, 18, _, _]

Lookup 18 in set:
Step 1: index = hash(18) % 8 = 2
Step 2: Check slot 2 -> contains 10, not 18 -> NOT a match, keep probing
Step 3: Follow same probe sequence -> arrive at slot 5
Step 4: Slot 5 contains 18 -> MATCH -> return True
(This lookup took 2 probes instead of 1 — this is the "extra cost" of collisions)

Production-Ready Sample Code:

# ============================================================
# SET OPERATIONS — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. O(1) membership testing: the #1 reason to reach for a set ---
def contains_duplicate(nums):
"""LeetCode 217 pattern: O(n) time, O(n) space using a set."""
seen = set()
for num in nums:
if num in seen: # O(1) average lookup
return True
[Link](num) # O(1) average insert
return False

print(contains_duplicate([1, 2, 3, 1])) # True

print(contains_duplicate([1, 2, 3, 4])) # False

# --- 2. Set algebra for "find common / unique elements" problems ---
arr1 = {1, 2, 3, 4, 5}
arr2 = {4, 5, 6, 7, 8}

print(f"Union: {arr1 | arr2}") # {1,2,3,4,5,6,7,8}

print(f"Intersection: {arr1 & arr2}") # {4, 5}
print(f"Difference (arr1 - arr2): {arr1 - arr2}") # {1, 2, 3}
print(f"Symmetric difference: {arr1 ^ arr2}") # {1,2,3,6,7,8}

# --- 3. Custom objects in a set REQUIRE __hash__ and __eq__ ---

class Point:
"""A 2D point usable as a set element / dict key."""
def __init__(self, x, y):
self.x = x
self.y = y

def __eq__(self, other):

# Two points are equal if coordinates match
return isinstance(other, Point) and self.x == other.x and self.y == other.y

def __hash__(self):
# MUST be consistent with __eq__: equal objects -> equal hashes
return hash((self.x, self.y))

def __repr__(self):
return f"Point({self.x}, {self.y})"

points = {Point(1, 2), Point(3, 4), Point(1, 2)} # duplicate Point(1,2) collapses
print(f"Deduplicated points: {points}") # only 2 unique points remain

# --- 4. frozenset: hashable set, usable as a dict key or set-of-sets ---

visited_combinations = set()
combo1 = frozenset([1, 2, 3])
combo2 = frozenset([3, 2, 1]) # same elements, different insertion order
visited_combinations.add(combo1)
print(f"Is combo2 already visited? {combo2 in visited_combinations}") # True (order doesn't matter)

# --- 5. Using a set for graph traversal "visited" tracking (very common) ---
def has_cycle_undirected(n, edges):
"""Detects a cycle in an undirected graph using a visited set + DFS."""
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)

visited = set()

def dfs(node, parent):

[Link](node)
for neighbor in graph[node]:
if neighbor == parent:
continue # skip the edge we just came from
if neighbor in visited:
return True # found a back-edge -> cycle
if dfs(neighbor, node):
return True
return False

return dfs(0, -1)

print(f"Cycle present: {has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,0)])}") # True

print(f"Cycle present: {has_cycle_undirected(4, [(0,1),(1,2),(2,3)])}") # False

1.4 Dictionaries

Core Concept & Use Case: A dict is Python's hash map implementation: an unordered (well, insertion-ordered since 3.7+)
collection of key-value pairs, where keys must be hashable and unique. Dictionaries are arguably the single most important data
structure in interview DSA — used for: frequency counting, caching/memoization, adjacency lists for graphs, grouping (e.g.,
anagram grouping), and O(1) average lookups that turn brute-force O(n²) solutions into O(n) ones (the classic "Two Sum" pattern).

Time & Space Complexity:

 Operation Average Case Worst Case Notes

Get d[key] O(1) O(n) Worst case under heavy hash collisions (rare in practice)

Set d[key] = val O(1) O(n) Same caveat; amortized O(1) including resizes

Delete del d[key] O(1) O(n)

Membership key in d O(1) O(n)

Iteration (all items) O(n) O(n) Must visit every key-value pair

Space O(n) O(n) Higher constant factor than a list (stores hash, key, value per slot)

Deep-Dive Sub-Topics:

a) Hashing requirements (same as sets): Dictionary keys must be hashable — meaning immutable, with a stable __hash__ . This is
why dict s use strings, numbers, and tuples as keys constantly, but never lists or other dicts.

b) Handling Key Collisions: Identical mechanism to sets (Section 1.3b) — CPython dicts use open addressing with pseudo-random
probing. When two keys hash to the same slot, the second one to arrive is placed at a different slot determined by a probing formula
derived from the hash. Lookups follow the same probe sequence to relocate the correct key. This is also why a badly designed __hash__
(e.g., one that always returns the same value for every object) can degrade dict performance to O(n) per operation — every key collides
into the same bucket, and lookups become a linear scan.

c) Load Factor & Resizing: When a dict's table becomes roughly ⅔ (CPython's actual threshold) full, Python allocates a larger table
(typically 4x the current size for small dicts, 2x for larger ones) and re-hashes and re-inserts every existing key into the new table.
This single resize operation is O(n), but because it happens rarely (table size grows geometrically), the amortized cost per insertion
remains O(1) — exactly analogous to list resizing.

d) Insertion order guarantee (Python 3.7+): Since Python 3.7, dicts officially preserve insertion order as a language guarantee (it
was a CPython implementation detail in 3.6). This is leveraged in DSA for tasks like building an LRU cache (where you need to know "the
oldest" or "the most recently touched" key) — though [Link] (or dict + manual bookkeeping) is typically used
explicitly for that purpose.

e) [Link]() vs dict[key] vs defaultdict : d[key] raises KeyError if missing. [Link](key, default) returns a fallback without raising.
[Link](factory) auto-initializes missing keys using a factory function (e.g., int , list , set ) — eliminating repetitive "if
key not in d: d[key] = ..." boilerplate, which is extremely common in DSA frequency-counting and graph-building code.

Dry-Run Example: Frequency counting + hash collision handling

Goal: count character frequency in "aab" using a dict.

d = {}

Process 'a':
Step 1: hash('a') computed -> maps to bucket index, say 3
Step 2: Bucket 3 is empty -> insert key 'a' with value 1
Table (conceptual): {... slot3: ('a', 1) ...}

Process second 'a':

Step 1: hash('a') -> same bucket index 3 (deterministic hash)
Step 2: Bucket 3 occupied by 'a' itself -> key MATCHES (not a true collision,
it's the same key) -> increment existing value: d['a'] = 1 + 1 = 2

Process 'b':
Step 1: hash('b') -> maps to bucket index, say 3 (COLLISION with 'a's slot!)
Step 2: Bucket 3 occupied by 'a' -> keys differ -> probe to next candidate slot, say 7
Step 3: Slot 7 is empty -> insert key 'b' with value 1
Table (conceptual): {... slot3: ('a', 2), slot7: ('b', 1) ...}

Final result: {'a': 2, 'b': 1}

Production-Ready Sample Code:

# ============================================================
# DICTIONARY OPERATIONS — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. Classic Two Sum: O(n^2) brute force -> O(n) using a dict ---
def two_sum(nums, target):
"""Returns indices of two numbers that add up to target. O(n) time."""
seen = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) average lookup
return [seen[complement], i]
seen[num] = i # O(1) average insert
return [] # no solution found

print(f"Two Sum result: {two_sum([2, 7, 11, 15], 9)}") # [0, 1]

# --- 2. Frequency counting: manual dict vs defaultdict vs Counter ---

text = "leetcode"

# Manual approach (verbose, shows the underlying logic)

freq_manual = {}
for ch in text:
if ch not in freq_manual:
freq_manual[ch] = 0
freq_manual[ch] += 1

# defaultdict approach (cleaner, auto-initializes missing keys to 0)

from collections import defaultdict
freq_default = defaultdict(int)
for ch in text:
freq_default[ch] += 1 # no need to check existence first

# Counter approach (purpose-built, most idiomatic for this exact task)

from collections import Counter
freq_counter = Counter(text)

print(f"Manual: {freq_manual}")
print(f"defaultdict: {dict(freq_default)}")
print(f"Counter: {freq_counter}")
print(f"Most common 2: {freq_counter.most_common(2)}") # [('e', 3), ('l', 1)] (order may vary on ties)

# --- 3. [Link]() avoids KeyError, with a clean default ---

inventory = {"apples": 10, "bananas": 5}
print(f"Oranges in stock: {[Link]('oranges', 0)}") # 0, no crash

# --- 4. Grouping pattern: Group Anagrams (LeetCode classic) ---

def group_anagrams(words):
"""Groups words that are anagrams of each other. O(n * k log k)."""
groups = defaultdict(list)
for word in words:
key = "".join(sorted(word)) # sorted letters = canonical anagram key
groups[key].append(word)
return list([Link]())

print(f"Anagram groups: {group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat'])}")

# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

# --- 5. Building a graph as an adjacency list using a dict ---

def build_graph(edges):
"""Builds an undirected adjacency-list graph from an edge list."""
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
return graph

g = build_graph([(0, 1), (1, 2), (0, 2)])

print(f"Adjacency list: {dict(g)}") # {0: [1, 2], 1: [0, 2], 2: [1, 0]}

# --- 6. Why a poorly-designed __hash__ degrades performance to O(n) ---

class BadHash:
"""Demonstrates worst-case dict behavior: every instance collides."""
def __init__(self, val):
[Link] = val
def __eq__(self, other):
return isinstance(other, BadHash) and [Link] == [Link]
def __hash__(self):
return 1 # ALWAYS the same bucket -> every lookup becomes O(n) linear probing

bad_dict = {BadHash(i): i for i in range(5)}

print(f"BadHash dict still works correctly, just slowly: {len(bad_dict)} entries")
# Correctness is preserved (probing + __eq__ resolves collisions),
# but performance degrades from O(1) to O(n) per operation since
# every key lands in the same initial bucket.
Section 2: Control Flow & Looping Efficiency

2.1 List Comprehensions

Core Concept & Use Case: A list comprehension is a syntactic construct — [expr for item in iterable if condition] — that builds a
new list in a single, optimized expression, replacing the classic "create empty list, loop, append" pattern. In DSA, comprehensions are
used constantly for: filtering arrays, transforming inputs (e.g., converting a string to a list of ints), building lookup tables, and
flattening nested structures — all while being faster than equivalent explicit loops due to internal bytecode-level optimization (the
loop body avoids the overhead of repeated attribute lookups for .append ).

Time & Space Complexity:

Average Worst
Operation Notes
Case Case

Simple comprehension [x for x in lst] O(n) O(n) One pass over the iterable

Filtered comprehension [x for x in lst if

O(n) O(n) Still one pass; cond check is O(1) typically
cond]

Nested comprehension (2 loops) O(n*m) O(n*m) One pass per combination of outer/inner

k = number of elements that survive the filter; entire result materializes in

Space O(k) O(k)
memory

Deep-Dive Sub-Topics:

a) Why comprehensions are faster than equivalent for-loops: At the bytecode level, a list comprehension compiles to a specialized
code object that uses the LIST_APPEND opcode directly within a dedicated loop frame, whereas a manual loop using [Link](x) must
repeatedly resolve the .append method via attribute lookup on every iteration. This avoids dictionary lookups for method resolution on
each loop iteration, giving a meaningful (though not asymptotic) constant-factor speedup — typically 20-30% faster in practice for the
same logical work.

b) Comprehensions vs. map() / filter() : [f(x) for x in lst] and list(map(f, lst)) produce the same result and have the same O(n)
complexity. Comprehensions are generally preferred in modern Python for readability when the transformation logic is more than a
single existing function reference.

c) Nested comprehensions — readability vs. cleverness trade-off: [x for row in matrix for x in row] flattens a 2D list in one line
(equivalent to a nested for-loop: outer for row in matrix , inner for x in row ). While powerful, comprehensions with more than 2 levels
of nesting or multiple conditions become hard to read — in those cases, an explicit loop is the better interview answer (clarity matters in
a live coding interview).

d) Critical Gotcha — list comprehensions are NOT lazy: Unlike generator expressions (Section 2.3), a list comprehension
immediately computes and stores every element in memory. [x**2 for x in range(10**8)] will attempt to allocate a list of 100
million integers right away — a common source of MemoryError in coding interviews when a candidate should have used a generator
instead.

Dry-Run Example: Filtering and squaring even numbers

Input: nums = [1, 2, 3, 4, 5, 6]

Expression: [x**2 for x in nums if x % 2 == 0]

Step 1: x = 1 -> 1 % 2 == 0? NO -> skip

Step 2: x = 2 -> 2 % 2 == 0? YES -> compute 2**2 = 4 -> append 4 to result
Step 3: x = 3 -> 3 % 2 == 0? NO -> skip
Step 4: x = 4 -> 4 % 2 == 0? YES -> compute 4**2 = 16 -> append 16 to result
Step 5: x = 5 -> 5 % 2 == 0? NO -> skip
Step 6: x = 6 -> 6 % 2 == 0? YES -> compute 6**2 = 36 -> append 36 to result
Final result list: [4, 16, 36]

Production-Ready Sample Code:

 # ============================================================
# LIST COMPREHENSIONS — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. Basic filter + transform (the canonical use case) ---

nums = [1, 2, 3, 4, 5, 6]
even_squares = [x**2 for x in nums if x % 2 == 0]
print(f"Even squares: {even_squares}") # [4, 16, 36]

# --- 2. Parsing input: string -> list of ints (extremely common in DSA setup) ---
raw_input_line = "5 3 8 1 9"
parsed = [int(x) for x in raw_input_line.split()]
print(f"Parsed ints: {parsed}") # [5, 3, 8, 1, 9]

# --- 3. Flattening a 2D matrix in one line ---

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat = [val for row in matrix for val in row]
print(f"Flattened: {flat}") # [1, 2, 3, 4, 5, 6, 7, 8, 9]

# --- 4. Building a fixed-size lookup/initialization structure ---

# Common DP pattern: initialize a 2D DP table with comprehension (avoids the
# shared-reference bug from Section 1.1d, since each row is freshly created)
rows, cols = 3, 4
dp = [[0 for _ in range(cols)] for _ in range(rows)]
dp[1][2] = 99
print(f"DP table (only one cell modified): {dp}")

# --- 5. Conditional expression INSIDE a comprehension (ternary, not a filter) ---

# Note the syntax difference: this transforms every element (no skipping),
# whereas `if cond` at the END filters which elements are included at all.
nums2 = [1, 2, 3, 4, 5]
labels = ["even" if x % 2 == 0 else "odd" for x in nums2]
print(f"Labels: {labels}") # ['odd', 'even', 'odd', 'even', 'odd']

# --- 6. The MemoryError trap: comprehension vs. generator for huge ranges ---
# DON'T do this for large n if you only need to iterate once:
# huge_list = [x * 2 for x in range(10**9)] # tries to allocate ~8GB+ immediately
# DO this instead if you just need to iterate (see Section 2.3 for generators):
huge_gen = (x * 2 for x in range(10**9)) # O(1) memory, lazy
print(f"Generator created lazily, first value: {next(huge_gen)}") # 0

2.2 Slicing

Core Concept & Use Case: Slicing ( seq[start:stop:step] ) extracts a sub-sequence from a list, string, or tuple without manually
writing a loop. In DSA, slicing is heavily used for: extracting sub-arrays/windows, reversing sequences ( seq[::-1] ), skipping
elements ( seq[::2] ), and implementing divide-and-conquer algorithms (e.g., merge sort splits an array via arr[:mid] and arr[mid:] ).

Time & Space Complexity:

Operation Average Case Worst Case Notes

Slice seq[a:b] O(b-a) O(b-a) Always creates a new object; cost is proportional to slice length, not original length

Full copy seq[:] O(n) O(n) Shallow copy of the entire sequence

Reverse seq[::-1] O(n) O(n) Creates a new, fully reversed sequence

Step slice seq[::k] O(n/k) O(n/k)

Space O(b-a) O(b-a) New memory allocated; original is untouched

Deep-Dive Sub-Topics:

a) Slicing always creates a new object (shallow copy): b = a[1:3] does not create a view into a (unlike NumPy arrays, which do
support views!). Plain Python lists/tuples/strings always copy the relevant elements into a brand-new object when sliced. This is
important for complexity analysis: repeatedly slicing a large list inside a loop (e.g., arr[i:] inside a for i in range(n) loop) silently
introduces an O(n²) total cost, because each slice itself costs O(n).

b) Out-of-bounds slicing never raises an error: Unlike direct indexing ( lst[100] raises IndexError on a 5-element list), slicing
gracefully clamps to valid bounds: lst[2:100] on a 5-element list simply returns everything from index 2 onward. This is a frequent
source of silent bugs — code that should crash on bad input instead returns a partial/empty result.

c) Negative indices and steps: seq[-3:] grabs the last 3 elements. seq[::-1] reverses the entire sequence (start/stop omitted = full
range, step = -1 = backward). seq[::2] grabs every second element starting from index 0.

d) Slice assignment (mutating part of a list in place): lst[1:3] = [99, 100] replaces elements at indices 1 and 2 — and the
replacement doesn't even need to be the same length, enabling in-place insertion/deletion: lst[1:1] = [99] inserts 99 at index 1 without
removing anything.

Dry-Run Example: Reversing via slicing vs. two-pointer swap

Input: arr = [1, 2, 3, 4, 5]
Operation: arr[::-1]

Step 1:
start is omitted -> defaults to the last valid index (since step is negative)
Step 2:
stop is omitted -> defaults to "before the first index" (since step is negative)
Step 3:
step = -1 -> traverse backward, one element at a time
Step 4:
Build NEW list by visiting indices: 4, 3, 2, 1, 0
-> collect arr[4]=5, arr[3]=4, arr[2]=3, arr[1]=2, arr[0]=1
Result (new list): [5, 4, 3, 2, 1]
Original 'arr' is UNCHANGED: [1, 2, 3, 4, 5] <- slicing never mutates the source

Production-Ready Sample Code:

# ============================================================
# SLICING — Common DSA Idioms & Edge Cases
# ============================================================

arr = [10, 20, 30, 40, 50]

# --- 1. Basic sub-array extraction ---

print(f"Middle elements arr[1:4]: {arr[1:4]}") # [20, 30, 40]

# --- 2. Reversal without mutating the original (common in palindrome checks) ---
reversed_arr = arr[::-1]
print(f"Reversed copy: {reversed_arr}, original unchanged: {arr}")

# --- 3. Every other element (step slicing) ---

print(f"Every 2nd element: {arr[::2]}") # [10, 30, 50]

# --- 4. Last K elements (common "sliding window from the end" pattern) ---
k = 2
print(f"Last {k} elements: {arr[-k:]}") # [40, 50]

# --- 5. Out-of-bounds slicing does NOT raise an error (gotcha demo) ---
print(f"arr[2:100] (out of bounds, no crash): {arr[2:100]}") # [30, 40, 50]
print(f"arr[100:200] (way out of bounds): {arr[100:200]}") # [] (empty, not an error)

# --- 6. Slice assignment: insert without removing anything ---

nums = [1, 2, 3, 7, 8]
nums[3:3] = [4, 5, 6] # insert 4,5,6 at index 3, shifting the rest right
print(f"After slice-insert: {nums}") # [1, 2, 3, 4, 5, 6, 7, 8]

# --- 7. Slice assignment: delete a range (equivalent to del nums[a:b]) ---

nums[3:6] = []
print(f"After slice-delete: {nums}") # [1, 2, 3, 7, 8]

# --- 8. Merge sort split — classic divide & conquer use of slicing ---
def merge_sort(arr):
"""O(n log n) merge sort using slicing to split the array."""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # O(mid) to create this slice
right = merge_sort(arr[mid:]) # O(n - mid) to create this slice
return _merge(left, right)

def _merge(left, right):

result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return result

print(f"Merge sorted: {merge_sort([5, 2, 9, 1, 5, 6])}") # [1, 2, 5, 5, 6, 9]

# --- 9. THE O(n^2) TRAP: repeated slicing inside a loop ---

# This looks like an O(n) loop but is secretly O(n^2) because each
# slice arr[i:] itself costs O(n - i):
def bad_sum_of_suffixes(arr):
total = 0
for i in range(len(arr)):
total += sum(arr[i:]) # arr[i:] is O(n-i) to CREATE, then sum() is another O(n-i)
return total
# A better approach would precompute suffix sums in a single O(n) pass.
print(f"(Inefficient but correct) suffix sum total: {bad_sum_of_suffixes([1,2,3,4])}")

2.3 Generator Expressions

Core Concept & Use Case: A generator expression — (expr for item in iterable if cond) — looks like a list comprehension but
uses parentheses instead of brackets, and crucially, it produces values lazily, one at a time, rather than computing the entire
sequence upfront. In DSA, generators matter whenever you need to: process huge or infinite sequences without exhausting memory,
short-circuit early (e.g., any() / all() checks that can stop at the first match), or chain transformations without materializing
intermediate lists.

Time & Space Complexity:

 Average Worst
Operation Notes
Case Case

Creation (x for x in it) O(1) O(1) No computation happens at creation time

Full consumption (e.g. via list() ) O(n) O(n) Same total time as a list comprehension over n items

Early termination (e.g. next() once, or any() k = elements consumed before stopping; this is the main advantage over
O(k) O(n)
short-circuit) comprehensions

Only the current item + generator state is held in memory — this is the
Space O(1) O(1)
headline benefit

Deep-Dive Sub-Topics:

a) Lazy evaluation — the core mechanism: A generator expression doesn't run any of its code when created. It returns a generator
object that implements the iterator protocol ( __next__ ). Each call to next(gen) resumes execution exactly where it left off, computes the
next single value, and pauses again. This is fundamentally different from a list comprehension, which runs the entire loop to completion
immediately and returns a fully-populated list.

b) One-shot / single-use limitation: A generator can only be iterated once. After it's exhausted (raises StopIteration internally, which
for loops handle automatically), trying to iterate again yields nothing — there's no data left, and no way to "rewind." This trips up many
beginners who try to reuse a generator like a list. If you need to iterate multiple times, you must either recreate the generator or
materialize it into a list.

c) Generators + short-circuiting built-ins ( any , all , sum , next ) — a huge interview pattern: any(x > 100 for x in huge_list)
stops checking the instant it finds a value greater than 100 — it does NOT build a full list of booleans first. Compare this to the
(wasteful) any([x > 100 for x in huge_list]) , which first builds the entire boolean list via the inner comprehension, then checks it.
Dropping the brackets for parentheses here is a one-character change with a real algorithmic benefit when an early match is likely.

d) Generator functions ( yield ) vs. generator expressions: A generator expression is the inline (x for x in y) syntax. A generator
function uses yield inside a regular def block to achieve the same lazy, resumable behavior but with arbitrarily complex logic (loops,
branching, recursion) — useful for things like lazily yielding all valid next-states in a BFS/backtracking search without precomputing
them all.

Dry-Run Example: Lazy evaluation step-by-step with next()

gen = (x * x for x in [1, 2, 3])

Step 1: gen is created. NO computation has happened yet. Internal pointer at index 0.

Call next(gen):
Step 2: Resume execution -> fetch x = 1 from the source iterable
Step 3: Compute x * x = 1
Step 4: PAUSE execution, return 1 to caller
(Internal state: paused right after yielding for x=1; index advances)

Call next(gen) again:

Step 5: RESUME from paused point -> fetch x = 2
Step 6: Compute x * x = 4
Step 7: PAUSE, return 4

Call next(gen) again:

Step 8: RESUME -> fetch x = 3
Step 9: Compute x * x = 9
Step 10: PAUSE, return 9

Call next(gen) a 4th time:

Step 11: RESUME -> source iterable is exhausted (no more elements)
Step 12: Raise StopIteration internally (a `for` loop would just stop silently here)

Total memory used throughout: O(1) — never more than ONE squared value existed at a time.

Production-Ready Sample Code:

# ============================================================
# GENERATOR EXPRESSIONS — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. Basic generator creation and manual consumption with next() ---
squares_gen = (x * x for x in [1, 2, 3])
print(next(squares_gen)) # 1
print(next(squares_gen)) # 4
print(next(squares_gen)) # 9
try:
next(squares_gen) # source exhausted
except StopIteration:
print("Generator exhausted, as expected.")

# --- 2. Memory comparison: list comprehension vs generator for a large range ---
import sys

list_version = [x for x in range(100_000)]

gen_version = (x for x in range(100_000))
print(f"List size in memory: {[Link](list_version):,} bytes")
print(f"Generator size in memory: {[Link](gen_version):,} bytes")
# The generator's size stays tiny and CONSTANT regardless of range size,
# while the list's size grows linearly with the number of elements.

# --- 3. Short-circuiting with any()/all() — the killer interview use case ---
def has_pair_with_sum(nums, target):
"""Checks if any pair sums to target, stopping at the FIRST match found."""
seen = set()
# any() short-circuits the moment the generator yields a True
return any((target - num) in seen or [Link](num) for num in nums)
# Note: [Link](num) returns None (falsy), so the `or` correctly
# falls through to evaluate the next iteration's condition each time.

print(has_pair_with_sum([1, 2, 3, 9], 5)) # True (2 + 3)

# --- 4. Generator function (using yield) for lazy Fibonacci sequence ---
def fibonacci_gen(limit):
"""Lazily yields Fibonacci numbers up to `limit` count. O(1) space (excl. output)."""
a, b = 0, 1
count = 0
while count < limit:
yield a
a, b = b, a + b
count += 1

# Only computes values as they're requested in the loop below:

fib_values = list(fibonacci_gen(8))
print(f"First 8 Fibonacci numbers: {fib_values}") # [0, 1, 1, 2, 3, 5, 8, 13]

# --- 5. Chaining generators without materializing intermediate lists ---

data = range(1, 21)
# Pipeline: filter evens -> square them -> take only those > 50
pipeline = (sq for sq in (x * x for x in data if x % 2 == 0) if sq > 50)
print(f"Pipeline result: {list(pipeline)}") # [64, 100, 144, 196, 256, 324, 400]
# At no point does this materialize a full intermediate list — each value
# flows through the entire pipeline one at a time.

# --- 6. THE ONE-SHOT TRAP: generators can't be reused ---

gen = (x for x in range(3))
first_pass = list(gen)
second_pass = list(gen) # gen is already exhausted!
print(f"First pass: {first_pass}, second pass (empty!): {second_pass}")
# [0, 1, 2], [] <- this is a very common bug source for beginners
Section 3: Functions & Scope

3.1 Recursion Basics & The Call Stack

Core Concept & Use Case: Recursion is when a function calls itself to solve smaller instances of the same problem, relying on a
base case to stop, and a recursive case that makes progress toward that base case. In DSA, recursion is fundamental to: tree and
graph traversal (DFS), divide-and-conquer (merge sort, quick sort, binary search), backtracking (permutations, combinations, N-
Queens), and dynamic programming (top-down/memoized solutions). Understanding the call stack is essential because it explains
both why recursion works and why it can fail (stack overflow) or be inefficient (without memoization).

Time & Space Complexity:

Operation Average Case Worst Case Notes

Single recursive call O(1) per call (excl. subcalls) O(1) per call The overhead of pushing/popping one stack frame

Linear recursion (e.g. factorial, sum of list) O(n) time O(n) time n recursive calls, one per element

Linear recursion call stack O(n) space O(n) space n frames sit on the stack simultaneously at max depth

Binary/tree recursion (e.g. naive Fibonacci) O(2^n) time O(2^n) time Exponential blow-up without memoization

Binary/tree recursion call stack O(n) space O(n) space Stack depth = longest single path, NOT total calls

Divide & conquer (e.g. merge sort) O(log n) stack depth O(log n) stack depth Each level halves the problem size

Deep-Dive Sub-Topics:

a) What actually happens on each function call — the Stack Frame: Every time a function is called (recursive or not), Python
pushes a new stack frame onto the call stack. This frame stores: the function's local variables, its parameters, and a "return address"
(where to resume execution in the caller once this call finishes). When the function returns, its frame is popped off the stack, and control
resumes in the caller's frame, exactly where it left off.

b) Why deep recursion crashes: RecursionError / Stack Overflow: Python's default recursion limit is 1000 frames
( [Link]() ). Each unfinished recursive call keeps its frame alive on the stack (waiting for its recursive sub-call to return),
so a recursion depth of n requires O(n) stack frames simultaneously in memory. Exceeding the limit raises RecursionError: maximum
recursion depth exceeded . This is exactly why naive recursive solutions to problems with large inputs (e.g., a linked list of 100,000 nodes
processed recursively) can crash, while an equivalent iterative solution (using an explicit loop, O(1) extra space) would not.

c) Tree recursion and the "stack depth ≠ total calls" distinction: Naive recursive Fibonacci fib(n) = fib(n-1) + fib(n-2) makes an
exponential number of total calls (O(2^n)) — but the maximum stack depth at any instant is only O(n), because Python fully resolves
the fib(n-1) branch (popping all its frames) before even starting the fib(n-2) branch. This distinction — "total work" vs. "peak
memory" — is a frequent point of confusion and a common interview clarifying question.

d) Memoization — turning exponential into polynomial: Caching previously-computed results (e.g., with a dict or
functools.lru_cache ) avoids recomputing the same sub-problem multiple times, transforming naive O(2^n) recursive Fibonacci into O(n)
by ensuring each unique sub-problem is only solved once.

e) Tail recursion — and why Python does NOT optimize it: Some languages (Scheme, Scala) optimize "tail-recursive" calls (where
the recursive call is the very last operation) to reuse the same stack frame instead of pushing a new one, achieving O(1) stack space.
CPython deliberately does not implement this optimization — every recursive call always uses a new frame, regardless of where it
appears in the function. This means even a "tail recursive-style" Python function will still hit RecursionError on deep inputs; converting
to an explicit iterative loop is the only reliable fix in Python.

Dry-Run Example: The call stack during factorial(4)

def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)

Call factorial(4):

CALLING DOWN (stack grows):

Frame 1: factorial(4) called. n=4. Not base case. Needs factorial(3) to continue.
[STACK: factorial(4)]
Frame 2: factorial(3) called. n=3. Not base case. Needs factorial(2) to continue.
[STACK: factorial(4), factorial(3)]
Frame 3: factorial(2) called. n=2. Not base case. Needs factorial(1) to continue.
[STACK: factorial(4), factorial(3), factorial(2)]
Frame 4: factorial(1) called. n=1. BASE CASE HIT -> returns 1 immediately.
[STACK: factorial(4), factorial(3), factorial(2), factorial(1)] <- peak depth = 4

RETURNING UP (stack shrinks, each frame completes its pending multiplication):

Frame 4 returns 1 to Frame 3. [STACK pops factorial(1)]
Frame 3 computes 2 * 1 = 2, returns 2 to Frame 2. [STACK pops factorial(2)]
Frame 2 computes 3 * 2 = 6, returns 6 to Frame 1. [STACK pops factorial(3)]
Frame 1 computes 4 * 6 = 24, returns 24 to the original caller. [STACK pops factorial(4)]

Final result: 24. Peak stack depth was 4 (proportional to n).

Production-Ready Sample Code:

# ============================================================
# RECURSION & THE CALL STACK — Common DSA Idioms & Edge Cases
# ============================================================

import sys

# --- 1. Basic linear recursion: factorial ---

def factorial(n):
"""O(n) time, O(n) space (call stack depth)."""
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case

print(f"5! = {factorial(5)}") # 120

# --- 2. Demonstrating RecursionError on deep input ---

print(f"Default recursion limit: {[Link]()}")

def count_down_recursive(n):
if n <= 0:
return 0
return 1 + count_down_recursive(n - 1)

try:
count_down_recursive(10_000) # exceeds default limit of 1000
except RecursionError as e:
print(f"Crashed as expected on deep recursion: {e}")

# --- 3. The ITERATIVE fix: same logic, O(1) extra space, no crash risk ---
def count_down_iterative(n):
"""Equivalent result, but uses a loop instead of the call stack."""
total = 0
while n > 0:
total += 1
n -= 1
return total

print(f"Iterative version handles large n safely: {count_down_iterative(10_000)}")

# --- 4. Naive exponential recursion vs memoized O(n) recursion ---

def fib_naive(n):
"""O(2^n) time -- recomputes the same sub-problems repeatedly."""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)

def fib_memo(n, memo=None):

"""O(n) time, O(n) space -- each sub-problem solved exactly once."""
if memo is None:
memo = {}
if n <= 1:
return n
if n in memo: # cache hit -> O(1) instead of re-recursing
return memo[n]
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]

print(f"fib_naive(20) = {fib_naive(20)}") # 6765 (slow for larger n)

print(f"fib_memo(50) = {fib_memo(50)}") # 12586269025 (instant, naive would take forever)

# --- 5. functools.lru_cache: the idiomatic, zero-boilerplate memoization ---

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n - 1) + fib_cached(n - 2)

print(f"fib_cached(50) = {fib_cached(50)}") # 12586269025

 # --- 6. Tree recursion: peak stack depth vs. total call count ---
call_counter = [0] # mutable container to track calls across recursive invocations

def fib_count_calls(n):
call_counter[0] += 1
if n <= 1:
return n
return fib_count_calls(n - 1) + fib_count_calls(n - 2)

fib_count_calls(15)
print(f"fib(15) made {call_counter[0]} total calls, "
f"but peak stack depth never exceeded ~15.")

# --- 7. DFS on a tree: the canonical recursive DSA pattern ---

class TreeNode:
def __init__(self, val, left=None, right=None):
[Link] = val
[Link] = left
[Link] = right

def max_depth(root):
"""Recursive DFS: O(n) time, O(h) space where h = tree height."""
if root is None: # base case: empty tree has depth 0
return 0
left_depth = max_depth([Link])
right_depth = max_depth([Link])
return 1 + max(left_depth, right_depth)

# Build a small tree: 1

# / \
# 2 3
# /
# 4
tree = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(f"Max depth of sample tree: {max_depth(tree)}") # 3

3.2 Mutability vs. Immutability in Function Arguments

Core Concept & Use Case: Python passes arguments by "assignment" (sometimes called "pass-by-object-reference") — neither
strictly pass-by-value nor pass-by-reference as those terms are used in C++/Java. What this means in practice: the function parameter
becomes a new local name bound to the same object the caller passed in. Whether changes inside the function are visible to the caller
depends entirely on whether the object itself is mutable (lists, dicts, sets, custom objects) or immutable (ints, strings, tuples,
frozensets). This single concept is responsible for some of the most common and confusing bugs in interview coding — e.g., a "helper
function" that's supposed to modify a list in place but silently doesn't, or accidental shared mutation across recursive calls.

Time & Space Complexity:

Scenario Time Cost Space Cost Notes

Passing any argument (mutable or Only a reference/pointer is copied, never the underlying
O(1) O(1)
immutable) data

Reassigning a parameter inside a Rebinds the local name only; caller's variable is
O(1) O(1)
function ( x = new_value ) unaffected

Mutating an object in place Depends on the operation (see Depends on the The mutation is visible to the caller because both
( [Link](x) , d[k]=v ) Sections 1.1–1.4) operation names point to the same object

Defensive copy before mutating Common technique to avoid mutating the caller's
O(n) O(n)
( new_lst = [Link]() ) original data

Deep-Dive Sub-Topics:

a) The core mental model: "names are labels on boxes, not boxes themselves." When you write x = [1, 2, 3] , think of it as: a list
object exists in memory, and the name x is a label pointing at it. When you call f(x) , the parameter inside f (say, called lst ) becomes
a second label pointing at the exact same object. There is only ever one list in memory at this point — two names referring to it.

b) Reassignment vs. mutation — the critical distinction: - Reassignment ( lst = [9, 9, 9] inside the function) makes the local
name lst point to a brand new object. The caller's original variable is completely unaffected, because the caller's label was never
touched — only the function's local label was redirected. - Mutation ( [Link](9) , lst[0] = 9 , [Link]() ) modifies the existing
object in place. Since the caller's variable still points to that same object, the caller will see the change. This is the single most
important distinction in this entire topic — interviewers frequently probe exactly this with a "what does this print?" style question.

c) Why immutable arguments "feel" like pass-by-value: Since you cannot mutate an int, string, or tuple in place at all (there is no
.append() or item-assignment for them), the only thing you can ever do with an immutable argument inside a function is reassign the
local name — which, per (b), never affects the caller. This is why integers and strings appear to be passed "by value" even though the
actual mechanism (binding a new local name to the same object) is identical for both mutable and immutable types.

d) The classic mutable default argument trap: def f(lst=[]): — the default empty list is created exactly once, at function
definition time, not on every call. If the function mutates this default (e.g., [Link](x) ) and the caller relies on the default (never
passes their own list), that same single list object persists and accumulates state across calls, which is almost never the intended
behavior. The standard fix is def f(lst=None): if lst is None: lst = [] .

e) Defensive copying — protecting the caller's data: If a function needs to sort, filter, or otherwise modify a list internally without
affecting the caller's original list, it must explicitly create a copy first ( [Link]() , lst[:] , or list(lst) ) rather than mutating the
parameter directly.

Dry-Run Example: Mutation vs. Reassignment side-by-side

caller_list = [1, 2, 3] # Object A created. caller_list -> Object A

--- Scenario 1: function MUTATES the parameter ---

def add_item(lst):
[Link](99) # mutates Object A in place (lst and caller_list both point to it)

add_item(caller_list)
Step 1: add_item is called. Parameter `lst` is bound to Object A (same object as caller_list).
Step 2: [Link](99) modifies Object A directly. No new object created.
Step 3: Function returns. Local name `lst` is discarded, but Object A retains the change.
print(caller_list) -> [1, 2, 3, 99] <-- caller SEES the change

--- Scenario 2: function REASSIGNS the parameter ---

caller_list2 = [1, 2, 3] # Object B created. caller_list2 -> Object B

def replace_list(lst):
lst = [9, 9, 9] # creates a NEW Object C; lst now points to C. Object B untouched.

replace_list(caller_list2)
Step 1: replace_list is called. Parameter `lst` is bound to Object B (same as caller_list2).
Step 2: lst = [9, 9, 9] creates Object C and rebinds the LOCAL name `lst` to it.
Object B is completely unaffected; caller_list2 still points to Object B.
Step 3: Function returns. Local name `lst` (pointing to C) is discarded entirely.
print(caller_list2) -> [1, 2, 3] <-- caller does NOT see any change

Production-Ready Sample Code:

# ============================================================
# MUTABILITY vs IMMUTABILITY IN ARGUMENTS — Idioms & Edge Cases
# ============================================================

# --- 1. Mutation IS visible to the caller (lists, dicts, sets, objects) ---
def add_item(lst):
[Link](99) # in-place mutation

caller_list = [1, 2, 3]
add_item(caller_list)
print(f"After mutation, caller sees: {caller_list}") # [1, 2, 3, 99]

# --- 2. Reassignment is NOT visible to the caller (rebinds local name only) ---
def replace_list(lst):
lst = [9, 9, 9] # local rebind, does NOT affect the caller's object

caller_list2 = [1, 2, 3]
replace_list(caller_list2)
print(f"After reassignment attempt, caller still sees: {caller_list2}") # [1, 2, 3]

# --- 3. Immutable arguments: reassignment is the ONLY option, so it "looks" like pass-by-value ---
def try_increment(n):
n = n + 1 # creates a new int object; local rebind only
return n

x = 5
result = try_increment(x)
print(f"Original x unchanged: {x}, returned new value: {result}") # 5, 6

# --- 4. THE MUTABLE DEFAULT ARGUMENT TRAP (a notorious real-world bug) ---
def buggy_append(item, target_list=[]): # DANGER: default list created ONCE, ever
target_list.append(item)
return target_list

print(buggy_append(1)) # [1] <- looks fine so far...

print(buggy_append(2)) # [1, 2] <- but the SAME default list persists!
print(buggy_append(3)) # [1, 2, 3] <- accumulating across unrelated calls!

# THE FIX: use None as a sentinel, create a fresh list inside the function
def safe_append(item, target_list=None):
if target_list is None:
target_list = [] # a NEW list every call where the default is used
target_list.append(item)
return target_list

print(safe_append(1)) # [1]
print(safe_append(2)) # [2] <- correctly independent this time

# --- 5. Defensive copying: protecting the caller's original data ---

def sorted_without_mutating(lst):
"""Returns a sorted COPY, leaving the caller's original list untouched."""
new_lst = [Link]() # O(n) defensive copy
new_lst.sort() # mutate the COPY, not the original
return new_lst

original = [3, 1, 2]
sorted_version = sorted_without_mutating(original)
print(f"Original (unchanged): {original}, sorted copy: {sorted_version}")
# [3, 1, 2], [1, 2, 3]

# --- 6. The same logic applies to custom objects (not just built-ins) ---
class Counter:
def __init__(self, count=0):
[Link] = count

def increment_counter(counter_obj):
counter_obj.count += 1 # mutates the object's attribute in place

c = Counter(count=10)
increment_counter(c)
print(f"Custom object mutation visible to caller: {[Link]}") # 11

# --- 7. Passing a list into recursion: shared mutation across calls (common in backtracking) ---
def collect_leaves(node, result):
"""Appends leaf values into a SHARED result list across all recursive calls."""
if node is None:
return
if [Link] is None and [Link] is None:
[Link]([Link]) # mutates the SAME list object every recursive call sees
return
collect_leaves([Link], result)
collect_leaves([Link], result)

class Node:
def __init__(self, val, left=None, right=None):
[Link], [Link], [Link] = val, left, right

tree = Node(1, Node(2, Node(4), Node(5)), Node(3))

leaves = []
collect_leaves(tree, leaves)
print(f"Collected leaves via shared mutable list: {leaves}") # [4, 5, 3]
Section 4: Object-Oriented Programming (OOP) for DSA

4.1 Classes & Custom Nodes

Core Concept & Use Case: A class is a blueprint for creating objects that bundle data (attributes) and behavior (methods)
together. In DSA specifically, classes are used almost exclusively to define custom node structures — ListNode for linked lists,
TreeNode for binary trees, Node / Edge for graphs — which are the building blocks for the majority of "Top 130"-style problems.
Understanding classes well means understanding exactly how these node-based structures are constructed, linked together via
references, and traversed.

Time & Space Complexity:

Worst
Operation Average Case Notes
Case

Object instantiation Node(val) O(1) O(1) Allocates memory for the object's attributes

Attribute access [Link] O(1) O(1) Direct dictionary-like lookup in the instance's __dict__

Attribute assignment
O(1) O(1) Rebinds a reference, doesn't copy data
[Link] = x

O(1) + method's own

Method call [Link]() Same The dispatch itself is O(1); cost depends on what the method does
complexity

O(1) per object (excl. referenced Plus overhead for Python's object metadata (~56 bytes baseline for a
Space per object O(1)
data) simple object)

Deep-Dive Sub-Topics:

a) Anatomy of a class: __init__ , self , and instance attributes: __init__ is the constructor — automatically called when you write
Node(5) . The first parameter, conventionally named self , refers to the specific instance being created/operated on; it's how Python
distinguishes "this particular node's val " from "that other node's val ." Every attribute assigned via [Link] = value inside __init__
becomes part of that specific instance's state.

b) The standard DSA node pattern ( ListNode , TreeNode ): Across nearly all linked-list and tree problems, the convention is: val holds
the data, and one or more additional attributes ( next for linked lists; left / right for binary trees) hold references to other node
objects (or None if there is no such neighbor). This is precisely how a "structure" emerges from individually simple objects — the
structure lives entirely in how the references are wired together, not in any single node.

c) __repr__ and __str__ for debuggability: By default, printing a custom object gives an unhelpful <__main__.Node object at 0x7f...> .
Defining __repr__ (used by print() , debuggers, and the REPL) lets you control exactly what gets shown — invaluable when debugging
linked-list or tree problems where you want to print the value, not the memory address.

d) Comparison methods ( __eq__ , __lt__ ) for use in sets, dicts, and heaps: As established in Sections 1.3 and 1.4, custom objects
need __eq__ / __hash__ to be usable in sets/dicts. Separately, objects need __lt__ (less-than) defined if you want to push them directly
into a heapq (Section 5.2) or sort a list of them — Python's sorting and heap operations rely on < comparisons between elements.

e) @dataclass — reducing node boilerplate (modern Python, optional but useful): The dataclasses module's @dataclass decorator
auto-generates __init__ , __repr__ , and __eq__ from simple type-annotated attribute declarations, eliminating repetitive boilerplate for
simple node-like classes. Worth knowing, though raw classes remain the dominant style seen in LeetCode's own node definitions.

Dry-Run Example: Constructing a 3-node linked list and traversing it

class ListNode:
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

Step 1: c = ListNode(3) # Object_C created: {val: 3, next: None}

Step 2: b = ListNode(2, c) # Object_B created: {val: 2, next: -> Object_C}
Step 3: a = ListNode(1, b) # Object_A created: {val: 1, next: -> Object_B}

Memory picture:
a -> [val=1, next] -> b -> [val=2, next] -> c -> [val=3, next=None]

Traversal: current = a
Step 4: [Link] = 1 -> print 1. current = [Link] -> now points to Object_B
Step 5: [Link] = 2 -> print 2. current = [Link] -> now points to Object_C
Step 6: [Link] = 3 -> print 3. current = [Link] -> now points to None
Step 7: current is None -> loop terminates.

Output: 1 2 3

Production-Ready Sample Code:

# ============================================================
# CLASSES & CUSTOM NODES — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. The canonical LeetCode-style ListNode definition ---

class ListNode:
"""Standard singly-linked-list node, exactly as defined in most LeetCode problems."""
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

def __repr__(self):
# Custom repr makes debugging MUCH easier than the default object address
return f"ListNode({[Link]})"

# Manually building a linked list: 1 -> 2 -> 3 -> None

node3 = ListNode(3)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)

# Traversing it (the fundamental linked-list operation)

def print_linked_list(head):
values = []
current = head
while current is not None:
[Link](str([Link]))
current = [Link] # move the pointer forward
print(" -> ".join(values))

print_linked_list(node1) # 1 -> 2 -> 3

# --- 2. The canonical LeetCode-style TreeNode definition ---

class TreeNode:
"""Standard binary tree node, exactly as defined in most LeetCode problems."""
def __init__(self, val=0, left=None, right=None):
[Link] = val
[Link] = left
[Link] = right

def __repr__(self):
return f"TreeNode({[Link]})"

# Build: 5
# / \
# 3 8
# / \
# 1 4
root = TreeNode(5,
TreeNode(3, TreeNode(1), TreeNode(4)),
TreeNode(8))

def inorder_traversal(node, result=None):

"""Standard recursive in-order DFS traversal."""
if result is None:
result = []
if node:
inorder_traversal([Link], result)
[Link]([Link])
inorder_traversal([Link], result)
return result

print(f"In-order traversal: {inorder_traversal(root)}") # [1, 3, 4, 5, 8]

# --- 3. Custom comparison methods for use in heaps / sorting ---

class Task:
"""A task with a priority, comparable directly for use in heapq or sorted()."""
def __init__(self, name, priority):
[Link] = name
[Link] = priority

def __lt__(self, other):

# Defines what "less than" means for two Tasks -> enables heapq/sort to work
return [Link] < [Link]

def __repr__(self):
return f"Task({[Link]!r}, priority={[Link]})"

tasks = [Task("low", 5), Task("urgent", 1), Task("medium", 3)]

[Link]() # works because __lt__ is defined; no key= needed
print(f"Sorted tasks by priority: {tasks}")
# [Task('urgent', priority=1), Task('medium', priority=3), Task('low', priority=5)]

# --- 4. @dataclass: reducing boilerplate for simple node-like classes ---

from dataclasses import dataclass, field
from typing import Optional

@dataclass
class GraphNode:
"""Auto-generates __init__, __repr__, and __eq__ from these annotations."""
val: int
neighbors: list = field(default_factory=list)
# default_factory avoids the mutable-default-argument trap from Section 3.2d

n1 = GraphNode(1)
n2 = GraphNode(2)
[Link](n2)
print(f"Dataclass node: {n1}") # GraphNode(val=1, neighbors=[GraphNode(val=2, neighbors=[])])

# --- 5. A more complete custom class: a simple Stack ADT built on a list ---
class Stack:
 """Encapsulates a list to provide a clean Stack interface (LIFO)."""
def __init__(self):
self._items = [] # leading underscore = "internal use" convention

def push(self, item):

self._items.append(item) # O(1) amortized

def pop(self):
if self.is_empty():
raise IndexError("pop from an empty stack")
return self._items.pop() # O(1)

def peek(self):
if self.is_empty():
raise IndexError("peek from an empty stack")
return self._items[-1] # O(1)

def is_empty(self):
return len(self._items) == 0 # O(1)

def __len__(self):
return len(self._items) # enables len(my_stack)

s = Stack()
[Link](1); [Link](2); [Link](3)
print(f"Stack size: {len(s)}, peek: {[Link]()}, pop: {[Link]()}, size after pop: {len(s)}")

4.2 Pointers / References in Python

Core Concept & Use Case: Python has no explicit pointer type (no &x or *ptr syntax like C/C++), but the concept of a pointer — "a
value that refers to the location of another value" — is exactly what every Python variable name is. Every variable is a reference to an
object living somewhere in memory; this is the mechanism that makes linked lists, trees, and graphs possible at all in Python (Section
4.1's [Link] / [Link] are pointers, just without the explicit dereference syntax). Mastering this distinction between "the
variable" and "the object it refers to" is the single most important mental model for linked-list and tree manipulation problems
(reversal, cycle detection, deep copying).

Time & Space Complexity:

Operation Average Case Worst Case Notes

Assignment a = b (reference copy) O(1) O(1) Only copies the reference, never the underlying object

is comparison (identity check) O(1) O(1) Compares memory addresses directly

== comparison (equality check) O(1) to O(n) O(n) Depends on the type; may recursively compare contents

Shallow copy [Link](obj) O(n) O(n) n = number of top-level elements; nested objects still shared

Deep copy [Link](obj) O(n) O(n) n = total elements across all nesting levels; fully independent copy

Deep-Dive Sub-Topics:

a) is vs == — identity vs. equality: a is b asks: "do these two names point to the exact same object in memory?" a == b asks: "do
these two objects have equivalent value, according to __eq__ ?" Two distinct list objects with identical contents ( [1,2,3] and [1,2,3] )
are == but not is — they're equal in value but live at different memory addresses. This distinction is critical in linked-list problems:
checking [Link] is None (identity) is the correct, idiomatic way to check for the end of a list — never [Link] == None .

b) Why two pointers to the same node enable O(1) cycle/intersection tricks: Floyd's Cycle Detection ("tortoise and hare") works
because both the slow and fast pointer are just two separate variable names that can independently be re-pointed to walk through the
same underlying chain of node objects. If the fast pointer ( fast = [Link] ) ever becomes identical ( is ) to the slow pointer, you've
proven a cycle exists — entirely through reference comparison, no extra data structure needed.

c) Shallow copy vs. deep copy — the nested-mutation trap: [Link](obj) (shallow) creates a new top-level container, but every
element inside it still references the same nested objects as the original. If those nested objects are mutable, modifying them through
the copy will also affect the original. [Link](obj) recursively copies everything, all the way down, producing a fully independent
structure — at the cost of more time and memory.

d) Reference counting & garbage collection (brief, practical relevance): CPython tracks how many references point to each object
( [Link] ). When that count drops to zero (no variable, list, or attribute points to it anymore), the object's memory is
automatically reclaimed. This is why setting [Link] = None during linked-list deletion is what actually allows the "deleted" node to be
garbage collected — there's no free() call needed, but you must ensure nothing still references the node you intend to discard.

e) Why "rewiring pointers" is the essence of most linked-list problems: Reversing a linked list, deleting a node, inserting a node,
merging two lists — all of these are really just exercises in carefully reassigning .next references in the correct order so that no node is
"lost" (unreachable) prematurely, and no cycle is accidentally introduced.

Dry-Run Example: Reversing a linked list via pointer rewiring

Initial list: 1 -> 2 -> 3 -> None
Goal: reverse to None <- 1 <- 2 <- 3 (i.e., new head is the old tail)

prev = None
curr = node1 ([Link]=1, points to node2)

Iteration 1:
Step 1: next_temp = [Link] # save node2 before we overwrite [Link]
Step 2: [Link] = prev # [Link] now points to None (was node2)
Step 3: prev = curr # prev now points to node1
Step 4: curr = next_temp # curr now points to node2
State: None <- 1 2 -> 3 -> None (prev chain: None<-1; remaining: 2->3->None)

Iteration 2:
Step 1: next_temp = [Link] # save node3
Step 2: [Link] = prev # [Link] now points to node1 (was node3)
Step 3: prev = curr # prev now points to node2
Step 4: curr = next_temp # curr now points to node3
State: None <- 1 <- 2 3 -> None

Iteration 3:
Step 1: next_temp = [Link] # next_temp = None (node3 had no next)
Step 2: [Link] = prev # [Link] now points to node2 (was None)
Step 3: prev = curr # prev now points to node3
Step 4: curr = next_temp # curr now points to None -> LOOP ENDS

Final: prev points to node3, which is now the new head.

Resulting list: 3 -> 2 -> 1 -> None

Production-Ready Sample Code:

# ============================================================
# POINTERS / REFERENCES — Common DSA Idioms & Edge Cases
# ============================================================

# --- 1. `is` vs `==`: identity vs equality (the correct way to check for None) ---
a = [1, 2, 3]
b = [1, 2, 3] # a DIFFERENT object with the same contents
c = a # c is the SAME object as a (reference copy)

print(f"a == b: {a == b}") # True (same VALUE)

print(f"a is b: {a is b}") # False (different OBJECTS in memory)
print(f"a is c: {a is c}") # True (literally the same object)

# Idiomatic None-checking in DSA code: ALWAYS use `is`, never `==`

node_next = None
if node_next is None: # correct, idiomatic
print("Reached the end of the list (using 'is None').")

# --- 2. Reversing a singly linked list via pointer rewiring ---

class ListNode:
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

def reverse_linked_list(head):
"""Iterative reversal: O(n) time, O(1) extra space."""
prev = None
curr = head
while curr is not None:
next_temp = [Link] # save the next node before we overwrite the link
[Link] = prev # reverse this node's pointer
prev = curr # advance prev
curr = next_temp # advance curr
return prev # prev is now the new head

def to_list(head):
out = []
while head:
[Link]([Link])
head = [Link]
return out

node3 = ListNode(3)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)
new_head = reverse_linked_list(node1)
print(f"Reversed list: {to_list(new_head)}") # [3, 2, 1]

# --- 3. Floyd's Cycle Detection: pure pointer-comparison trick ---

def has_cycle(head):
"""O(n) time, O(1) space -- detects a cycle using two pointers, no extra set."""
slow = fast = head
while fast is not None and [Link] is not None:
slow = [Link] # moves 1 step
fast = [Link] # moves 2 steps
if slow is fast: # IDENTITY check: have they landed on the same node?
return True
return False

# Build a list with a cycle: 1 -> 2 -> 3 -> back to 2

cyc3 = ListNode(3)
cyc2 = ListNode(2, cyc3)
cyc1 = ListNode(1, cyc2)
[Link] = cyc2 # introduces the cycle
print(f"Cycle detected: {has_cycle(cyc1)}") # True

# A separate, cycle-free list for comparison

clean3 = ListNode(3)
clean2 = ListNode(2, clean3)
clean1 = ListNode(1, clean2)
print(f"Cycle detected (clean list): {has_cycle(clean1)}") # False

# --- 4. Shallow copy vs deep copy: the nested-mutation trap ---

import copy

original = {"name": "Alice", "scores": [90, 85, 95]}

shallow = [Link](original)
shallow["scores"].append(100) # mutates the SHARED inner list
print(f"Original after shallow-copy mutation: {original}")
# {'name': 'Alice', 'scores': [90, 85, 95, 100]} <- original WAS affected!

deep_original = {"name": "Bob", "scores": [70, 80, 90]}

deep = [Link](deep_original)
deep["scores"].append(999) # mutates an INDEPENDENT inner list
print(f"Original after deep-copy mutation: {deep_original}")
# {'name': 'Bob', 'scores': [70, 80, 90]} <- original was NOT affected

# --- 5. Reference counting in action ---

import sys

x = [1, 2, 3]
print(f"Reference count for x's object: {[Link](x) - 1}") # -1 to exclude the temp ref from the call itself
y = x # one more reference to the SAME object
print(f"Reference count after y = x: {[Link](x) - 1}")
del y # remove one reference
print(f"Reference count after del y: {[Link](x) - 1}")
Section 5: Built-in Modules for DSA

5.1 [Link]

Core Concept & Use Case: deque (pronounced "deck," short for double-ended queue) is implemented as a doubly-linked list of
fixed-size blocks, giving it O(1) appends/pops from both ends — something a plain list fundamentally cannot do efficiently at the
front (recall Section 1.1b: [Link](0) is O(n)). In DSA, deque is the correct choice for: implementing a Queue (FIFO, for BFS), a
Stack (LIFO, equally valid and often preferred over a list), and the sliding window maximum/minimum pattern (monotonic
deque).

Time & Space Complexity:

Operation Average Case Worst Case Notes

append(x) (right end) O(1) O(1)

appendleft(x) (left end) O(1) O(1) This is the key advantage over a list

pop() (right end) O(1) O(1)

popleft() (left end) O(1) O(1) This is the key advantage over a list

Indexed access dq[i] O(n) O(n) Unlike a list! Deques are NOT optimized for random access

Search x in dq O(n) O(n) Linear scan

rotate(k) O(k) O(k) Rotates elements k steps

Space O(n) O(n) Slightly higher per-element overhead than a list

Deep-Dive Sub-Topics:

a) Why deque beats list for queue-like (FIFO) usage: A list stores its elements in one contiguous block, so removing from the
front ( pop(0) ) requires shifting every other element. A deque is internally structured as a chain of fixed-size blocks, with direct pointers
to both the first and last block — adding/removing from either end never requires shifting any other element, hence true O(1) at both
ends.

b) The random-access trade-off: Because of that block-based internal structure, jumping directly to an arbitrary middle index
( dq[500] ) requires walking through blocks to locate it — O(n) in the worst case, unlike a list's O(1) direct offset calculation. Rule of
thumb: if your algorithm needs frequent indexing into the middle, use a list; if it needs frequent push/pop at either end, use a deque.

c) maxlen — a built-in fixed-size sliding window: deque(maxlen=k) automatically discards the oldest element from the opposite end
once the deque exceeds size k on the next append — extremely useful for fixed-size sliding window problems (e.g., "last k elements
seen") without any manual eviction logic.

d) The Monotonic Deque pattern (sliding window maximum): A more advanced but very common technique: maintain a deque of
indices such that the values they point to are always in decreasing order (front-to-back). When a new element arrives, pop smaller
elements off the back before adding the new index — this guarantees the front of the deque always holds the index of the current
window's maximum, achieved in amortized O(1) per element (O(n) total for the whole array), which is a major improvement over the
naive O(n*k) brute force.

e) deque as a Stack — equally valid, sometimes preferred: Although a plain list is commonly used as a stack, deque 's
append() / pop() from the right end are also O(1), making it an equally correct stack choice — and the only correct choice if the same
structure also needs FIFO behavior at some point (e.g., certain BFS/DFS hybrid algorithms).

Dry-Run Example: BFS using a deque as a FIFO queue

Graph (adjacency list): {1: [2, 3], 2: [4], 3: [4], 4: []}
Goal: BFS starting from node 1.

from collections import deque

queue = deque([1]) # initialize with start node. queue: [1]
visited = {1}

Iteration 1:
Step 1: node = [Link]() -> node = 1. queue: [] (now empty)
Step 2: Process node 1 (e.g., print/record it)
Step 3: For neighbor in [2, 3]: neither visited -> add to visited, append to queue
State: queue: [2, 3] visited: {1, 2, 3}

Iteration 2:
Step 1: node = [Link]() -> node = 2. queue: [3]
Step 2: Process node 2
Step 3: For neighbor in [4]: not visited -> add to visited, append to queue
State: queue: [3, 4] visited: {1, 2, 3, 4}

Iteration 3:
Step 1: node = [Link]() -> node = 3. queue: [4]
Step 2: Process node 3
Step 3: For neighbor in [4]: ALREADY visited -> skip
State: queue: [4] visited: {1, 2, 3, 4}

Iteration 4:
Step 1: node = [Link]() -> node = 4. queue: [] (empty)
Step 2: Process node 4. No neighbors.
Step 3: queue is empty -> BFS terminates.

Visit order: 1, 2, 3, 4 (each popleft() was O(1) -- a list's pop(0) would have been O(n) each time)

Production-Ready Sample Code:

# ============================================================
# [Link] — Common DSA Idioms & Edge Cases
# ============================================================

from collections import deque

# --- 1. Deque as a FIFO Queue for BFS (the most common DSA usage) ---
def bfs(graph, start):
"""Standard BFS using deque for O(1) popleft. O(V + E) time."""
visited = {start}
order = []
queue = deque([start])
while queue:
node = [Link]() # O(1) -- would be O(n) with a list!
[Link](node)
for neighbor in [Link](node, []):
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor) # O(1)
return order

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}

print(f"BFS order: {bfs(graph, 1)}") # [1, 2, 3, 4]

# --- 2. Deque as a Stack (LIFO) -- equally valid as a list-based stack ---

stack = deque()
[Link](1)
[Link](2)
[Link](3)
print(f"Stack pop: {[Link]()}, remaining: {list(stack)}") # 3, [1, 2]

# --- 3. appendleft/popleft -- operations a list literally cannot do efficiently ---

dq = deque([2, 3, 4])
[Link](1) # O(1) -- adds to the front
[Link](5) # O(1) -- adds to the back
print(f"After appendleft(1) and append(5): {list(dq)}") # [1, 2, 3, 4, 5]
print(f"popleft(): {[Link]()}, remaining: {list(dq)}") # 1, [2, 3, 4, 5]

# --- 4. maxlen: automatic fixed-size sliding window ---

last_3 = deque(maxlen=3)
for num in [1, 2, 3, 4, 5]:
last_3.append(num)
print(f"After adding {num}, window is: {list(last_3)}")
# Output progression:
# [1]
# [1, 2]
# [1, 2, 3]
# [2, 3, 4] <- 1 was automatically evicted
# [3, 4, 5] <- 2 was automatically evicted

# --- 5. Monotonic deque: Sliding Window Maximum (LeetCode 239 pattern) ---
def max_sliding_window(nums, k):
"""
Returns the max of every k-sized window. O(n) total time using a
monotonic deque of INDICES (values stay in decreasing order front-to-back).
"""
dq = deque() # will store indices, not values
result = []

for i, num in enumerate(nums):

# Step 1: remove indices from the back whose VALUES are smaller
# than the current number -- they can never be the max again.
while dq and nums[dq[-1]] < num:
[Link]()
[Link](i)

# Step 2: remove the front index if it has fallen out of the window
if dq[0] <= i - k:
[Link]()

# Step 3: once we've seen at least k elements, record the current max
if i >= k - 1:
[Link](nums[dq[0]]) # front of deque = index of current max

return result

print(f"Sliding window max: {max_sliding_window([1,3,-1,-3,5,3,6,7], 3)}")

# [3, 3, 5, 5, 6, 7]

# --- 6. rotate(): cyclic shifting, useful for circular buffer problems ---
dq2 = deque([1, 2, 3, 4, 5])
[Link](2) # positive k rotates RIGHT (elements move toward higher index)
print(f"After rotate(2): {list(dq2)}") # [4, 5, 1, 2, 3]
[Link](-2) # negative k rotates LEFT, undoing the previous rotation
print(f"After rotate(-2): {list(dq2)}") # [1, 2, 3, 4, 5]

5.2 heapq

Core Concept & Use Case: heapq provides a binary min-heap implementation built directly on top of a plain Python list — there's
no separate "Heap" object; you just call module-level functions ( [Link](lst, x) , etc.) on an ordinary list that the module
treats as a heap-ordered array. In DSA, heaps are the structure of choice whenever you repeatedly need the smallest (or largest)
element from a changing collection — used in: Top-K problems, Dijkstra's shortest path, merge K sorted lists, median-finding
(two-heap technique), and any "priority queue" requirement (task scheduling by priority).
 Time & Space Complexity:

Operation Average Case Worst Case Notes

heappush(heap, x) O(log n) O(log n) Insert + "bubble up" to restore heap property

heappop(heap) O(log n) O(log n) Remove root + "bubble down" to restore heap property

Peek minimum heap[0] O(1) O(1) The root is always at index 0 — no removal needed

heapify(list) (build heap from existing list) O(n) O(n) Surprisingly linear, NOT O(n log n) — see deep-dive below

heappushpop(heap, x) O(log n) O(log n) Push then pop in one optimized call

nlargest(k, iterable) / nsmallest(k, iterable) O(n log k) O(n log k) Efficient for small k relative to n

Space O(n) O(n) Same array, no extra structure needed

Deep-Dive Sub-Topics:

a) Min-heap by default — and the "negate for max-heap" trick: Python's heapq only implements a min-heap (smallest element
always at the root/index 0). To simulate a max-heap, the standard idiom is to push the negation of each value ( [Link](heap, -
x) ), then negate again when popping ( -[Link](heap) ). For tuples/objects where simple negation doesn't apply, you instead define
__lt__ to invert the natural comparison (see Section 4.1d).

b) Why heapify is O(n), not O(n log n): Intuitively you might expect building a heap from scratch to cost O(n log n) (n inserts × O(log
n) each), but heapify is smarter: it works bottom-up, calling "sift-down" only on the non-leaf nodes (roughly the first half of the array).
The mathematical reason it totals O(n) rather than O(n log n) is that most nodes are near the bottom of the tree and only need to sift
down a very short distance — the sum of all these distances, across the whole tree, converges to a linear bound rather than n log n.

c) The array-based heap structure (no explicit tree nodes): A binary heap stored in a list uses simple index arithmetic to represent
the implicit tree: for a node at index i , its children are at indices 2*i + 1 and 2*i + 2 , and its parent is at (i - 1) // 2 . This means no
Node objects or pointers are needed at all — the entire tree structure is implicit in the array positions, which is part of why heap
operations are so fast (great cache locality, no pointer chasing).

d) Pushing tuples for "priority + payload" — and the tie-breaking gotcha: The most common heap idiom in DSA is pushing
(priority, payload) tuples, e.g., [Link](heap, (distance, node)) for Dijkstra's algorithm. Tuples compare element-by-element, so
the heap orders primarily by priority . Gotcha: if two tuples have equal priority, Python will then compare the second elements
( payload ) to break the tie — if those payloads are objects without a defined __lt__ , this raises a TypeError . The standard fix is to include
a unique tie-breaker (like an insertion counter) as the second tuple element: (priority, counter, payload) .

e) The two-heap pattern for streaming median: Maintaining a running median over a stream of numbers efficiently requires two
heaps: a max-heap for the lower half of numbers seen so far, and a min-heap for the upper half, kept balanced in size. The median is
then derivable in O(1) from the two roots, while each new number only costs O(log n) to insert and rebalance.

Dry-Run Example: heappush bubble-up mechanics

Starting min-heap (as an array): [2, 5, 7, 9, 8]

(Implicit tree: 2
/ \
5 7
/ \
9 8 )

Call [Link](heap, 1):

Step 1: Append 1 to the END of the array (next available leaf position).
Array: [2, 5, 7, 9, 8, 1] <- 1 is now at index 5
Step 2: Compute its parent index: (5 - 1) // 2 = 2 -> parent value is 7
Step 3: Is 1 < 7 (child smaller than parent)? YES -> violates min-heap property -> SWAP
Array: [2, 5, 1, 9, 8, 7] <- 1 moved to index 2, 7 moved to index 5
Step 4: New index of 1 is 2. Compute ITS parent: (2 - 1) // 2 = 0 -> parent value is 2
Step 5: Is 1 < 2? YES -> violates property again -> SWAP
Array: [1, 5, 2, 9, 8, 7] <- 1 moved to index 0 (the root), 2 moved to index 2
Step 6: New index of 1 is 0 -- it's the root, no parent to compare against -> STOP

Final heap array: [1, 5, 2, 9, 8, 7] (root = 1, the new minimum, as expected)

This "bubble up" process took O(log n) swaps in the worst case (tree height).

Production-Ready Sample Code:

# ============================================================
# heapq — Common DSA Idioms & Edge Cases
# ============================================================

import heapq

# --- 1. Basic min-heap usage: push, pop, peek ---

heap = []
[Link](heap, 5)
[Link](heap, 1)
[Link](heap, 8)
[Link](heap, 3)
print(f"Heap array (internal, NOT fully sorted): {heap}") # e.g. [1, 3, 8, 5]
print(f"Peek minimum (heap[0]): {heap[0]}") # 1, O(1)
print(f"Pop minimum: {[Link](heap)}") # 1, O(log n)
print(f"Heap after pop: {heap}")

# --- 2. heapify: converting an existing list into a heap IN PLACE, in O(n) ---
nums = [9, 4, 7, 1, 8, 2]
[Link](nums) # O(n), rearranges 'nums' in place
print(f"Heapified array: {nums}") # root (nums[0]) is guaranteed to be the minimum

# --- 3. Simulating a MAX-heap via negation ---

max_heap = []
for val in [5, 1, 8, 3]:
[Link](max_heap, -val) # store negated values

largest = -[Link](max_heap) # negate again on the way out

print(f"Largest value via negated min-heap trick: {largest}") # 8

# --- 4. Top-K pattern: find the K largest elements efficiently ---

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
top_3 = [Link](3, data) # O(n log k), better than full sort for small k
bottom_3 = [Link](3, data)
print(f"Top 3 largest: {top_3}") # [9, 6, 5]
print(f"Bottom 3 smallest: {bottom_3}") # [1, 1, 2]

# --- 5. Priority queue with (priority, payload) tuples + tie-breaker ---

import itertools

task_heap = []
counter = [Link]() # unique, ever-increasing tie-breaker

def add_task(priority, name):

# (priority, unique_count, name) -- the counter guarantees no TypeError
# ever occurs from comparing 'name' strings directly when priorities tie.
[Link](task_heap, (priority, next(counter), name))

add_task(2, "write report")

add_task(1, "fix critical bug")
add_task(2, "review PR") # SAME priority as "write report" -- tie-breaker saves us
add_task(3, "update docs")

while task_heap:
priority, _, name = [Link](task_heap)
print(f"Processing (priority={priority}): {name}")
# Output order: fix critical bug (1), write report (2), review PR (2), update docs (3)

# --- 6. Dijkstra's shortest path -- the canonical heapq graph algorithm ---
def dijkstra(graph, start):
"""
graph: dict of node -> list of (neighbor, weight)
Returns: dict of node -> shortest distance from start. O((V+E) log V).
"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)] # (distance, node)

while pq:
current_dist, current_node = [Link](pq)

# Skip stale entries (we may have pushed a node multiple times
# before finding its true shortest distance -- this is fine and
# standard practice with heapq, which has no built-in decrease-key).
if current_dist > distances[current_node]:
continue

for neighbor, weight in graph[current_node]:

distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
[Link](pq, (distance, neighbor))

return distances

graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
print(f"Shortest distances from A: {dijkstra(graph, 'A')}")
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}

# --- 7. Two-heap pattern: running median from a data stream ---

class MedianFinder:
"""Maintains a running median in O(log n) per insertion."""
def __init__(self):
[Link] = [] # max-heap (negated) for the lower half
[Link] = [] # min-heap for the upper half

def add_num(self, num):

[Link]([Link], -num) # always add to 'small' first
# Ensure every element in 'small' <= every element in 'large'
if [Link] and [Link] and (-[Link][0] > [Link][0]):
val = -[Link]([Link])
[Link]([Link], val)
# Rebalance sizes so they differ by at most 1
if len([Link]) > len([Link]) + 1:
val = -[Link]([Link])
 [Link]([Link], val)
elif len([Link]) > len([Link]) + 1:
val = [Link]([Link])
[Link]([Link], -val)

def find_median(self):
if len([Link]) > len([Link]):
return -[Link][0]
elif len([Link]) > len([Link]):
return [Link][0]
else:
return (-[Link][0] + [Link][0]) / 2.0

mf = MedianFinder()
for n in [5, 15, 1, 3]:
mf.add_num(n)
print(f"After adding {n}, median is: {mf.find_median()}")
# 5.0, 10.0, 5.0, 4.0

5.3 math

Core Concept & Use Case: The math module provides fast, C-implemented mathematical functions and constants that show up
constantly in DSA — not as a "data structure" in itself, but as essential utility for complexity analysis on the fly, numeric edge-
case handling, and classic algorithmic building blocks (GCD for number-theory problems, sqrt for prime-checking, inf for
initializing comparison baselines, log2 for understanding/predicting binary-search-style complexity).

Time & Space Complexity:

Function Average Case Worst Case Notes

[Link](x) O(1) O(1) Hardware-level floating point operation

[Link](a, b) O(log(min(a,b))) O(log(min(a,b))) Euclidean algorithm

[Link](n) O(n) O(n) Must multiply n terms; result can have many digits for large n

[Link](x, y) / x ** y O(log y) O(log y) Uses exponentiation by squaring for integer powers

[Link](x, base) O(1) O(1) Hardware-level operation

[Link] , [Link] , [Link] O(1) O(1) Constant-time checks/values

Space (all of the above) O(1) O(1) All return/operate on scalar values

Deep-Dive Sub-Topics:

a) [Link] as a "no comparison baseline yet" sentinel: Algorithms that track a running minimum (e.g., "find the minimum path
cost") commonly initialize a variable to [Link] rather than 0 or None — this guarantees that the very first real comparison ( if cost <
min_cost ) will always succeed, with no special-casing needed for "is this the first value we've seen?" The symmetric pattern, -[Link] , is
used when tracking a running maximum.

b) [Link] and number-theory-flavored problems: The Greatest Common Divisor shows up in problems involving fractions
(reducing to lowest terms), array problems asking for the GCD of all elements, and detecting repeating patterns. [Link] (available for
2+ arguments since Python 3.9) uses the highly efficient Euclidean algorithm internally rather than a naive factor-search.

c) [Link] and combinatorics — and why it grows dangerously fast: Factorials appear in permutation-counting and
combinatorics problems. It's worth internalizing just how fast factorial growth is: 20! is already over 2 quintillion — larger than a 64-bit
integer can represent in languages with fixed-width integers (Python's arbitrary-precision integers handle this gracefully, but it's a
reminder that any algorithm with true O(n!) complexity is only viable for tiny n, roughly n ≤ 12 in an interview setting).

d) math.log2 for predicting/verifying algorithmic complexity: If you want to sanity-check "how many times can I halve n before
reaching 1?" (the core operation count in binary search, or in divide-and-conquer recursion depth), math.log2(n) gives you that count
directly — useful both for complexity analysis during an interview, and occasionally as a literal value needed within a solution (e.g.,
determining the number of bits needed to represent a number).

e) Floating-point pitfalls ( [Link] , integer vs. float division): [Link] and similar functions return floats, which are subject
to floating-point precision error ( 0.1 + 0.2 != 0.3 in raw Python). When checking equality involving computed floats (e.g., verifying a
number is a perfect square), use [Link](a, b) rather than == , or stick to integer arithmetic where possible (e.g., checking r*r ==
n using r = int([Link](n)) and then verifying with integer multiplication, not trusting the float result alone).

Dry-Run Example: Euclidean algorithm for [Link](48, 18)

Goal: compute gcd(48, 18) using the Euclidean algorithm's repeated-remainder logic.

Step 1: a = 48, b = 18. Since b != 0, compute remainder = a % b = 48 % 18 = 12

Step 2: a, b = b, remainder -> a = 18, b = 12
Step 3: Since b != 0, compute remainder = a % b = 18 % 12 = 6
Step 4: a, b = b, remainder -> a = 12, b = 6
Step 5: Since b != 0, compute remainder = a % b = 12 % 6 = 0
Step 6: a, b = b, remainder -> a = 6, b = 0
Step 7: b == 0 -> STOP. The answer is a = 6.

gcd(48, 18) = 6
(Each step roughly halves the size of the numbers involved, which is why
this runs in O(log(min(a,b))) time rather than a slow factor-by-factor search.)

Production-Ready Sample Code:

# ============================================================
# math MODULE — Common DSA Idioms & Edge Cases
# ============================================================

import math

# --- 1. [Link] as a sentinel for running min/max tracking ---

def find_min_in_matrix(matrix):
"""Find the global minimum across a 2D matrix using [Link] as a baseline."""
min_val = [Link] # guarantees the first real comparison always succeeds
for row in matrix:
for val in row:
if val < min_val:
min_val = val
return min_val

print(f"Min in matrix: {find_min_in_matrix([[5, 2], [8, -3], [1, 9]])}") # -3

# --- 2. [Link] for reducing fractions / finding common patterns ---

print(f"gcd(48, 18) = {[Link](48, 18)}") # 6
print(f"gcd of multiple numbers: {[Link](48, 18, 12)}") # 6 (Python 3.9+)

def reduce_fraction(numerator, denominator):

"""Reduces a fraction to its lowest terms using gcd."""
g = [Link](numerator, denominator)
return numerator // g, denominator // g

print(f"24/36 reduced: {reduce_fraction(24, 36)}") # (2, 3)

# --- 3. [Link] for combinatorics (and why huge n is infeasible) ---

print(f"5! = {[Link](5)}") # 120
print(f"20! = {[Link](20)}") # 2432902008176640000 -- already enormous

def count_permutations(n, r):

"""nPr = n! / (n-r)! -- common combinatorics formula in DSA problems."""
return [Link](n) // [Link](n - r)

print(f"Permutations of 5 items taken 3 at a time: {count_permutations(5, 3)}") # 60

# --- 4. [Link] for primality checking (only check up to the square root) ---
def is_prime(n):
"""O(sqrt(n)) primality check -- a classic complexity-reduction technique."""
if n < 2:
return False
# Only need to check divisors up to sqrt(n): if n = a*b and a <= b,
# then a must be <= sqrt(n) -- so any factor pair has one factor <= sqrt(n).
for i in range(2, int([Link](n)) + 1):
if n % i == 0:
return False
return True

print(f"Is 17 prime? {is_prime(17)}") # True

print(f"Is 18 prime? {is_prime(18)}") # False

# --- 5. math.log2 to predict binary search step count ---

def binary_search_steps_needed(n):
"""How many comparisons binary search needs in the worst case for n elements."""
return [Link](math.log2(n)) if n > 0 else 0

print(f"Binary search steps needed for n=1,000,000: {binary_search_steps_needed(1_000_000)}") # 20

# --- 6. Floating-point pitfalls: [Link] vs naive == ---

result = 0.1 + 0.2
print(f"0.1 + 0.2 == 0.3 ? {result == 0.3}") # False! (floating point error)
print(f"[Link](0.1+0.2, 0.3) ? {[Link](result, 0.3)}") # True (correct way to compare)

def is_perfect_square(n):
"""Avoids trusting float sqrt directly -- verifies with integer arithmetic."""
if n < 0:
return False
r = int([Link](n))
# Check neighbors too, since float sqrt can be off by a tiny epsilon for large n
for candidate in (r - 1, r, r + 1):
if candidate >= 0 and candidate * candidate == n:
return True
return False

print(f"Is 16 a perfect square? {is_perfect_square(16)}") # True

print(f"Is 17 a perfect square? {is_perfect_square(17)}") # False

# --- 7. [Link] / [Link] -- defensive checks in numeric DSA code ---

value = float('inf')
print(f"Is value infinite? {[Link](value)}") # True
nan_value = float('nan')
print(f"Is nan_value NaN? {[Link](nan_value)}") # True
Section 6: Quick-Reference Cheat Sheet Table

Use this as your final sanity-check before any mock interview or contest. Bold entries highlight the operations most likely to trip
you up if you assume the wrong complexity.

Lists (Dynamic Array)

Operation Average Case Worst Case

Index access lst[i] O(1) O(1)

Index assignment lst[i] = x O(1) O(1)

Append (end) [Link](x) O(1) O(n)

Pop from front [Link](0) O(n) O(n)

Pop from end [Link]() O(1) O(1)

Insert middle [Link](i, x) O(n) O(n)

Delete middle del lst[i] O(n) O(n)

Search x in lst O(n) O(n)

Slice lst[a:b] O(k) O(k)

Sort [Link]() O(n log n) O(n log n)

Reverse [Link]() / lst[::-1] O(n) O(n)

Min/Max min(lst) / max(lst) O(n) O(n)

Tuples (Immutable Array)

Operation Average Case Worst Case

Index access tup[i] O(1) O(1)

Search x in tup O(n) O(n)

Slice tup[a:b] O(k) O(k)

Concatenation t1 + t2 O(n+m) O(n+m)

Hashing (for use as dict key) O(n) O(n)

Sets (Hash Table — keys only)

Operation Average Case Worst Case

Add [Link](x) O(1) O(n)

Remove [Link](x) / [Link](x) O(1) O(n)

Membership x in s O(1) O(n)

Union s1 \| s2 O(len(s1)+len(s2)) O(len(s1)+len(s2))

Intersection s1 & s2 O(min(|s1|,|s2|)) O(min(|s1|,|s2|))

Difference s1 - s2 O(len(s1)) O(len(s1))

Dictionaries (Hash Table — key-value pairs)

Operation Average Case Worst Case

Get d[key] O(1) O(n)

Set d[key] = val O(1) O(n)

Delete del d[key] O(1) O(n)

Membership key in d O(1) O(n)

[Link](key, default) O(1) O(n)

Iterate all items O(n) O(n)

[Link]() / .values() / .items() (creation) O(1) O(1)

Deques ([Link])

Operation Average Case Worst Case

append(x) / appendleft(x) O(1) O(1)

pop() / popleft() O(1) O(1)

Indexed access dq[i] O(n) O(n)

Search x in dq O(n) O(n)

rotate(k) O(k) O(k)

Heaps (heapq, binary min-heap on a list)

Operation Average Case Worst Case

Peek min heap[0] O(1) O(1)

heappush(heap, x) O(log n) O(log n)

heappop(heap) O(log n) O(log n)

heapify(list) O(n) O(n)

nlargest(k, it) / nsmallest(k, it) O(n log k) O(n log k)

heappushpop(heap, x) O(log n) O(log n)

Strings (immutable sequence, included for completeness)

Operation Average Case Worst Case

Index access s[i] O(1) O(1)

Slice s[a:b] O(k) O(k)

Concatenation s1 + s2 O(n+m) O(n+m)

s in big_s (substring search) O(n*m) O(n*m)

"".join(list_of_str) O(total chars) O(total chars)

Recursion & Function Calls

 Scenario Time Space (Call Stack)

Linear recursion (e.g. factorial) O(n) O(n)

Naive tree recursion (e.g. fib) O(2^n) O(n) — peak depth, not total calls

Memoized recursion O(n) typically O(n)

Divide & conquer (e.g. merge sort) O(n log n) O(log n) — stack depth only

Final Notes Before You Begin

Default to a dict or set the instant you catch yourself writing a nested loop just to check "have I seen this before?" — that's almost
always an O(n²) → O(n) opportunity.
Default to deque , not list , the instant your algorithm needs to remove from the front of a collection repeatedly (BFS, sliding
windows).
Always ask yourself "mutate or reassign?" before passing a list/dict into a helper function — it determines whether your caller's
data survives intact.
heapq is min-heap only — remember the negation trick (or a custom __lt__ ) the moment you need a max-heap.

When in doubt about a structure's cost, come back to this cheat sheet rather than guessing under interview pressure.

You're ready. Good luck with the 130.