🐍 Python Master Reference Guide

Complete Encyclopedia for LeetCode, Interviews & Production Code

Topics Covered:
Python Fundamentals • Data Structures • OOP
Functional & Dynamic Programming • Memory Management
Data Manipulation & Mining • Algorithms & Complexity
Advanced Topics • LeetCode Patterns & Brute Force

Brute Force → Optimized | Every Concept with Full Code

SECTION 1: Python Fundamentals
1.1 Syntax & Variables
Python uses indentation (4 spaces) to define code blocks. No semicolons or braces needed.

# Variables — no type declaration needed

name = 'Alice' # str
age = 30 # int
height = 5.9 # float
is_active = True # bool
nothing = None # NoneType

# Multiple assignment
x, y, z = 1, 2, 3
a = b = c = 0

# Type casting
num_str = str(42) # '42'
num_int = int('99') # 99
num_float = float('3.14') # 3.14
to_bool = bool(0) # False (0, '', [], None are falsy)

1.2 Data Types

Python's core built-in types:

# Strings
s = 'hello'
s2 = "world"
s3 = '''multi
line'''
s4 = f'Hello {name}, you are {age}' # f-string
s5 = [Link]() # HELLO
s6 = s[1:4] # ell (slicing)
s7 = s[::-1] # olleh (reverse)
s8 = ' hi '.strip() # 'hi'
s9 = 'a,b,c'.split(',') # ['a','b','c']
s10 = '-'.join(['a','b']) # 'a-b'

# Numbers
i = 10 // 3 # 3 (floor division)
r = 10 % 3 # 1 (modulo)
p = 2 ** 10 # 1024 (power)
import math
[Link](16) # 4.0
[Link](2.1) # 3
[Link](2.9) # 2
abs(-5) # 5
1.3 Operators
# Arithmetic: + - * / // % **
# Comparison: == != < > <= >=
# Logical: and or not
# Bitwise: & | ^ ~ << >>
# Assignment: = += -= *= /= //= **= %=
# Identity: is is not
# Membership: in not in

x = 5
print(x & 3) # 1 (bitwise AND: 101 & 011 = 001)
print(x | 3) # 7 (bitwise OR: 101 | 011 = 111)
print(x ^ 3) # 6 (XOR: 101 ^ 011 = 110)
print(x << 1) # 10 (left shift = multiply by 2)
print(x >> 1) # 2 (right shift = floor divide by 2)

# Walrus operator := (Python 3.8+)

data = [1, 2, 3, 4, 5]
if (n := len(data)) > 3:
print(f'List has {n} items') # List has 5 items

1.4 Control Flow

# if / elif / else
score = 85
if score >= 90: grade = 'A'
elif score >= 80: grade = 'B'
elif score >= 70: grade = 'C'
else: grade = 'F'

# Ternary
result = 'pass' if score >= 60 else 'fail'

# for loop
for i in range(5): # 0 1 2 3 4
print(i, end=' ')

for i in range(2, 10, 3): # 2 5 8 (start, stop, step)

print(i, end=' ')

for i, val in enumerate(['a','b','c']):

print(i, val) # 0 a, 1 b, 2 c

for a, b in zip([1,2,3], ['x','y','z']):

print(a, b) # 1 x, 2 y, 3 z

# while loop
n = 0
while n < 5:
n += 1
if n == 3: continue # skip 3
if n == 5: break # stop at 5
 print(n, end=' ') # 1 2 4

1.5 Comprehensions
# List comprehension
squares = [x**2 for x in range(10)]
evens = [x for x in range(20) if x % 2 == 0]
flat = [x for row in [[1,2],[3,4]] for x in row] # [1,2,3,4]

# Dict comprehension
word_len = {w: len(w) for w in ['hi','hello','hey']}
# {'hi': 2, 'hello': 5, 'hey': 3}

# Set comprehension
unique_sq = {x**2 for x in [-2,-1,0,1,2]} # {0,1,4}

# Generator expression (lazy — doesn't build full list in memory)

total = sum(x**2 for x in range(1000000)) # memory-efficient

💡 CHEAT SHEET — String

Methods: .upper() .lower() .strip() .split() .join() .replace() .find() .startswith() .endswith() .isdigit() .isalp
ha() .zfill() .format()
SECTION 2: Data Structures
2.1 Lists
Ordered, mutable, allows duplicates. O(1) append, O(n) insert/delete at arbitrary index.

lst = [3, 1, 4, 1, 5, 9, 2, 6]

# Access & slicing

lst[0] # 3 (first)
lst[-1] # 6 (last)
lst[2:5] # [4, 1, 5]
lst[::2] # [3, 4, 5, 2] (every 2nd)
lst[::-1] # reversed copy

# Mutation
[Link](7) # add to end
[Link](0, 0) # insert at index
[Link]([8,9]) # add multiple
[Link]() # remove last, returns it
[Link](0) # remove at index
[Link](1) # remove first occurrence of value
del lst[2:4] # delete slice

# Useful operations
[Link]() # in-place sort O(n log n)
[Link](key=lambda x: -x) # sort descending
sorted_copy = sorted(lst) # returns new list
[Link]() # in-place reverse
[Link](1) # count occurrences
[Link](9) # find first index of value
[Link]() # shallow copy

2.2 Tuples
Ordered, immutable, hashable (can be used as dict keys or in sets).

t = (1, 2, 3)
t2 = 1, 2, 3 # parentheses optional
single = (42,) # trailing comma needed for single-element

# Unpacking
a, b, c = t # a=1, b=2, c=3
first, *rest = t # first=1, rest=[2,3]

# Named tuples
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p.x, p.y) # 3 4
print(p[0], p[1]) # 3 4 (also indexable)
2.3 Sets
Unordered, unique elements. O(1) average lookup/insert/delete. Great for deduplication.

s = {1, 2, 3, 4, 5}
[Link](6) # add element
[Link](10) # remove if present (no error)
[Link](3) # remove (raises KeyError if missing)

# Set operations
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
a | b # union: {1,2,3,4,5,6}
a & b # intersection: {3,4}
a - b # difference: {1,2}
a ^ b # symmetric diff: {1,2,5,6}
[Link](b) # False
[Link]({1,2}) # True

# Deduplication
nums = [1, 2, 2, 3, 3, 3]
unique = list(set(nums)) # [1, 2, 3] (order not guaranteed)

2.4 Dictionaries
Key-value store. O(1) average access, insert, delete. Ordered by insertion order (Python 3.7+).

d = {'name': 'Alice', 'age': 30, 'score': 95}

# Access
d['name'] # 'Alice' (KeyError if missing)
[Link]('age', 0) # 30 (default 0 if missing)
[Link]('city', 'NYC') # sets if missing, returns value

# Modification
d['age'] = 31 # update
[Link]({'age': 32, 'x': 1}) # merge another dict
del d['x'] # delete key
[Link]('city', None) # remove and return (no error if missing)

# Iteration
[Link]() # dict_keys([...])
[Link]() # dict_values([...])
[Link]() # dict_items([(k,v), ...])
for k, v in [Link]():
print(f'{k}: {v}')

# Dict comprehension + merge (Python 3.9+)

merged = {**d, 'extra': 'val'}
merged2 = d | {'extra': 'val'} # same thing

# Frequency counter pattern

text = 'abracadabra'
freq = {}
 for ch in text:
freq[ch] = [Link](ch, 0) + 1
# Simpler with Counter:
from collections import Counter
freq = Counter(text) # Counter({'a':5,'b':2,'r':2,'c':1,'d':1})

2.5 Stacks & Queues

# ── STACK (LIFO) using list ──
stack = []
[Link](1) # push
[Link](2)
[Link](3)
[Link]() # 3 (pop from top)
stack[-1] # 2 (peek without removing)

# ── QUEUE (FIFO) using deque ──

from collections import deque
q = deque()
[Link](1) # enqueue right
[Link](2)
[Link](3)
[Link]() # 1 dequeue left O(1)
q[0] # 2 peek front

# deque as double-ended queue

dq = deque([1,2,3])
[Link](0) # [0, 1, 2, 3]
[Link](-1) # [-1, 0, 1, 2, 3]
[Link]() # removes 3
[Link]() # removes -1

# deque with max length (sliding window)

dq = deque(maxlen=3)
for n in [1,2,3,4,5]:
[Link](n) # auto-removes from left when full

2.6 Heaps (Priority Queue)

import heapq

# Min-heap (default)
h = []
[Link](h, 5)
[Link](h, 1)
[Link](h, 3)
[Link](h) # 1 (always removes minimum)
h[0] # peek minimum without removing

# Build heap from list

 nums = [3, 1, 4, 1, 5, 9]
[Link](nums) # O(n) in-place

# Max-heap trick: negate values

max_heap = []
for n in [3, 1, 4, 1, 5]:
[Link](max_heap, -n)
max_val = -[Link](max_heap) # 5

# k smallest / k largest
[Link](3, [5,3,1,7,2]) # [1,2,3]
[Link](3, [5,3,1,7,2]) # [7,5,3]

# Priority queue with tuples

pq = []
[Link](pq, (1, 'low'))
[Link](pq, (5, 'high'))
[Link](pq, (3, 'med'))
while pq:
priority, item = [Link](pq)
print(priority, item) # sorted by priority

2.7 Linked Lists

# Singly Linked List implementation
class ListNode:
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

class LinkedList:
def __init__(self):
[Link] = None

def append(self, val):

if not [Link]:
[Link] = ListNode(val)
else:
cur = [Link]
while [Link]:
cur = [Link]
[Link] = ListNode(val)

def prepend(self, val):

node = ListNode(val, [Link])
[Link] = node

def delete(self, val):

if not [Link]: return
if [Link] == val:
[Link] = [Link]; return
cur = [Link]
while [Link]:
 if [Link] == val:
[Link] = [Link]; return
cur = [Link]

def to_list(self):
result, cur = [], [Link]
while cur:
[Link]([Link])
cur = [Link]
return result

# Common LeetCode patterns

# Reverse a linked list
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = [Link]
[Link] = prev
prev = cur
cur = nxt
return prev

# Detect cycle (Floyd's tortoise & hare)

def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow == fast:
return True
return False

2.8 Trees
# Binary Tree Node
class TreeNode:
def __init__(self, val=0, left=None, right=None):
[Link] = val
[Link] = left
[Link] = right

# ── Traversals (DFS) ──
def inorder(root): # Left → Node → Right
return inorder([Link]) + [[Link]] + inorder([Link]) if root else []

def preorder(root): # Node → Left → Right

return [[Link]] + preorder([Link]) + preorder([Link]) if root else []

def postorder(root): # Left → Right → Node

return postorder([Link]) + postorder([Link]) + [[Link]] if root else
[]

# ── Level Order Traversal (BFS) ──

 from collections import deque
def level_order(root):
if not root: return []
result, q = [], deque([root])
while q:
level = []
for _ in range(len(q)): # process entire level
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return result

# ── Tree Height ──
def height(root):
if not root: return 0
return 1 + max(height([Link]), height([Link]))

# ── BST operations ──
def bst_search(root, target):
if not root: return False
if [Link] == target: return True
if target < [Link]: return bst_search([Link], target)
return bst_search([Link], target)

def bst_insert(root, val):

if not root: return TreeNode(val)
if val < [Link]: [Link] = bst_insert([Link], val)
else: [Link] = bst_insert([Link], val)
return root

2.9 Graphs
# Adjacency list representation
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 5],
3: [1],
4: [1, 5],
5: [2, 4]
}

# BFS — shortest path in unweighted graph

from collections import deque
def bfs(graph, start, target):
visited = set([start])
q = deque([(start, [start])])
while q:
node, path = [Link]()
if node == target: return path
for neighbor in graph[node]:
 if neighbor not in visited:
[Link](neighbor)
[Link]((neighbor, path + [neighbor]))
return None

# DFS — iterative
def dfs_iterative(graph, start):
visited, stack = set(), [start]
order = []
while stack:
node = [Link]()
if node not in visited:
[Link](node)
[Link](node)
[Link](graph[node])
return order

# DFS — recursive
def dfs_recursive(graph, node, visited=None):
if visited is None: visited = set()
[Link](node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited

# Detect cycle in directed graph

def has_cycle_directed(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY
for nb in graph[node]:
if color[nb] == GRAY: return True # back edge = cycle
if color[nb] == WHITE and dfs(nb): return True
color[node] = BLACK
return False
return any(dfs(n) for n in graph if color[n] == WHITE)

📋 CHEAT SHEET: list O(1) append/access | dict/set O(1) avg lookup | deque O(1) both ends | heap
O(log n) push/pop | heapify O(n)
SECTION 3: Object-Oriented Programming (OOP)
3.1 Classes & Objects
class Animal:
# Class variable (shared across ALL instances)
kingdom = 'Animalia'
count = 0

def __init__(self, name, age):

# Instance variables (unique to each instance)
[Link] = name
[Link] = age
[Link] += 1

def speak(self):
return f'{[Link]} makes a sound'

@classmethod
def get_count(cls):
return [Link]

@staticmethod
def is_alive(age):
return age > 0

def __repr__(self):
return f'Animal(name={[Link]!r}, age={[Link]})'

a1 = Animal('Dog', 3)
a2 = Animal('Cat', 5)
print(Animal.get_count()) # 2
print(Animal.is_alive(3)) # True
print(repr(a1)) # Animal(name='Dog', age=3)

3.2 Inheritance & Polymorphism

class Animal:
def __init__(self, name):
[Link] = name
def speak(self):
raise NotImplementedError('Subclass must implement speak()')

class Dog(Animal):
def speak(self): # override
return f'{[Link]} says: Woof!'
def fetch(self):
return f'{[Link]} fetches the ball'

class Cat(Animal):
def speak(self): # override
 return f'{[Link]} says: Meow!'

# Multiple inheritance
class Robot:
def charge(self):
return 'Charging...'

class RoboDog(Dog, Robot): # MRO: RoboDog → Dog → Animal → Robot

pass

rd = RoboDog('Rex')
[Link]() # 'Rex says: Woof!' (from Dog)
[Link]() # 'Charging...' (from Robot)

# Polymorphism
animals = [Dog('Buddy'), Cat('Whiskers'), Dog('Max')]
for animal in animals:
print([Link]()) # each calls its own version

# super() — call parent method

class Puppy(Dog):
def __init__(self, name, tricks):
super().__init__(name) # call Dog (then Animal) __init__
[Link] = tricks

3.3 Encapsulation & Abstraction

from abc import ABC, abstractmethod

class Shape(ABC): # Abstract Base Class

@abstractmethod
def area(self): pass

@abstractmethod
def perimeter(self): pass

def describe(self): # concrete method on abstract class

return f'Area: {[Link]():.2f}, Perimeter: {[Link]():.2f}'

class Circle(Shape):
def __init__(self, radius):
self._radius = radius # _name = 'protected' (convention)
self.__secret = 'hidden' # __name = 'private' (name mangling)

@property
def radius(self): # getter
return self._radius

@[Link]
def radius(self, value): # setter with validation
if value <= 0: raise ValueError('Radius must be positive')
self._radius = value
 def area(self):
import math
return [Link] * self._radius ** 2

def perimeter(self):
import math
return 2 * [Link] * self._radius

c = Circle(5)
print([Link]()) # Area: 78.54, Perimeter: 31.42
[Link] = 10 # uses setter
# c.__secret # AttributeError — name mangled to _Circle__secret

3.4 Dunder / Magic Methods

class Vector:
def __init__(self, x, y):
self.x, self.y = x, y

# String representations
def __str__(self): return f'Vector({self.x}, {self.y})'
def __repr__(self): return f'Vector(x={self.x}, y={self.y})'

# Arithmetic operators
def __add__(self, other): return Vector(self.x+other.x, self.y+other.y)
def __sub__(self, other): return Vector(self.x-other.x, self.y-other.y)
def __mul__(self, scalar): return Vector(self.x*scalar, self.y*scalar)
def __rmul__(self, scalar): return self.__mul__(scalar)

# Comparison
def __eq__(self, other): return self.x == other.x and self.y == other.y
def __lt__(self, other): return abs(self) < abs(other)

# Container protocol
def __len__(self): return 2
def __getitem__(self, i): return (self.x, self.y)[i]
def __iter__(self): return iter((self.x, self.y))

# Boolean / numeric
def __bool__(self): return self.x != 0 or self.y != 0
def __abs__(self): return (self.x**2 + self.y**2) ** 0.5
def __hash__(self): return hash((self.x, self.y))

v1, v2 = Vector(1, 2), Vector(3, 4)

print(v1 + v2) # Vector(4, 6)
print(3 * v1) # Vector(3, 6)
print(list(v1)) # [1, 2]
print(abs(v2)) # 5.0
SECTION 4: Functional & Dynamic Programming
4.1 Lambda, map, filter, reduce
from functools import reduce

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Lambda — anonymous function

square = lambda x: x ** 2
add = lambda x, y: x + y

# map — apply function to each element

squares = list(map(lambda x: x**2, nums)) # [1,4,9,16,...]
squares = list(map(square, nums)) # same thing

# filter — keep elements where function returns True

evens = list(filter(lambda x: x % 2 == 0, nums)) # [2,4,6,8,10]

# reduce — fold list to single value

total = reduce(lambda a, b: a + b, nums) # 55
product = reduce(lambda a, b: a * b, nums) # 3628800

# Sorting with key

words = ['banana', 'apple', 'cherry', 'date']
[Link](key=lambda w: len(w)) # sort by length
[Link](key=lambda w: (len(w), w)) # multi-key sort

people = [{'name':'Bob','age':30}, {'name':'Alice','age':25}]

[Link](key=lambda p: p['age']) # sort dicts by field

4.2 Closures & Decorators

# Closure — inner function captures outer scope
def make_counter(start=0):
count = [start] # mutable container to allow reassignment
def counter():
count[0] += 1
return count[0]
return counter

c = make_counter(10)
c() # 11
c() # 12

# Decorator — wraps function to add behavior

import time, functools

def timer(func):
@[Link](func) # preserves original __name__, __doc__
def wrapper(*args, **kwargs):
 start = time.perf_counter()
result = func(*args, **kwargs)
end = time.perf_counter()
print(f'{func.__name__} took {end-start:.4f}s')
return result
return wrapper

@timer
def slow_sum(n):
return sum(range(n))

slow_sum(1000000) # slow_sum took 0.0312s

# Decorator with arguments

def repeat(n):
def decorator(func):
@[Link](func)
def wrapper(*args, **kwargs):
for _ in range(n):
result = func(*args, **kwargs)
return result
return wrapper
return decorator

@repeat(3)
def greet(name):
print(f'Hello, {name}!')

greet('Alice') # prints 3 times

4.3 Generators
# Generator function — uses yield
def fibonacci():
a, b = 0, 1
while True: # infinite sequence!
yield a
a, b = b, a + b

fib = fibonacci()
print([next(fib) for _ in range(10)]) # [0,1,1,2,3,5,8,13,21,34]

# Generator with range

def count_up(start, stop, step=1):
n = start
while n < stop:
yield n
n += step

list(count_up(0, 10, 2)) # [0, 2, 4, 6, 8]

# Generator expression
gen = (x**2 for x in range(1000000))
 next(gen) # 0 — computes lazily!

# yield from — delegate to sub-generator

def flatten(nested):
for item in nested:
if isinstance(item, list):
yield from flatten(item)
else:
yield item

list(flatten([1, [2, [3, 4]], [5, 6]])) # [1,2,3,4,5,6]

# Memory advantage: generator vs list

import sys
list_mem = [Link]([x**2 for x in range(10000)])
gen_mem = [Link](x**2 for x in range(10000))
print(list_mem, gen_mem) # ~87624 120 (generator is tiny!)

4.4 Recursion & Memoization

import sys
[Link](10000) # default is 1000

# Fibonacci — naive (exponential time O(2^n))

def fib_naive(n):
if n <= 1: return n
return fib_naive(n-1) + fib_naive(n-2)

# Fibonacci — memoized (O(n) time, O(n) space)

from functools import lru_cache

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

# Manual memoization
def fib_manual(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_manual(n-1, memo) + fib_manual(n-2, memo)
return memo[n]

# ── Dynamic Programming Patterns ──

# Tabulation (bottom-up) — Fibonacci

def fib_dp(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# Space-optimized Fibonacci
def fib_opt(n):
a, b = 0, 1
for _ in range(n): a, b = b, a + b
return a

# Coin Change (classic DP)

def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

coin_change([1, 5, 10, 25], 36) # 3 (25+10+1)

# Longest Common Subsequence

def lcs(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]

lcs('ABCBDAB', 'BDCAB') # 4 (BCAB or BDAB)

SECTION 5: Memory Management in Python
5.1 Stack vs Heap
Stack: function call frames, local variables, references. Heap: actual objects (lists, dicts, class
instances). Python variables are references on the stack pointing to objects on the heap.

import sys

# Every Python object has: identity (id), type, value, reference count
x = [1, 2, 3]
y = x # y and x reference the SAME object on the heap
id(x) == id(y) # True

y = [Link]() # now y is a different object

id(x) == id(y) # False

# Object sizes
[Link](42) # 28 bytes (int)
[Link]('hello') # 54 bytes
[Link]([1,2,3]) # 88 bytes (list header + 3 pointers)
[Link]({}) # 232 bytes (dict is expensive!)
[Link](set()) # 216 bytes

5.2 Reference Counting & Garbage Collection

import sys, gc

# Reference counting
a = [1, 2, 3] # ref count = 1
b = a # ref count = 2
c = a # ref count = 3
del b # ref count = 2
del c # ref count = 1
del a # ref count = 0 → object is freed immediately

# Check reference count

x = []
[Link](x) # at least 2 (x + argument to getrefcount)

# Circular reference (reference counting FAILS here)

class Node:
def __init__(self): [Link] = None

a = Node()
b = Node()
[Link] = b # a → b
[Link] = a # b → a (cycle!)
del a # ref count stays 1 each, NOT freed
del b # same — gc module cleans these up
 # Garbage collector handles cycles
[Link]() # force collection
gc.get_count() # (gen0, gen1, gen2) object counts
[Link]() # disable cyclic GC (dangerous!)
[Link]() # re-enable

5.3 Memory Profiling

import tracemalloc, sys

# tracemalloc — track memory allocations

[Link]()

# ... your code here ...

data = [i**2 for i in range(100000)]

snapshot = tracemalloc.take_snapshot()
top_stats = [Link]('lineno')
for stat in top_stats[:3]:
print(stat)

[Link]()

# [Link] — shallow size of object

lst = [1, 2, 3, 4, 5]
[Link](lst) # 120 — list container only, not element sizes

# Deep size (custom function)

def deep_sizeof(obj, seen=None):
if seen is None: seen = set()
obj_id = id(obj)
if obj_id in seen: return 0
[Link](obj_id)
size = [Link](obj)
if isinstance(obj, dict):
size += sum(deep_sizeof(k, seen) + deep_sizeof(v, seen) for k, v in
[Link]())
elif hasattr(obj, '__iter__') and not isinstance(obj, (str, bytes)):
size += sum(deep_sizeof(i, seen) for i in obj)
return size

5.4 Memory Optimization Techniques

# 1. __slots__ — eliminate per-instance __dict__
class WithDict:
def __init__(self, x, y): self.x = x; self.y = y

class WithSlots:
__slots__ = ['x', 'y']
def __init__(self, x, y): self.x = x; self.y = y
import sys
d = WithDict(1, 2); s = WithSlots(1, 2)
[Link](d.__dict__) # 232 bytes
# WithSlots has no __dict__ — saves ~200 bytes per instance

# 2. Generators vs Lists (for large datasets)

gen = (x**2 for x in range(1_000_000)) # 120 bytes
lst = [x**2 for x in range(1_000_000)] # ~8 MB!

# 3. array module — typed arrays (like C arrays)

import array
arr = [Link]('i', range(1000)) # int array — ~4 bytes each vs 28 for Python
int

# 4. Shallow vs deep copy

import copy
original = [[1,2],[3,4],[5,6]]
shallow = [Link]() # or list(original) or original[:]
deep = [Link](original)
original[0][0] = 99
print(shallow[0][0]) # 99 (shared inner list!)
print(deep[0][0]) # 1 (fully independent copy)

# 5. intern strings for repeated lookups

import sys
a = [Link]('frequently_used_key')
b = [Link]('frequently_used_key')
a is b # True — same object in memory
SECTION 6: Data Manipulation & Mining
6.1 File I/O
# Reading files
with open('[Link]', 'r') as f:
content = [Link]() # entire file as string

with open('[Link]', 'r') as f:

lines = [Link]() # list of lines

with open('[Link]', 'r') as f:

for line in f: # memory-efficient line by line
print([Link]())

# Writing files
with open('[Link]', 'w') as f: # overwrite
[Link]('Hello\n')

with open('[Link]', 'a') as f: # append

[Link]('World\n')

# CSV
import csv
with open('[Link]', 'r') as f:
reader = [Link](f) # each row = dict
rows = list(reader)

with open('[Link]', 'w', newline='') as f:

writer = [Link](f, fieldnames=['name','age'])
[Link]()
[Link]([{'name':'Alice','age':30}])

# JSON
import json
with open('[Link]', 'r') as f:
data = [Link](f) # file → Python object

with open('[Link]', 'w') as f:

[Link](data, f, indent=2) # Python object → file

json_str = [Link]({'key': 'val'}) # dict → JSON string

obj = [Link](json_str) # JSON string → dict

6.2 Regex
import re

text = 'Contact us at alice@[Link] or bob@[Link]'

# Search — first match

 m = [Link](r'\w+@\w+\.\w+', text)
[Link]() # 'alice@[Link]'

# Find all matches

emails = [Link](r'[\w.-]+@[\w.-]+\.\w+', text)
# ['alice@[Link]', 'bob@[Link]']

# Match at start of string

[Link](r'Contact', text) # match object
[Link](r'alice', text) # None

# Replace
clean = [Link](r'\s+', ' ', 'too many spaces') # 'too many spaces'

# Split
[Link](r'[,;\s]+', 'a, b;c d') # ['a','b','c','d']

# Groups
m = [Link](r'(\w+)@(\w+)\.(\w+)', text)
[Link](0) # 'alice@[Link]'
[Link](1) # 'alice'
[Link](2) # 'example'

# Common patterns
r'\d+' # one or more digits
r'\w+' # word characters (letters, digits, _)
r'\s+' # whitespace
r'^...$' # anchors: start and end of string
r'[a-zA-Z]+' # letters only
r'(?i)pattern' # case-insensitive

6.3 NumPy
import numpy as np

# Creating arrays
a = [Link]([1, 2, 3, 4, 5])
b = [Link]((3, 4)) # 3x4 matrix of zeros
c = [Link]((2, 3)) # 2x3 matrix of ones
d = [Link](0, 10, 2) # [0 2 4 6 8]
e = [Link](0, 1, 5) # [0. .25 .5 .75 1.]
r = [Link](3, 3) # 3x3 random floats

# Indexing & slicing

arr = [Link]([[1,2,3],[4,5,6],[7,8,9]])
arr[1, 2] # 6
arr[:, 1] # [2, 5, 8] (column 1)
arr[0:2, :] # first 2 rows
arr[arr > 4] # boolean indexing: [5,6,7,8,9]

# Vectorized operations (NO loops needed)

arr * 2 # multiply every element
arr + 10 # add to every element
 arr ** 2 # square every element
[Link](arr) # element-wise sqrt

# Matrix operations
A = [Link]([[1,2],[3,4]])
B = [Link]([[5,6],[7,8]])
A @ B # matrix multiply [[19,22],[43,50]]
A.T # transpose [[1,3],[2,4]]
[Link](A, B) # same as A @ B

# Statistics
[Link](arr) # mean
[Link](arr) # standard deviation
[Link](arr) # minimum
[Link](arr) # index of maximum
[Link](arr, axis=0) # sum along columns
[Link](arr, axis=1) # sort each row

6.4 Pandas
import pandas as pd

# Create DataFrame
df = [Link]({
'name': ['Alice','Bob','Charlie','Diana'],
'age': [25, 30, 35, 28],
'score':[95, 80, 85, 92]
})

# Inspection
[Link](2) # first 2 rows
[Link](2) # last 2 rows
[Link]() # dtypes, nulls
[Link]() # statistics
[Link] # (4, 3)
[Link] # Index(['name','age','score'])

# Selection
df['name'] # Series (column)
df[['name','score']] # DataFrame (multiple columns)
[Link][0] # row 0 by index
[Link][1:3, 0:2] # rows 1-2, cols 0-1
[Link][df['age'] > 28] # filter rows

# Filtering
df[df['score'] >= 90]
df[(df['age'] > 25) & (df['score'] > 85)]

# Adding / transforming columns

df['grade'] = df['score'].apply(lambda x: 'A' if x>=90 else 'B')
df['age_sq'] = df['age'] ** 2

# GroupBy
[Link]('grade')['score'].mean()
[Link]('grade').agg({'score': ['mean','max'], 'age': 'min'})

# Handling nulls
[Link]().sum() # count nulls per column
[Link]() # drop rows with any null
[Link](0) # fill nulls with 0
df['age'].fillna(df['age'].mean(), inplace=True)

# Merge / Join
df2 = [Link]({'name':['Alice','Bob'], 'dept':['Eng','HR']})
merged = [Link](df, df2, on='name', how='left') # left join

# Sort
df.sort_values('score', ascending=False)
df.sort_values(['grade','score'], ascending=[True, False])
SECTION 7: Algorithms & Complexity
7.1 Big O Notation
Big O describes worst-case time or space growth as input size n grows. Always analyze the dominant
term.

# O(1) — constant: hash lookup, list append

# O(log n)— logarithmic: binary search, balanced BST
# O(n) — linear: linear scan, one loop
# O(n log n) — linearithmic: merge sort, heap sort
# O(n^2) — quadratic: nested loops, bubble sort
# O(2^n) — exponential: naive recursion, subsets
# O(n!) — factorial: permutations

# Example analysis
def example(lst): # O(n^2)
for i in range(len(lst)): # O(n)
for j in range(len(lst)): # O(n)
pass

# Space complexity
def reverse(lst): # O(n) space
return lst[::-1] # creates new list

def reverse_inplace(lst): # O(1) space

l, r = 0, len(lst) - 1
while l < r:
lst[l], lst[r] = lst[r], lst[l]
l += 1; r -= 1

7.2 Sorting Algorithms

# Bubble Sort — O(n^2) time, O(1) space
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

# Merge Sort — O(n log n) time, O(n) space

def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
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
return result + left[i:] + right[j:]

# Quick Sort — O(n log n) avg, O(n^2) worst, O(log n) space

def quick_sort(arr):
if len(arr) <= 1: return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)

# Heap Sort — O(n log n) time, O(1) space

import heapq
def heap_sort(arr):
h = [Link]()
[Link](h)
return [[Link](h) for _ in range(len(h))]

7.3 Searching Algorithms

# Linear Search — O(n)
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target: return i
return -1

# Binary Search — O(log n) — requires SORTED array

def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1

# Binary search — find insertion point

import bisect
arr = [1, 3, 5, 7, 9]
bisect.bisect_left(arr, 5) # 2 (leftmost position for 5)
bisect.bisect_right(arr, 5) # 3 (rightmost position for 5)
[Link](arr, 4) # inserts 4 in sorted order

# Binary search on answer (search space is a range of values)

def min_days_to_eat_oranges(n):
# Can eat 1, or n//2, or n//3 per day
from functools import lru_cache
@lru_cache(maxsize=None)
 def dp(n):
if n <= 1: return n
return 1 + min(n % 2 + dp(n//2), n % 3 + dp(n//3))
return dp(n)

7.4 Two Pointers & Sliding Window

# Two Pointers — pair sum in sorted array O(n)
def two_sum_sorted(arr, target):
l, r = 0, len(arr) - 1
while l < r:
s = arr[l] + arr[r]
if s == target: return (l, r)
elif s < target: l += 1
else: r -= 1
return None

# Two pointers — remove duplicates in-place O(n)

def remove_dupes(arr):
if not arr: return 0
slow = 0
for fast in range(1, len(arr)):
if arr[fast] != arr[slow]:
slow += 1
arr[slow] = arr[fast]
return slow + 1

# Sliding Window — max sum subarray of size k O(n)

def max_sum_window(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i-k] # slide window
max_sum = max(max_sum, window_sum)
return max_sum

# Sliding Window — longest substring without repeating O(n)

def length_of_longest_substring(s):
seen = {}
left = max_len = 0
for right, char in enumerate(s):
if char in seen and seen[char] >= left:
left = seen[char] + 1 # shrink window
seen[char] = right
max_len = max(max_len, right - left + 1)
return max_len

7.5 Backtracking
# Template for backtracking
def backtrack(state, choices):
if is_solution(state):
record(state)
return
for choice in choices:
if is_valid(choice, state):
make_choice(state, choice)
backtrack(state, next_choices(state))
undo_choice(state, choice) # KEY: backtrack

# Permutations of a list
def permutations(nums):
result = []
def bt(path, remaining):
if not remaining:
[Link](path[:]); return
for i, num in enumerate(remaining):
[Link](num)
bt(path, remaining[:i] + remaining[i+1:])
[Link]()
bt([], nums)
return result

# Subsets / Power Set

def subsets(nums):
result = []
def bt(start, current):
[Link](current[:])
for i in range(start, len(nums)):
[Link](nums[i])
bt(i + 1, current)
[Link]()
bt(0, [])
return result

# N-Queens
def solve_n_queens(n):
result = []
cols = set(); diag1 = set(); diag2 = set()
board = [['.']*n for _ in range(n)]
def bt(row):
if row == n:
[Link]([''.join(r) for r in board]); return
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2: continue
[Link](col); [Link](row-col); [Link](row+col)
board[row][col] = 'Q'
bt(row + 1)
board[row][col] = '.'
[Link](col); [Link](row-col); [Link](row+col)
bt(0)
return result
SECTION 8: Advanced Topics
8.1 Type Hints
from typing import List, Dict, Tuple, Optional, Union, Callable, Any, TypeVar
from typing import Set, FrozenSet, Sequence, Iterable, Generator

# Basic annotations
def greet(name: str) -> str:
return f'Hello, {name}'

def process(items: List[int], limit: int = 10) -> Dict[str, int]:

return {str(i): i for i in items[:limit]}

# Optional — value or None

def find_user(user_id: int) -> Optional[str]:
users = {1: 'Alice', 2: 'Bob'}
return [Link](user_id) # returns str or None

# Union — one of several types

def stringify(val: Union[int, float, str]) -> str:
return str(val)

# Python 3.10+ — use | instead of Union

def new_style(val: int | float | None) -> str:
return str(val) if val else 'none'

# TypeVar — generic functions

T = TypeVar('T')
def first(items: List[T]) -> Optional[T]:
return items[0] if items else None

# Callable type
def apply(func: Callable[[int, int], int], a: int, b: int) -> int:
return func(a, b)

8.2 Context Managers

# Class-based context manager
class Timer:
import time
def __enter__(self):
[Link] = __import__('time').perf_counter()
return self
def __exit__(self, exc_type, exc_val, exc_tb):
[Link] = __import__('time').perf_counter() - [Link]
print(f'Elapsed: {[Link]:.4f}s')
return False # don't suppress exceptions

with Timer() as t:
total = sum(range(1_000_000))
 # Elapsed: 0.0312s

# Generator-based using contextlib

from contextlib import contextmanager

@contextmanager
def managed_resource(name):
print(f'Opening {name}')
try:
yield name # everything before yield = __enter__
except Exception as e:
print(f'Error: {e}')
finally:
print(f'Closing {name}') # always runs = __exit__

with managed_resource('DB Connection') as r:

print(f'Using {r}') # Opening ... Using ... Closing ...

8.3 Async / Await

import asyncio

# Basic coroutine
async def fetch_data(url: str) -> str:
await [Link](1) # non-blocking wait (simulating I/O)
return f'Data from {url}'

# Run multiple tasks concurrently

async def main():
# Sequential — slow (2 seconds total)
r1 = await fetch_data('url1')
r2 = await fetch_data('url2')

# Concurrent — fast (1 second total)

r1, r2 = await [Link](
fetch_data('url1'),
fetch_data('url2')
)
return r1, r2

[Link](main())

# Async with real HTTP (aiohttp)

# import aiohttp
# async def fetch(session, url):
# async with [Link](url) as resp:
# return await [Link]()

# async def fetch_all(urls):

# async with [Link]() as session:
# tasks = [fetch(session, url) for url in urls]
# return await [Link](*tasks)
 # Async iterator
class AsyncRange:
def __init__(self, stop): [Link] = 0; [Link] = stop
def __aiter__(self): return self
async def __anext__(self):
if [Link] >= [Link]: raise StopAsyncIteration
val = [Link]; [Link] += 1
await [Link](0) # yield control
return val

8.4 Multithreading & Multiprocessing

import threading, [Link], multiprocessing

# Threading — good for I/O-bound tasks (network, file I/O)

# GIL prevents true parallel CPU execution in threads
def worker(n, results, idx):
results[idx] = n * n

results = [0] * 5
threads = [[Link](target=worker, args=(i, results, i)) for i in range(5)]
for t in threads: [Link]()
for t in threads: [Link]()
print(results) # [0, 1, 4, 9, 16]

# ThreadPoolExecutor — easier interface

with [Link](max_workers=4) as ex:
futures = [[Link](lambda x: x**2, i) for i in range(5)]
results = [[Link]() for f in futures]

# Multiprocessing — true parallelism for CPU-bound tasks

def cpu_task(n):
return sum(i**2 for i in range(n))

with [Link](processes=4) as pool:

results = [Link](cpu_task, [10000, 20000, 30000, 40000])

# ProcessPoolExecutor
with [Link]() as ex:
results = list([Link](cpu_task, [1000, 2000, 3000]))

# Thread-safe data sharing

lock = [Link]()
counter = 0
def safe_increment():
global counter
with lock: # acquire and release automatically
counter += 1
8.5 Metaclasses
# type is the default metaclass of all classes
MyClass = type('MyClass', (object,), {'x': 10, 'greet': lambda self: 'hi'})
obj = MyClass()
[Link]() # 'hi'

# Custom metaclass
class SingletonMeta(type):
_instances = {}
def __call__(cls, *args, **kwargs):
if cls not in cls._instances:
cls._instances[cls] = super().__call__(*args, **kwargs)
return cls._instances[cls]

class Database(metaclass=SingletonMeta):
def __init__(self):
[Link] = 'connected'

db1 = Database()
db2 = Database()
db1 is db2 # True — same instance!

# __new__ vs __init__
class ImmutablePoint:
def __new__(cls, x, y): # controls object creation
instance = super().__new__(cls)
return instance
def __init__(self, x, y): # initializes object
self._x = x; self._y = y
def __setattr__(self, name, val):
if [Link]('_'):
super().__setattr__(name, val)
else:
raise AttributeError('Immutable!')
SECTION 9: Built-in Python Tools
9.1 collections Module
from collections import Counter, defaultdict, OrderedDict, deque, namedtuple

# Counter — frequency counting

c = Counter('abracadabra')
# Counter({'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1})
c.most_common(3) # [('a',5),('b',2),('r',2)]
c['a'] += 1 # increment
c1 + c2 # merge counters
c1 - c2 # subtract (removes zeros/negatives)

# defaultdict — auto-creates missing keys

dd = defaultdict(list)
dd['key'].append(1) # no KeyError — auto-creates empty list
dd['key'].append(2)
# dd = {'key': [1, 2]}

dd_int = defaultdict(int) # default 0

dd_set = defaultdict(set) # default empty set
dd_dict = defaultdict(dict) # default empty dict

# Group items by key — common pattern

words = ['apple','ant','bat','banana','cherry']
groups = defaultdict(list)
for w in words:
groups[w[0]].append(w)
# {'a':['apple','ant'], 'b':['bat','banana'], 'c':['cherry']}

# deque — O(1) at both ends

from collections import deque
d = deque([1,2,3])
[Link](0) # [0,1,2,3]
[Link](4) # [0,1,2,3,4]
[Link]() # 0 — O(1)
[Link](2) # [3,4,1,2] — rotate right by 2

# namedtuple
Point = namedtuple('Point', ['x','y'])
p = Point(3, 4)
p.x, p.y # 3, 4
p._asdict() # OrderedDict([('x',3),('y',4)])
p._replace(x=10) # Point(x=10, y=4)

9.2 itertools
import itertools

# Combinations & Permutations

 list([Link]('ABC', 2))
# [('A','B'),('A','C'),('B','C')]

list([Link]('ABC', 2))
# [('A','B'),('A','C'),('B','A'),...] — 6 total

list([Link]([0,1], repeat=3))
# all 8 binary combos: (0,0,0),(0,0,1),...

# Chaining iterables
list([Link]([1,2], [3,4], [5,6])) # [1,2,3,4,5,6]

# Groupby — group consecutive elements

data = [('A',1),('A',2),('B',3),('B',4),('C',5)]
for key, group in [Link](data, key=lambda x: x[0]):
print(key, list(group))
# A [('A',1),('A',2)] B [('B',3),('B',4)] ...

# Accumulate — running total

list([Link]([1,2,3,4,5])) # [1,3,6,10,15]
list([Link]([1,2,3,4], max)) # [1,2,3,4] (running max)

# Count, cycle, repeat

counter = [Link](start=10, step=2) # 10,12,14,16,...
cycler = [Link](['R','G','B']) # R,G,B,R,G,B,...
repeater = [Link]('x', 3) # ['x','x','x']

# islice — lazy slicing

first5 = list([Link]([Link](), 5)) # [0,1,2,3,4]

9.3 functools
from functools import lru_cache, partial, reduce, wraps, cache

# lru_cache — memoize function results

@lru_cache(maxsize=128)
def expensive(n):
import time; [Link](0.1)
return n * n

expensive(5) # slow (0.1s)

expensive(5) # instant (cached)
expensive.cache_info() # CacheInfo(hits=1, misses=1, maxsize=128, currsize=1)
expensive.cache_clear() # clear cache

# @cache (Python 3.9+) — unbounded lru_cache

@cache
def fib(n):
if n < 2: return n
return fib(n-1) + fib(n-2)

# partial — fix some arguments of a function

def power(base, exp):
 return base ** exp

square = partial(power, exp=2) # fix exp=2

cube = partial(power, exp=3) # fix exp=3
square(5) # 25
cube(3) # 27

# reduce
reduce(lambda a, b: a * b, [1,2,3,4,5]) # 120

# total_ordering — fill in comparison methods

from functools import total_ordering
@total_ordering
class Student:
def __init__(self, name, gpa): [Link] = name; [Link] = gpa
def __eq__(self, other): return [Link] == [Link]
def __lt__(self, other): return [Link] < [Link]
# __le__, __gt__, __ge__ are auto-generated!
SECTION 10: LeetCode Patterns & Brute Force
10.1 Brute Force Approach
Always write brute force first. It verifies correctness, clarifies the problem, and gives a baseline. Then
optimize.

# Two Sum — Brute Force O(n^2)

def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []

# Two Sum — Optimized O(n) with hash map

def two_sum_opt(nums, target):
seen = {} # val → index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []

# Contains Duplicate — Brute O(n^2)

def has_dup_brute(nums):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] == nums[j]: return True
return False

# Contains Duplicate — Optimized O(n)

def has_dup_opt(nums):
return len(nums) != len(set(nums))

10.2 Prefix Sums

# Subarray Sum Equals K — Brute O(n^2)
def subarray_sum_brute(nums, k):
count = 0
for i in range(len(nums)):
total = 0
for j in range(i, len(nums)):
total += nums[j]
if total == k: count += 1
return count

# Optimized O(n) with prefix sum + hash map

def subarray_sum_opt(nums, k):
count = 0
 prefix = 0
seen = {0: 1} # prefix_sum → count
for num in nums:
prefix += num
# if (prefix - k) was seen, there's a subarray summing to k
count += [Link](prefix - k, 0)
seen[prefix] = [Link](prefix, 0) + 1
return count

# Product of array except self — prefix/suffix O(n)

def product_except_self(nums):
n = len(nums)
result = [1] * n
# prefix products
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# suffix products
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result

10.3 Monotonic Stack

# Next Greater Element O(n)
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # stores indices, monotonically decreasing by value
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
idx = [Link]()
result[idx] = num
[Link](i)
return result

# Largest Rectangle in Histogram O(n)

def largest_rectangle(heights):
stack = [] # monotonic increasing stack
max_area = 0
heights = heights + [0] # sentinel
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
idx, height = [Link]()
max_area = max(max_area, height * (i - idx))
start = idx
[Link]((start, h))
return max_area

# Daily Temperatures — next warmer day O(n)

 def daily_temperatures(temps):
result = [0] * len(temps)
stack = [] # indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = [Link]()
result[j] = i - j
[Link](i)
return result

10.4 Union-Find (Disjoint Set Union)

class UnionFind:
def __init__(self, n):
[Link] = list(range(n))
[Link] = [0] * n
[Link] = n

def find(self, x):

if [Link][x] != x:
[Link][x] = [Link]([Link][x]) # path compression
return [Link][x]

def union(self, x, y) -> bool:

px, py = [Link](x), [Link](y)
if px == py: return False # already connected
if [Link][px] < [Link][py]: px, py = py, px
[Link][py] = px
if [Link][px] == [Link][py]: [Link][px] += 1
[Link] -= 1
return True

def connected(self, x, y) -> bool:

return [Link](x) == [Link](y)

# Usage: Number of connected components

def count_components(n, edges):
uf = UnionFind(n)
for u, v in edges:
[Link](u, v)
return [Link]

10.5 Topological Sort

from collections import defaultdict, deque

# Kahn's Algorithm (BFS-based) O(V + E)

def topo_sort(n, prerequisites):
graph = defaultdict(list)
in_deg = [0] * n
 for dest, src in prerequisites:
graph[src].append(dest)
in_deg[dest] += 1

q = deque(i for i in range(n) if in_deg[i] == 0)

order = []
while q:
node = [Link]()
[Link](node)
for nb in graph[node]:
in_deg[nb] -= 1
if in_deg[nb] == 0:
[Link](nb)

return order if len(order) == n else [] # empty if cycle

# Course Schedule II
topo_sort(4, [[1,0],[2,0],[3,1],[3,2]]) # [0,1,2,3] or [0,2,1,3]

# DFS-based topological sort

def topo_dfs(n, edges):
graph = defaultdict(list)
for u, v in edges: graph[u].append(v)
visited, result = set(), []
def dfs(node):
for nb in graph[node]:
if nb not in visited:
[Link](nb); dfs(nb)
[Link](node)
for i in range(n):
if i not in visited:
[Link](i); dfs(i)
return result[::-1]

10.6 Bit Manipulation

# Essential bit tricks
n = 13 # binary: 1101

n & 1 # 1 — check if odd (last bit)

n >> 1 # 6 — divide by 2
n << 1 # 26 — multiply by 2
n & (n-1) # 12 — clear lowest set bit
n & (-n) # 1 — isolate lowest set bit
n ^ n # 0 — XOR with itself
~n # -14 — bitwise NOT

# Count set bits (popcount)

bin(n).count('1') # 3
n.bit_count() # 3 (Python 3.10+)

def count_bits(n):
count = 0
 while n:
n &= n - 1 # clears lowest set bit
count += 1
return count

# Single Number — find the one non-duplicate O(n), O(1) space

def single_number(nums):
result = 0
for n in nums: result ^= n # XOR cancels pairs
return result

# Power of two
def is_power_of_two(n):
return n > 0 and (n & (n-1)) == 0

# Get / set / clear / toggle bit at position i

def get_bit(n, i): return (n >> i) & 1
def set_bit(n, i): return n | (1 << i)
def clear_bit(n, i): return n & ~(1 << i)
def toggle_bit(n, i): return n ^ (1 << i)
MASTER PATTERN CHEAT SHEET
Problem Type → Data Structure / Algorithm

Problem Pattern Use This Approach

Find pair summing to target Hash map / Two pointers (sorted)
Longest subarray/substring Sliding window + hash map
Subarray sum equals k Prefix sum + hash map
Top K frequent elements Max-heap or Counter.most_common
Shortest path (unweighted) BFS
Shortest path (weighted) Dijkstra (heapq)
All paths / DFS exploration DFS + backtracking
Detect cycle in graph DFS with color / Union-Find
Course scheduling (ordering) Topological sort (Kahn's)
Connected components Union-Find or BFS/DFS
Next greater/smaller element Monotonic stack
Find duplicate / missing num XOR bit tricks / index marking
Overlapping subproblems Dynamic programming (memoize/tabulate)
All subsets / combinations Backtracking
Binary search on value/answer Binary search on answer space
Merge k sorted lists Min-heap of (val, list_idx, elem_idx)
Stream median Two heaps (max-heap + min-heap)
String pattern matching Sliding window + Counter
Matrix path / island count BFS/DFS on grid
Palindrome check Two pointers from center
Anagram groups Sort string as key → defaultdict
LRU Cache OrderedDict or doubly linked list + hash
Trie / prefix search Trie data structure
Range sum queries Prefix sum array / Fenwick tree

Big O Quick Reference

Operation Time Complexity
list[i] / dict[k] / set has k O(1)
[Link]() / [Link]() O(1) amortized
[Link](i) / [Link](i) O(n)
dict/set add/remove/lookup O(1) average
heappush / heappop O(log n)
heapify (build heap) O(n)
Binary search O(log n)
sorted() / [Link]() O(n log n)
BFS / DFS on graph O(V + E)
Union-Find (amortized) O(α(n)) ≈ O(1)
String concatenation in loop O(n²) — use join()!
Nested list comprehension O(n * m)

🎯 THE GOLDEN RULE: Write brute force first → verify it's correct → identify the bottleneck (usually a
nested loop or repeated work) → eliminate it with the right data structure or algorithm pattern from this
guide.
📖 HOW TO USE THIS REFERENCE
This section is your quick-recall layer. For every concept in the guide, you get:

What it is — plain English definition of the concept

Why it exists — the problem it solves
When to use it — the trigger — when should this pop into your head?
Key behaviour — the most important things to remember about how it works
Common mistake — the thing everyone gets wrong the first time
Code hook — the one-liner or pattern you'll actually type

🎯 Goal
After reading this section you should be able to hear a problem description and immediately think:
'That's a sliding window' or 'That needs a heap' — without looking anything up.
SECTION 1 NOTES — Python Fundamentals
Variables & Types
Dynamic typing — Python figures out the type at runtime — you never declare int x, just x = 5
Everything is an object — Even int and bool are objects with methods. 5 .bit_length() works.
None — The absence of a value. Like null in other languages. Always check with 'is None' not '== None'
Falsy values — False, 0, 0.0, '', [], {}, set(), None all evaluate False in a boolean context
Truthy — Everything else is True. Non-empty string, non-zero number, non-empty list
id() — Returns the memory address of an object. Use to check if two variables point to the same object

String Key Facts

Immutable — You can't change a string in place. s[0] = 'X' raises TypeError. Create a new string instead.
f-strings — f'Hello {name}' — fastest and most readable way to embed variables. Use these always.
Slicing s[start:stop:step] — stop is EXCLUSIVE. s[1:4] gives indices 1,2,3. s[::-1] reverses.
join() over + — ''.join(list) is O(n). Concatenating with + in a loop is O(n²) because strings are immutable.
strip/split/replace — The three most-used string methods. strip() removes whitespace, split() tokenizes,
replace() swaps.

Operators — The Tricky Ones

// floor division — Always rounds DOWN toward negative infinity. -7 // 2 = -4, not -3
% modulo — Result has same sign as divisor in Python. -7 % 2 = 1 (not -1 like in C/Java)
** exponent — 2**10 = 1024. Use instead of [Link]() for integers.
is vs == — 'is' checks identity (same object in memory). '==' checks equality (same value). Always use ==
for values.
in operator — Works on strings, lists, dicts (checks keys), sets, tuples. O(1) for sets/dicts, O(n) for lists.
Walrus := — Assign and test in one expression. if (n := len(data)) > 10: — avoids calling len() twice.
Bitwise & | ^ ~ << >> — Work on individual bits of integers. Used heavily in LeetCode bit
manipulation problems.

Control Flow
range(stop) — Generates 0 to stop-1. range(5) → 0,1,2,3,4. Lazy — doesn't build a list.
range(start,stop,step) — range(10,0,-1) counts down. range(0,20,3) skips by 3.
enumerate(iterable) — Gives you (index, value) pairs. Use instead of range(len(lst)) to avoid off-by-one
bugs.
zip(a,b) — Pairs elements from multiple iterables. Stops at the shortest. Use zip_longest from itertools to
keep all.
break — Exits the innermost loop immediately.
continue — Skips the rest of this iteration and goes to the next one.
pass — Does nothing — a placeholder when syntax requires a block but you have no code yet.
else on loops — for...else / while...else — the else runs only if the loop completed WITHOUT a break.
Comprehensions
List comp [x for x in iterable if condition] — Fastest way to build a list. More readable than
map/filter for simple cases.
Dict comp {k:v for k,v in items} — Build a dict in one line. Great for inverting a dict: {v:k for k,v in
[Link]()}
Set comp {x for x in iterable} — Like list comp but deduplicates automatically.
Generator (x for x in iterable) — Like list comp but LAZY — computes one item at a time. Use for
large data.
Nested comp — [x for row in matrix for x in row] — flattens 2D to 1D. Read left to right like nested for loops.

⚡ Quick Recall — Fundamentals

str = immutable | list = mutable | None check with 'is' | falsy: 0 '' [] {} None False | f-strings always |
join() not + | enumerate() not range(len()) | generator () saves memory vs list []
SECTION 2 NOTES — Data Structures
List
What — Ordered, mutable, allows duplicates. The Python workhorse.
Access — O(1) by index. O(n) to search by value.
append() — O(1) amortized — add to end. The fast way.
insert(i, val) — O(n) — has to shift everything after index i. Slow for front.
pop() — O(1) — remove last. pop(0) is O(n) — use deque for that.
sort() vs sorted() — sort() mutates in place, returns None. sorted() returns new list, original unchanged.
key= param — sorted(lst, key=lambda x: x[1]) — sort by second element. Works on any attribute.
Slicing copies — lst[1:3] creates a NEW list. Modifying it doesn't affect original.
When to use — Default sequence. Use when you need ordered, indexed, mutable data.

Tuple
What — Ordered, immutable, hashable. A frozen list.
Hashable — Can be used as dict keys or set elements because it can't change.
Unpacking — a, b, c = (1,2,3) — cleaner than indexing. Works anywhere in assignments.
*rest unpacking — first, *rest = (1,2,3,4) — rest = [2,3,4]. Grab the tail.
When to use — Return multiple values from a function. Fixed data that shouldn't change. Dict keys that are
coordinates.

Dictionary
What — Key-value store. Hash table under the hood. O(1) average for all ops.
get(key, default) — Returns default instead of raising KeyError. Use this over d[key] when key might be
missing.
setdefault(key, default) — Sets the key to default if missing AND returns it. Useful for grouping.
[Link]() — Returns (key,value) pairs. Most common way to iterate a dict.
Counter — Specialized dict for counting. Counter('hello') → {'l':2,'h':1,'e':1,'o':1}
defaultdict — Never raises KeyError. Specify a factory: defaultdict(list) auto-creates [] for missing keys.
Order preserved — Python 3.7+ — dicts remember insertion order.
When to use — Any time you need fast lookup by a meaningful key. Grouping. Frequency counting.
Memoization.

Set
What — Unordered, unique elements. Hash table with no values.
O(1) lookup — The whole point. 'x in my_set' is O(1). 'x in my_list' is O(n).
No duplicates — Adding an existing element does nothing. Great for deduplication.
Set operations — | union & intersection - difference ^ symmetric difference. Very fast.
frozenset — Immutable set. Can be used as dict key or in another set.
When to use — Deduplication. Membership testing. Finding common/unique elements between collections.
Stack
What — Last In First Out (LIFO). Think: undo history, function call stack.
Use a list — append() to push, pop() to pop. Both O(1). That's all you need.
Peek — stack[-1] — look at top without removing.
When to use — Balanced parentheses problems. DFS. Expression evaluation. Monotonic stack patterns.

Queue
What — First In First Out (FIFO). Think: waiting line, BFS frontier.
Use deque — [Link]. appendleft/popleft are O(1). [Link](0) is O(n) — never use that for queues.
BFS pattern — Always. Put start node in queue, process level by level.
When to use — BFS. Level-order tree traversal. Task scheduling. Sliding window (with maxlen).

Heap (Priority Queue)

What — A tree-shaped structure where the smallest element is always at the root.
heapq — Python only has MIN-heap. heappush/heappop are O(log n).
Max-heap trick — Negate values: heappush(h, -val). Negate on pop: -heappop(h).
heapify — Build a heap from a list in O(n) — faster than n individual pushes.
Tuple ordering — (priority, value) — tuples compared element by element, so priority comes first.
When to use — K largest/smallest. Merge K sorted lists. Dijkstra. Median of data stream. Job scheduling.

Linked List
What — Nodes each holding a value and a pointer to the next node.
O(1) insert/delete at head — Just update the pointer. No shifting like arrays.
O(n) access by index — Must walk from head. No random access.
Two-pointer techniques — Fast/slow pointers for cycle detection, finding middle, kth from end.
Dummy head node — Create a ListNode(0) as a fake head to simplify edge cases in manipulation problems.
When to use — LeetCode gives you ListNode. Real world: when inserts/deletes at arbitrary positions are
frequent.

Binary Tree
What — Each node has at most 2 children (left, right).
Inorder L→N→R — For BST gives SORTED order. Key insight for many BST problems.
Preorder N→L→R — Use to serialize/copy a tree. Root comes first.
Postorder L→R→N — Use for deletion, calculating subtree sizes. Children before parent.
BFS level order — Use a deque. Process queue level by level. len(queue) trick snapshots each level's
size.
Height/depth — Recursive: 1 + max(height(left), height(right)). Base: height(None) = 0.
BST property — Left < Node < Right. Enables O(log n) search when balanced.
When to use — Hierarchical data. BST for sorted dynamic data. Heaps built on array representation.
Graph
What — Nodes (vertices) connected by edges. Can be directed or undirected, weighted or unweighted.
Adjacency list — Dict of {node: [neighbors]}. Space O(V+E). Use for sparse graphs (most LeetCode
problems).
BFS — Uses queue. Finds SHORTEST PATH in unweighted graphs. Explores layer by layer.
DFS — Uses stack (or recursion). Explores as deep as possible before backtracking.
visited set — ALWAYS track visited nodes in graph traversal or you'll loop forever on cycles.
When to use — BFS = shortest path, level-based problems. DFS = path existence, cycle detection,
topological sort.

⚡ Quick Recall — Which Structure?

Need fast lookup? → dict or set | Order matters? → list or deque | Priority? → heapq | Unique items?
→ set | LIFO? → list as stack | FIFO? → deque | Neighbors? → adjacency list dict
SECTION 3 NOTES — Object-Oriented
Programming
Classes & Objects
class — Blueprint. Defines structure and behaviour. Not executed until instantiated.
object / instance — The actual thing created from the class. dog = Dog('Rex') — dog is the instance.
self — Reference to the current instance. Always first parameter of instance methods. Python passes it
automatically.
__init__ — Constructor. Runs when you create an instance. Sets up instance variables.
Instance variable (self.x) — Belongs to ONE instance. Each object has its own copy.
Class variable (ClassName.x) — Shared across ALL instances. Change it once and all instances see it.
@classmethod — Receives the class (cls) not instance (self). Used for alternative constructors.
@staticmethod — Receives nothing special. Just a regular function namespaced inside the class.

Inheritance
What — Child class gets all methods and attributes of parent. Reuse code, extend behaviour.
super() — Call the parent class's version of a method. Essential in __init__ to run parent setup.
Method overriding — Define same method name in child — child version runs instead of parent's.
MRO (Method Resolution Order) — Python looks for a method: class itself → parents left to right →
object. Use ClassName.__mro__ to see it.
Multiple inheritance — class C(A, B) — C inherits from both. MRO determines which method wins.
isinstance(obj, Class) — Returns True if obj is instance of Class OR any subclass. More flexible than
type().

Encapsulation
What — Hiding internal state, exposing only what's needed. Reduces accidental bugs.
_single_underscore — Convention: 'protected'. Not enforced. Means 'please don't touch this from outside'.
__double_underscore — Name mangling. _ClassName__attr. Harder (not impossible) to access from
outside. True hiding.
@property — Turn a method into an attribute-style access. [Link] not obj.get_radius().
@[Link] — Validate before setting. Raise ValueError if invalid. Keep data consistent.

Abstraction
What — Define WHAT something does, not HOW. Force subclasses to implement details.
ABC + @abstractmethod — from abc import ABC, abstractmethod. Class can't be instantiated until all
abstract methods are implemented.
Interface pattern — Define abstract methods in base class. Each subclass implements them differently.
When to use — Building frameworks, plugin systems, any time you want to enforce a contract.
Dunder (Magic) Methods — The Important Ones
__str__ — str(obj) or print(obj). Human-readable string. This is what users see.
__repr__ — repr(obj). Developer-readable. Should ideally let you recreate the object: 'Point(x=3, y=4)'
__len__ — len(obj). Makes your class work with len().
__eq__ — obj == other. Without this, == checks identity (is), not equality.
__hash__ — hash(obj). Required to use object as dict key or in a set. If you define __eq__ you MUST define
__hash__.
__lt__ __gt__ — Comparison operators. With @total_ordering you only need __eq__ and __lt__, rest are
auto-generated.
__add__ __mul__ etc — Operator overloading. Makes your objects work with + * - etc.
__contains__ — 'x in obj'. Makes your class work with the 'in' operator.
__iter__ + __next__ — Makes your class iterable. Can use in for loops.
__enter__ + __exit__ — Context manager protocol. Makes your class work with 'with' statement.
__getitem__ — obj[key]. Makes your class subscriptable like a list or dict.

⚡ Quick Recall — OOP

class = blueprint | self = current instance | __init__ = constructor | _x = convention-private | __x =
name-mangled | @property = getter | super() = call parent | ABC = force subclass contract | __eq__ +
__hash__ always together
SECTION 4 NOTES — Functional & Dynamic
Programming
Lambda Functions
What — Anonymous (nameless) function defined inline. lambda args: expression
Single expression only — Can't have multiple lines, if/else blocks (only ternary), or assignments.
Common use — As key= in sort: sorted(lst, key=lambda x: x[1]). As argument to map/filter.
Don't overuse — Named functions are more readable. Lambda = throwaway one-liners only.

map / filter / reduce

map(func, iterable) — Apply func to every element. Returns lazy iterator — wrap in list() to see results.
filter(func, iterable) — Keep elements where func returns True. Lazy iterator.
reduce(func, iterable) — Fold entire list to one value by repeatedly applying func. Need: from functools
import reduce
List comp is often cleaner — [f(x) for x in lst] vs list(map(f, lst)) — same result, comp is more Pythonic.

Closures
What — Inner function that remembers variables from its enclosing scope, even after outer function returns.
Why — Create functions with 'baked-in' state without using a class.
nonlocal — Use nonlocal x inside inner function to MODIFY (not just read) a variable from outer scope.
Common use — Factory functions: make_adder(5) returns a function that adds 5 to anything.

Decorators
What — A function that wraps another function to add behaviour before/after it runs.
Syntax @decorator — Just syntactic sugar. @timer above def foo is the same as foo = timer(foo).
@[Link](func) — Always put this in your decorator wrapper. Preserves the original function's
name and docstring.
*args **kwargs in wrapper — Always pass *args, **kwargs through so wrapped function still receives its
arguments.
Common uses — Timing, logging, authentication, caching, retry logic, rate limiting.
Stacking decorators — @dec1 @dec2 def foo — applied bottom up: dec1(dec2(foo)). Order matters.

Generators
What — Function that produces values one at a time using yield. Pauses and resumes execution.
Memory efficiency — Generator holds ONE value in memory at a time. List holds ALL. Huge difference for
big data.
yield — Pauses function, sends value out. Next call to next() resumes from that point.
yield from — Delegate to another generator or iterable. Cleaner than looping and re-yielding.
Lazy evaluation — Values computed only when requested. Infinite sequences are possible.
Can only iterate once — Once exhausted, re-iterating gives nothing. Create a new generator if needed.

Recursion
What — Function that calls itself. Solves problems by reducing to smaller versions of the same problem.
Base case — The condition that stops recursion. ALWAYS have one or you get infinite recursion.
Call stack — Each recursive call adds a frame to the stack. Python's default limit is 1000.
[Link]() to raise it.
Think in terms of — 'If I had the answer for n-1, how do I get the answer for n?'
Trust the recursion — Don't trace every call. Assume the recursive call does the right thing, just write the
combination logic.

Memoization / Caching
What — Store results of expensive function calls. Return cached result when same inputs appear again.
@lru_cache(maxsize=None) — The Python built-in. Decorator. maxsize=None means unlimited cache.
@cache (3.9+) — Simpler alias for @lru_cache(maxsize=None). Use this in modern Python.
Manual dict memo — def f(n, memo={}): — but careful, mutable default args are shared across calls.
When to use — Any recursive function where the same inputs recur (overlapping subproblems).

Dynamic Programming
What — Break a problem into overlapping subproblems, solve each once, store results.
Two flavors — Top-down = recursion + memoization. Bottom-up = tabulation (fill a table iteratively).
Memoization (top-down) — Natural — write the recursive solution, add @cache. Easy to reason about.
Tabulation (bottom-up) — Iterative. Fill dp[] from base cases up. Often more space-efficient.
State design — dp[i] means 'answer for subproblem i'. Define what i represents clearly FIRST.
Transition — How do you go from dp[i-1] to dp[i]? This is the recurrence relation.
Space optimization — Often you only need the last 1-2 values. Use variables instead of full array.
When to recognize DP — 'Optimal' + 'count ways' + 'can you achieve X' + overlapping subproblems = try
DP.

⚡ Quick Recall — Functional & DP

lambda = inline func | map/filter = lazy | @decorator = wrap behaviour | yield = pause generator |
memoize = cache repeated calls | DP = overlapping subproblems | top-down = @cache + recursion |
bottom-up = fill dp[] iteratively
SECTION 5 NOTES — Memory Management
Stack vs Heap
Stack — Stores local variables, function call frames, references. Fixed size. Auto-managed. Fast.
Heap — Stores actual objects (lists, dicts, instances). Dynamic size. Garbage collected.
Python variables — Variables are references (pointers on the stack) to objects (on the heap). Not the
objects themselves.
Assignment — x = y makes x point to the SAME object as y. Not a copy.

Reference Counting
What — Python tracks how many variables point to each object. When count hits 0, object is freed.
del x — Decrements the reference count of x's object. If count → 0, memory is freed.
[Link](x) — Shows reference count. Always at least 2 because the function call itself adds one.
Circular references — A → B → A. Both have count > 0 even after del. Reference counting can't free
these.
Cyclic GC — Python's garbage collector (gc module) detects and frees circular references periodically.

Shallow vs Deep Copy

Assignment (=) — NOT a copy. Both variables point to same object. Changing one changes both.
Shallow copy — New outer container, but inner objects are still shared. [Link]() / list[:] / [Link]()
Deep copy — Fully independent copy at all levels. [Link](). Use for nested structures.
Rule of thumb — If your data has no nested mutable objects, shallow copy is fine. Otherwise use deepcopy.

Memory Optimization
__slots__ — Class attribute. Prevents per-instance __dict__. Saves ~200 bytes per instance when you have
millions.
Generator over list — (x for x in data) uses constant memory. [x for x in data] builds full list in RAM.
array module — [Link]('i', data) stores raw C integers. ~4 bytes each vs 28 bytes for Python int object.
[Link]() — Shallow size — size of the container only. Doesn't include nested objects.
tracemalloc — Built-in memory profiler. Start → run code → snapshot → see what allocated the most.
intern strings — [Link]('key') — forces string to be reused from pool. Speeds up string comparison.

⚡ Quick Recall — Memory

= is reference not copy | .copy() = shallow | deepcopy() = full clone | __slots__ = save memory on
many instances | generator = lazy/constant memory | reference count → 0 = freed | gc handles cycles
SECTION 6 NOTES — Data Manipulation &
Mining
File I/O
with open() — ALWAYS use 'with'. Guarantees file is closed even if an error occurs.
'r' 'w' 'a' — r = read | w = write (overwrites!) | a = append | 'rb'/'wb' for binary files
[Link]() — Entire file as one string. Fine for small files.
for line in f — Iterates line by line. Memory efficient for large files — reads one line at a time.
[Link]() — List of lines including \n. Strip with [[Link]() for line in f].

CSV & JSON

[Link] — Each row is a dict keyed by column headers. More useful than plain reader.
[Link](f) — File → Python dict/list.
[Link](obj, f) — Python dict/list → file.
[Link](string) — JSON string → Python object.
[Link](obj) — Python object → JSON string.
indent=2 in dump — Pretty-prints JSON with indentation. Human readable.

Regex (re module)

[Link]() — Find first match ANYWHERE in string. Returns match object or None.
[Link]() — Match only at BEGINNING of string. Often surprises people.
[Link]() — Returns list of all matches. Most commonly used.
[Link]() — Find and replace. [Link](pattern, replacement, string)
[Link]() — Pre-compile a pattern if you'll use it many times. Faster in loops.
Raw strings r'' — ALWAYS use r'' for regex patterns. Avoids double-escaping backslashes.
Common patterns — \d+ = digits | \w+ = word chars | \s+ = whitespace | .* = anything | ^ = start | $ = end
Groups () — Wrap part of pattern in () to capture. [Link](1) gets first captured group.

NumPy
What — Fast array math. Operations run in C, not Python. Vectorized = no Python loops needed.
ndarray — The core object. Typed, fixed-size, multi-dimensional array.
Broadcasting — Lets you do arr + 5 — applies to every element. Works on arrays of compatible shapes.
Boolean indexing — arr[arr > 5] — returns elements matching condition. Very powerful filter.
axis= — Many ops take axis=0 (along rows, down columns) or axis=1 (along columns, across rows).
@ operator — Matrix multiplication. A @ B. Or [Link](A, B).
When to use — Any math-heavy code. Image processing. ML features. Anything with large numerical arrays.
Pandas
DataFrame — 2D table. Rows and columns. Like a spreadsheet or SQL table in Python.
Series — 1D column. Single column of a DataFrame.
iloc vs loc — iloc = integer index position (like list). loc = label-based index name.
df[condition] — Boolean filtering. df[df['age'] > 30] returns rows where age > 30.
groupby() — Split data into groups, apply function, combine results. SQL GROUP BY equivalent.
apply(func) — Apply any function to each row or column. Most flexible but slowest.
merge() — Combine two DataFrames on a key column. Like SQL JOIN.
fillna() / dropna() — Handle missing values. dropna() removes rows with any NaN. fillna(0) replaces
with 0.
When to use — Data analysis, cleaning, CSV/Excel processing, feature engineering for ML.

⚡ Quick Recall — Data

with open() always | [Link] = rows as dicts | [Link]/dumps = string ↔ dict |
[Link]/dump = file ↔ dict | raw strings for regex r'' | numpy = fast vectorized math | pandas =
table/DataFrame operations
SECTION 7 NOTES — Algorithms & Complexity
Big O — How to Think About It
O(1) — Doesn't grow with input. Dict lookup, list append, math ops. Instant.
O(log n) — Halves the search space each step. Binary search. B-tree lookup.
O(n) — One pass through data. Single loop. Unavoidable for many problems.
O(n log n) — Good sorting. Can't do better for comparison-based sort (mathematical proof).
O(n²) — Nested loops over same data. Brute force. Bad for n > 10,000.
O(2ⁿ) — Generate all subsets. Recursive trees. Only feasible for n < 20.
Drop constants — O(2n) = O(n). O(n + 100) = O(n). Only the growth rate matters.
Drop lower terms — O(n² + n) = O(n²). Dominant term wins.
Space complexity — How much extra memory? O(1) = constant extra | O(n) = proportional to input.

Sorting
Python built-in sort — Use sorted() or .sort() in real code. Timsort. O(n log n). Stable. Incredibly
optimized.
Bubble sort — Educational only. O(n²). Never use in production or interviews unless asked.
Merge sort — Divide in half, sort each, merge. O(n log n) guaranteed. O(n) space. Stable.
Quick sort — Pick pivot, partition, recurse. O(n log n) avg, O(n²) worst. O(log n) space. Fastest in practice.
Heap sort — Build heap, pop repeatedly. O(n log n) always. O(1) space. Not stable.
Counting sort — When values are in known small range. O(n + k). Faster than comparison-based sorts.

Searching
Linear search — Check every element. O(n). Use when unsorted or only searching once.
Binary search — REQUIRES SORTED data. Halve search space each step. O(log n). Template: lo/hi/mid.
bisect module — Python's built-in binary search. bisect_left = leftmost position. bisect_right = rightmost.
Binary search on answer — When you can binary search the VALUE space not the array. 'What's the
minimum X such that...'

Two Pointers
What — Two indices moving through data (usually from both ends or at different speeds).
Pair sum in sorted array — Left pointer from start, right from end. Move based on current sum vs
target.
Remove duplicates — Slow pointer = boundary of unique section. Fast pointer scans ahead.
When to use — Sorted arrays. Palindrome check. Container with most water. Three sum.

Sliding Window
What — A contiguous subarray/substring that moves through data. Expand right, shrink left.
Fixed size window — Subtract element leaving, add element entering. O(n) instead of O(n²).
Variable size window — Expand right always, shrink left when window violates constraint.
When to use — Longest/shortest subarray with property. Max/min sum of size k. Substring problems.

BFS vs DFS
BFS (Breadth First Search) — Queue. Level by level. Finds SHORTEST PATH in unweighted graphs.
DFS (Depth First Search) — Stack (or recursion). Goes deep first. Good for path existence, cycle
detection.
BFS space — O(w) where w is max width of graph. Can be large on wide graphs.
DFS space — O(h) where h is depth. Can blow stack on very deep graphs. Use iterative DFS for safety.
Grid BFS — Treat each cell as a node. Neighbors = up/down/left/right. Mark visited immediately when adding
to queue.

Backtracking
What — Try a choice, recurse, undo if it doesn't work. Explore all possibilities.
Template — make choice → recurse → undo choice. The 'undo' is what makes it backtracking.
Pruning — Add conditions to skip invalid paths early. Makes it much faster than brute force.
When to use — Permutations, combinations, subsets, N-Queens, Sudoku, word search on grid.

⚡ Quick Recall — Algorithms

O(n log n) = best sort | Binary search needs sorted | Two pointers = sorted or two speeds | Sliding
window = contiguous subarray | BFS = shortest path | DFS = path exists | Backtracking = try-recurse-
undo
SECTION 8 NOTES — Advanced Topics
Type Hints
What — Annotations that describe the expected types of function inputs and outputs.
Not enforced — Python doesn't check types at runtime. Hints are for humans, IDEs, and mypy linter.
List[int] — A list where all elements are ints. Python 3.9+ can use list[int] directly.
Optional[X] — Means X or None. Same as Union[X, None].
Union[X, Y] — Accepts either type. Python 3.10+ can use X | Y.
Callable[[arg_types], return_type] — For functions passed as arguments.
-> return type — Annotate what the function returns. -> None for no return value.
Why bother — Better autocomplete. Self-documenting code. Catches bugs before runtime.

Context Managers
What — Objects that set up and tear down resources. The 'with' statement guarantees cleanup.
__enter__ — Runs when entering 'with' block. Returns value bound to 'as' variable.
__exit__ — Runs when leaving 'with' block — ALWAYS, even if exception occurs.
@contextmanager — Generator shortcut. Code before yield = enter. Code after yield = exit. Put in try/finally.
Common uses — File handles. DB connections. Locks. Timers. Temporary state changes.
Why — Without it, resources leak if exceptions occur. 'with' guarantees cleanup.

Async / Await
What — Concurrency for I/O-bound tasks. Run other code WHILE waiting for network/disk.
async def — Defines a coroutine. Calling it returns a coroutine object, not the result.
await — Pause this coroutine until the awaited thing completes. Other coroutines can run meanwhile.
[Link]() — Entry point. Run your async main() function from synchronous code.
[Link]() — Run multiple coroutines CONCURRENTLY. Waits for all to finish.
[Link](0) — Yield control to event loop. Let other coroutines run.
NOT parallelism — Only one coroutine runs at a time. The benefit is not blocking during I/O waits.
When to use — Many network requests, file operations, or DB queries happening at once.

Threading vs Multiprocessing
GIL — Global Interpreter Lock. Only one thread executes Python bytecode at a time. True CPU parallelism
blocked.
Threading — Good for I/O-bound tasks (network, file). One thread waits for I/O, others can run.
Multiprocessing — Good for CPU-bound tasks. Each process has its own GIL. True parallelism.
ThreadPoolExecutor — High-level interface. submit() returns a Future. result() blocks until done.
ProcessPoolExecutor — Same interface as ThreadPoolExecutor but uses processes. Slow startup, true
parallelism.
Lock — Prevent race conditions when threads share data. with lock: around critical sections.
Metaclasses
What — The class of a class. type is the default metaclass of all Python classes.
type(name, bases, dict) — Create a class dynamically at runtime without the class keyword.
Custom metaclass — Override __call__ in metaclass to control instance creation.
Singleton pattern — Override __call__ to return the same instance every time.
__new__ vs __init__ — __new__ creates the object (allocation). __init__ initializes it (setup). __new__
runs first.
When to use — Framework code, ORM systems (like Django models), plugin registration, enforcing APIs.

⚡ Quick Recall — Advanced

Type hints = hints not enforcement | context manager = guaranteed cleanup | async = concurrent I/O
not parallel CPU | threading = I/O bound | multiprocessing = CPU bound | GIL = one thread at a time |
metaclass = class of a class
SECTION 9 NOTES — Built-in Python Tools
collections Module
Counter — Counts occurrences. Counter(iterable). .most_common(n) returns top n. Supports +, -, &
operations.
defaultdict — Dict that auto-creates default value for missing keys. Never raises KeyError.
deque — Double-ended queue. O(1) at both ends. Use instead of list for queues and BFS.
OrderedDict — Dict that remembers insertion order and has .move_to_end(). Useful for LRU cache.
namedtuple — Tuple with named fields. Like a lightweight struct. Immutable. Memory efficient.

itertools
combinations(it, r) — All r-length combos without repetition. C(n,r). Order doesn't matter.
permutations(it, r) — All r-length arrangements. P(n,r). Order matters.
product(*its, repeat=n) — Cartesian product. All combinations of elements from multiple iterables.
chain(*its) — Flatten multiple iterables into one lazy stream.
groupby(it, key) — Group consecutive elements by key. Sort first if you want all groups together.
accumulate(it, func) — Running accumulation. Default is addition (running sum). Can pass any binary
function.
islice(it, stop) — Lazy slice of an iterator. First n elements without building full list.

functools
@lru_cache — Memoize. Cache return values keyed by arguments. maxsize=None = unlimited.
@cache — Python 3.9+. Same as @lru_cache(maxsize=None). Simpler syntax.
partial(func, *args) — Pre-fill some arguments of a function. Returns new function.
reduce(func, it) — Fold iterable to single value. reduce(lambda a,b: a+b, [1,2,3,4]) = 10
@total_ordering — Define __eq__ and __lt__, get all other comparison methods free.
@wraps(func) — Use inside decorators to preserve the wrapped function's metadata.

heapq
Min-heap — Always. Python has no built-in max-heap. Use negated values for max behavior.
heappush(h, val) — O(log n). Insert and maintain heap property.
heappop(h) — O(log n). Remove and return smallest element.
heapify(lst) — O(n). Convert list to valid heap in-place. Much faster than n pushes.
h[0] — O(1) peek at minimum without removing.
nsmallest / nlargest — [Link](k, lst). Efficient for small k. Uses heap internally.

bisect
bisect_left(arr, x) — Leftmost index to insert x in sorted arr. If x exists, index of x.
bisect_right(arr, x) — Rightmost index to insert x. If x exists, index after last x.
insort(arr, x) — Insert x into sorted arr maintaining sort. O(n) due to list shift but O(log n) search.
Use case — Binary search with O(log n). Count elements < x with bisect_left.

⚡ Quick Recall — Builtins

Counter = frequency | defaultdict = no KeyError | deque = O(1) both ends | @lru_cache = memoize |
partial = pre-fill args | heapq = min-heap | bisect = binary search on sorted list | itertools = lazy
combos/permutations
SECTION 10 NOTES — LeetCode Patterns
The Universal Thought Process
Step 1 — Understand — Restate in your own words. Ask: sorted? duplicates? null? empty input?
Step 2 — Examples — Walk through 2-3 examples by hand. Include edge cases.
Step 3 — Brute force — Code the naive O(n²) or O(2ⁿ) solution. Get it working and verified.
Step 4 — Identify bottleneck — What's the slowest part? Usually a nested loop or repeated lookups.
Step 5 — Optimize — Replace the bottleneck: nested loop → hash map | repeated search → heap/BST |
subproblems → DP
Step 6 — Verify — Test original examples plus edge cases on the optimized solution.

Pattern Recognition Triggers

'Find pair/triplet that sums to X' — Two pointers (sorted) or hash map. O(n) not O(n²).
'Longest subarray/substring with property' — Sliding window. Expand right, shrink left when
violated.
'Subarray sum equals K' — Prefix sum + hash map. Store running sum, check if (sum - k) seen before.
'Top K elements' — Heap of size k. Max heap for k smallest, min heap for k largest.
'Shortest path between nodes' — BFS on unweighted graph. Dijkstra (heapq) on weighted.
'Can you reach/achieve X?' — BFS/DFS. Dynamic programming if subproblems overlap.
'Count/list all subsets/combos/perms' — Backtracking. Build incrementally, undo on backtrack.
'Next greater/smaller element' — Monotonic stack. Maintain a stack of candidates.
'Find the duplicate / missing number' — XOR trick or index-marking. O(n) time O(1) space.
'Optimal cost over subproblems' — Dynamic programming. Look for overlapping decisions.
'Connected components / cycle detection' — Union-Find or BFS/DFS with visited set.
'Prerequisite ordering' — Topological sort. Kahn's BFS algorithm.

Prefix Sum Pattern — Understand Deeply

What — prefix[i] = sum of all elements from index 0 to i.
Why — Any subarray sum = prefix[r] - prefix[l-1]. O(1) query after O(n) build.
Hash map trick — Store prefix sum → index. If prefix[j] - prefix[i] == k, we found a subarray summing to k.
Code — prefix = 0, seen = {0:1}. For each num: prefix += num. count += [Link](prefix-k, 0). seen[prefix] += 1

Monotonic Stack — Understand Deeply

What — Stack that stays sorted (increasing or decreasing). Pop when order would be violated.
Why — Efficiently find the next greater/smaller element for each position in O(n).
Increasing monotonic — Pop when new element is smaller. Each popped element found its 'next smaller'.
Decreasing monotonic — Pop when new element is larger. Each popped element found its 'next greater'.
Template — for i, val in enumerate(arr): while stack and condition: idx = [Link](); result[idx] = val.
[Link](i)
Union-Find — Understand Deeply
What — Data structure tracking which elements are in the same group (component).
find(x) — Returns the root/representative of x's group. Path compression makes this near O(1).
union(x, y) — Merges x's group and y's group. Returns False if already same group.
Path compression — Make every node point directly to root during find. Flattens the tree.
Union by rank — Always attach smaller tree under larger. Keeps tree flat.
When to use — Number of islands, connected components, detecting redundant connections.

Dynamic Programming Patterns to Memorize

Fibonacci / climbing stairs — dp[i] = dp[i-1] + dp[i-2]
Coin change (min coins) — dp[i] = min(dp[i], dp[i-coin] + 1) for each coin
0/1 Knapsack — dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
Longest common subsequence — dp[i][j] = dp[i-1][j-1]+1 if match, else max(dp[i-1][j], dp[i][j-1])
Longest increasing subsequence — dp[i] = max(dp[j]+1 for j < i if arr[j] < arr[i])
Matrix paths — dp[i][j] = dp[i-1][j] + dp[i][j-1] (count paths to cell)
Word break — dp[i] = any(dp[j] and s[j:i] in wordSet for j < i)

Bit Manipulation Quick Reference

x & 1 — Check if x is odd (last bit is 1)
x >> 1 — Divide by 2 (floor)
x << 1 — Multiply by 2
x & (x-1) — Clear the lowest set bit. Also: if result is 0, x is a power of 2
x ^ x = 0 — XOR of same value cancels. Find single non-duplicate: XOR all elements
x ^ 0 = x — XOR with 0 preserves value
~x = -(x+1) — Bitwise NOT. -1 in two's complement is all 1s
(x >> i) & 1 — Get bit at position i
x | (1 << i) — Set bit at position i
x & ~(1 << i) — Clear bit at position i

Edge Cases — Always Check These

Empty input — [], '', 0, None — what does your function return? Should it error or return a default?
Single element — One item in list, one node in tree/graph. Does your loop/recursion handle this?
All same elements — [5,5,5,5]. Sliding window, two pointers, deduplication — all behave differently.
Negative numbers — Affects min/max, modulo, bit operations. Does your solution assume non-negative?
Integer overflow — Python ints don't overflow (arbitrary precision). Other languages do — good
advantage.
Sorted vs unsorted input — Binary search requires sorted. Two-sum with two pointers requires sorted.
Disconnected graph — BFS/DFS from one node won't visit all — loop over all unvisited nodes.
Null/None tree node — All tree recursions must handle: if not root: return base_value

🏆 Final Mental Model

Every algorithm problem is: WHAT data structure gives me O(1) access to what I need? | Hash map =
O(1) lookup by value | Heap = O(log n) access to min/max | Stack = O(1) access to most recent |
Deque = O(1) at both ends | The right structure eliminates the bottleneck.

End of Python Master Reference Guide

Fundamentals • Data Structures • OOP • Functional/DP • Memory • Data • Algorithms • Advanced • Builtins • LeetCode
Patterns