Stanford CS: Python 3.11 Interactive DSA Cheat Sheet

Basics & Core Mechanics

Essential syntax structures required to construct algorithms without memory leaks or pointer bugs.

Simultaneous Assignment & Swapping

Swap variables or evaluate expressions atomically without an explicit temp variable. Essential for pointer variations.

# Swapping left and right pointers in-place
left, right = 0, len(arr) - 1
arr[left], arr[right] = arr[right], arr[left]

# Unpacking values neatly
x, y, z = [10, 20, 30]

Dividing with Precision Control

DSA indices must always be integers. Avoid fractional index bugs when finding midpoints.

# Float division (Standard)
print(5 / 2)   # Output: 2.5

# Floor division (Truncates fraction, returns int)
mid = 5 // 2   # Output: 2 (Safe for array indexing)

# Modulo (Remainder)
remainder = 5 % 2 # Output: 1

Lists (Dynamic Arrays)

Python lists are dynamic arrays under the hood. Tracking sizing and modification time complexities is key.

Initialization Pitfalls Crucial Rule

Never initialize a 2D matrix using multiplication. It duplicates references to the same inner list row.

# WRONG: Modifying one cell changes the entire column!
matrix = [[0] * cols] * rows 

# CORRECT: Matrix Comprehension (Creates distinct rows)
matrix = [[0] for _ in range(cols)] for _ in range(rows)]

Prof. Advice: Use the identifier `_` for variables you do not plan to read inside loops. It improves readability.

Common Operations O(1) vs O(N)

Adding or removing from the end is fast; inserting or deleting at random indices shifts elements.

arr = [1, 2, 3]
arr.append(4)    # O(1) time - Adds to end -> [1,2,3,4]
arr.pop()        # O(1) time - Removes last -> [1,2,3]

arr.insert(0, 99) # O(N) time - Dangerous! Shifts elements
arr.pop(0)       # O(N) time - Dangerous! Shifts elements

Slicing Engine O(K)

Extract subarrays easily using `[start:stop:step]`. Note that slicing copies elements.

nums = [0, 1, 2, 3, 4, 5]
sub = nums[1:4]    # Elements index 1 to 3 -> [1, 2, 3]
rev = nums[::-1]   # Reverse list completely
clone = nums[:]    # Shallow copy of the list

Strings (Immutable Arrays)

Strings in Python cannot be edited in place. Modifying a character creates a complete copy of the string.

Efficient Modification Pattern O(N) vs O(N²)

Do not update strings inside loops using `+=`. Instead, collect characters in a list and join them at completion.

# SLOW / BAD: Creates new memory allocations continuously
s = ""
for char in arr: s += char 

# FAST / CORRECT: Linear time constructor
chars = []
for char in arr:
    chars.append(char)
result = "".join(chars) # Single O(N) execution

Conversion Tools

Essential syntax for working with ASCII characters, parsing substrings, and validating string types.

# String to Integer conversion
val = int("42")

# ASCII Integer conversion
ascii_val = ord('a') # Returns 97
char_val  = chr(97)  # Returns 'a'

# Properties check
is_alpha = "abc".isalpha() # True
is_digit = "123".isdigit() # True

Dictionaries & Sets (Hash Tables)

Provides $O(1)$ amortized insertion, deletion, and lookup times. Vital for frequency tracking and tracking visited nodes.

Safe Frequency Counter defaultdict

Standard dicts throw a `KeyError` if looking up a missing key. Avoid checking `if key in dict` manually using `collections.defaultdict`.

from collections import defaultdict

# Automatically populates a missing key with an integer (0)
counts = defaultdict(int)

for num in [1, 2, 1, 3, 2, 1]:
    counts[num] += 1 # No KeyError! Safe configuration.

Dictionary Traversals

Iterate safely over keys, values, or key-value structures dynamically.

lookup = {"a": 1, "b": 2}

# Unpacking keys and values together
for key, value in lookup.items():
    print(key, value)

# Standard fallback using default dict values
val = lookup.get("z", 0) # Returns 0 without breaking execution

Sets O(1) Uniqueness

Sets eliminate duplicates and support constant time checks for values.

visited = set()
visited.add(5)

if 5 in visited: # O(1) Lookup complexity
    print("Found")

visited.remove(5) # Throws KeyError if missing
visited.discard(5) # Safe alternative: deletes if present

Deques (Double-Ended Queues)

Essential tool for Breadth-First Searches (BFS) and sliding window patterns. Faster than standard lists for popping items from the front.

FIFO Queue Implementation O(1) Efficiency

Using `list.pop(0)` takes $O(N)$ time. `collections.deque` optimizes insertions and deletions on both ends to $O(1)$ time.

from collections import deque

queue = deque()
queue.append(10)      # Push right
queue.append(20)

first_out = queue.popleft() # O(1) Pop left -> Returns 10

# Also works as an efficient stack
queue.appendleft(5)
last_out = queue.pop()

Heaps / Priority Queues

Binary trees that retrieve the highest or lowest prioritized items in $O(\log N)$ time. Python only provides Min-Heaps natively.

Min-Heap & Max-Heap Core Mechanics O(log N)

To implement a Max-Heap using `heapq`, multiply values by `-1` before pushing them into the heap.

import heapq

heap = []
# Push operation (Min-Heap by default)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 8)

smallest = heapq.heappop(heap) # Returns 1

# Transforming a list into a heap in-place
data = [5, 3, 9, 1]
heapq.heapify(data) # O(N) operational complexity

Control Loops & Pattern Matching

Clean iterative loops and Python 3.11 pattern matching workflows for recursive tree traversals.

Structural Pattern Matching Python 3.11

Replaces legacy nested `if-elif-else` structures. Matches structural layouts, such as evaluating coordinate pairs.

# Simplifies tree node type parsing
match node:
    case None:
        return 0
    case Node(left=None, right=None):
        return node.val
    case Node(left=l_node):
        return node.val + process(l_node)

Clean Loops & Unpacking

Use built-in looping mechanisms like `enumerate` instead of tracking indices manually with separate variables.

names = ["alice", "bob", "charlie"]

# BAD: tracking indices using a manual index variable
# i = 0; for item in names: i += 1

# GOOD: Clean tracking for elements and indices
for idx, name in enumerate(names):
    print(f"Index: {idx}, Target: {name}")

Loop Foundations The Blueprints

The absolute structural rules for iteration. Never forget the colon (:) or the indentation.

# Range Loop: Executes a specific number of times
for i in range(len(arr)):
    print(arr[i]) # Accesses index 0 up to len-1

# While Loop: Executes as long as the statement is True
while left < right:
    # Logic happens here
    left += 1 # Don't forget to update the variable!