1. Arrays & Hashing

Trading memory for time by using Hash Maps or Hash Sets to achieve $O(1)$ lookups.

Techniques: Frequency counting, prefix sums, caching complements
Classic problems:
- Easy: Two Sum
- Hard: Subarray Sum Equals K

Prefix sums

A prefix sum is an array where each element at index $i$ stores the sum of all elements in the original array from index $0$ up to $i$ .

🔑 Main uses cases:
- Finding the sum of a subarray (elements between index $L$ $L$ and index $R$ $R$ ):
  - Brute-force approach: iterate from $L$ to $R$ each time: $O(N)$ time
  - Prefix-sum: $O(N)$ upfront to build the prefix sum array - and then can answer any subarray sum query in $O(1)$ time: $\text{Sum}(L, R) = \text{Prefix}[R] - \text{Prefix}[L-1] \quad \text{(inclusive)}$
Implementation: It is standard to make the prefix sum array one element larger than the original array (starting with a 0 entry) so the $L-1$ edge case is clean when querying the sum starting from the first element

Hash map vs. Hash set

Both hash maps and hash sets are built on the concept of a hash table - under the hood, they run the key through a hash function $f: \text{key} \mapsto \mathbb{R}$ that acts as an exact memory address, allowing the computer to find the data in $O(1)$ time without having to search through the entire collection.

Feature	Hash Map (`dict` in Python)	Hash Set (`set` in Python)
Structure	Stores key-value pairs	Stores keys only (single elements)
Uniqueness	Keys must be unique, but values can be duplicated	All elements must be unique
Primary use	Mapping data to other data (frequency count, mapping nums to indices)	Membership testing
Analogy	A dictionary: you look up a unique word (key) to find its definition (value)	A VIP guest list: you check if a specific name is on the list
Both hash maps and hash sets offer $O(1)$ average time complexity for inserting, deleting, and looking up elements.

2. Two Pointers

Used to optimize $O(N^2)$ brute-force solutions down to $O(N)$ by iterating through an array with two indices simultaneously.

Techniques: Opposite ends moving inward, both moving forward at different speeds
Classic problems: Container With Most Water, Valid Palindrome

3. Sliding Window

Specific two-pointer technique for finding subarrays or substrings that meet certain conditions.

Techniques: Fixed-size window, dynamically resizing window (grow the right boundary, shrink the left)
Classic problems:
- Easy: Longest substring without repeating characters
- Hard: Minimum window substring
Types of problems:
- Two pointers: Valid palindrome, Two Sum II
- Sliding window (fixed-size): Maximum average subarray I (window size is exactly k), Permutation in String (window size matches the target string length)
- Sliding window (dynamically resizing): Longest substring without repeating characters (grow right until a duplicate, then shrink left until it's gone), Minimum size subarray sum (grow right until sum $\geq$ target, shrink left to minimize size)

4. Fast & Slow Pointers (Linked Lists)

Floyd's Cycle-Finding Algorithm - this pattern uses two pointers moving at different speeds to navigate linked list structures.

Techniques: Detecting cycles, finding the middle of a list
Classic problems: Linked List Cycle

Finding the middle of a list

Runner A (fast) runs 2x the speed of B (slow). If they start at the same time, when A crosses the finish line, B will be exactly at the halfway mark.

def find_middle(head):
	slow = head
	fast = head
	# fast moves 2, slow moves 1
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	return slow # slow is now at middle node

5. Stacks & Monotonic Stacks

Stacks are LIFO (last-in-first-out). Monotonic stacks maintain elements in a strictly increasing or decreasing order, allowing you to find the "next greater/smaller" element in $O(N)$ time.

Techniques:
Classic problems:
- Basic stack: Valid Parentheses
- Monotonic stack: Daily temperatures
Stack vs. monotonic stack:
- Basic stack: Used when you need to match things or backtrack state
- Monotonic stack: Used when you need to find the "next greater" or "next smaller" element
  - Enforce this rule each time you add an element

# basic stack
def isValid(s):
	stack = []
	mapping = {')': '(', '}': '{', ']': '['}
	for char in s:
		if char in mapping:
			# pop top element if stack isn't empty, else assign dummy
			top_element = stack.pop() if stack else "#"
			if mapping[char] != top_element:
				return False
		else:
			stack.append(char) # it's an opening bracket
	return not stack # true if stack is empty, false if stack has stuff
	
# monotonic stack - find how many days until a warmer temperature
def dailyTemperatures(temperatures):
	res = [0] * len(temperatures)
	stack = [] # stores indices
	for i, temp in enumerate(temperatures):
		# enforce decreasing order
		while stack and temp > temperatures[stack[-1]]:
			prev_index = stack.pop()
			res[prev_index] = i - prev_index
		stack.append(i)
	return res

Non-linear Structures & Advanced Logic

6. Binary Search

Finding numbers in sorted arrays; binary searching the answer space if the problem condition is monotonic.

Techniques: Standard search, searching rotated arrays, binary search on answer space.
Classic problems:
- Easy: Search in Rotated Sorted Array
- Hard: Koko Eating Bananas

Binary searching the answer space

If your array is a range of possible answers, and you have a monotonic condition (condition you are testing flips exactly once and never flips back, e.g. "Can I eat all bananas at speed $X$ ?") -

Speeds 1, 2, 3: [False, False, False]
Speeds 4, 5, 6: [T, T, T]
Because [F, F, F, T, T, T] is sorted, you can binary search to find the very first T!

7. Tree & DFS/BFS

Trees are recursive data structures.

Techniques: Pre/in/pos-order DFS (usually recursive), level-order BFS (using a queue)
Classic problems:
- DFS: Maximum Depth of Binary Tree
- BFS: Binary Tree Level Order Traversal

Binary Search Tree (BST)

A BST is a tree where for every node:

All nodes in its left subtree are smaller

All nodes in its right subtree are larger

class TreeNode:
	def __init__(self, val=0, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right
def insert(root, val):
	if not root:
		return TreeNode(val)
	if val < root.val:
		root.left = insert(root.left, val)
	else:
		root.right = insert(root.right, val)
	return root

Tree traversals

DFS: go as deep as possible before backtracking
- Pre-order: (root, left, right) - used for copying trees
- In-order: (left, root, right) - on a BST, this visits nodes in sorted ascending order
- Post-order: (left, right, root) - used for deleting trees or gathering data from children up to the parent
BFS: sweeps across the tree one layer at a time (level-order)
- BFS does not have pre/in/pos - BFS is purely layer-by-layer, left-to-right, using a queue

Union-find data structure

Tracks disjoint sets and efficiently answers - "are these two nodes in the same group?" Why use UnionFind data structure?

Without optimization, trees can degenerate into long, linear chains, causing operations to take $O(n)$ time.

Two main techniques to ensure near-constant time execution:
1. Path compression:
2. Union by rank or size:
Often used in:
- Dynamic connectivity: specific type of problem where the graph is changing over time
  - e.g. network of computers - every hour, a technician plugs a new cable between two random computers. at any given moment, the CEO might ask - "can computer A communicate with computer B right now?"

Kruskal's

Kruskal's alg builds a MST by continuously picking the cheapest available edge, as long as that edge doesn't create a closed loop (cycle).

🔑 Use case: find the MST in a connected, undirected weighted graph - connect all vertices in the graph with the minimum possible total edge weight without forming any cycles
- e.g. - minimizing the cost of cables/wiring/pipes needed to connect a series of physical locations, optimizing delivery routes or public transit layouts to reduce distance and construction costs, clustering tasks in ML, ...

Initialize a Union-find data structure: every node starts in its own isolated group
Sort the edges: take every edge in the graph and sort from lowest weight to highest weight
Iterate through the sorted edges - take the cheapest edge available: $e = (u,v)$
Cycle check: Ask union-find, find(u) == find(v)?
1. If yes, they are already connected, ignore this edge.
2. If no, they are not connected - add this edge to the MST, and union(u, v)
^ Repeat! Until - an MST for $V$ vertices always has exactly $V-1$ edges. Once you've successfully added $V-1$ edges, can stop searching.

8. Graphs

Graphs represent connected networks. The key difference from trees is that you must track visited nodes to avoid infinite loops.

Techniques: Matrix traversal, adjacency list DFS/BFS, topological sort (for dependency graphs like prerequisites), union-find (for connected components)
Classic problems:
- Matrix: Number of islands
- Topological sort: Course Schedule

Algorithm	What it does	When to use	Time complexity	Space complexity
Graph DFS	Explores deep paths	Checking if a path exists, counting islands, backtracking combos	$O(V+E)$	$O(V)$
Graph BFS	Explores outward in concentric rings	Finding the shortest path on an unweighted graph	$O(V+E)$	$O(V)$
Topological Sort	Orders directed acyclic graphs linearly	Dependency resolution (e.g. course schedule prereqs), requires DAG (no cycles!)	$O(V+E)$	$O(V)$
Dijkstra	Shortest path from node A to everywhere	Finding shortest paths on graphs with positive weights, uses a min-heap	$O((V+E)\log V)$	$O(V)$
Bellman-Ford	Shortest path, allows negative edges	When edge weights can be negative, or to detect negative cycles	$O(V \times E)$	$O(V)$
Kosaraju	Finds strongly connected components	When you need to find clusters where every node can reach every other node in the cluster	$O(V+E)$	$O(V+E)$ (due to storing reverse graph)

Topological sort

Kahn's algorithm - BFS-based approach for topo sort on DAGs.

Calculate in-degrees: count the number of incoming edges to every node in the graph
Initialize queue: find all the nodes with an in-degree of 0 (nodes with no dependencies) and add them to a queue
Process the queue: pop a node, append it to the topological ordering, and decrement the in-degree of all its adjacent neighbors (because one of their dependencies has been satisfied)
Update and repeat: if a neighbor's in-degree drops to 0 as a result, push that neighbor into the queue. Repeat until the queue is empty.

Built-in cycle detection!

^ If the graph contains a cycle, the nodes locked in the cycle will never reach an in-degree of 0 and won't be processed → so if the size of the final topo-sort list is less than the total number of vertices, a cycle is present

Time complexity: $O(V+E)$ because we visit each vertex and process each edge exactly once.

Dijkstra's

Finds the shortest path from a start node to all other nodes in positively weighted graphs.

Greedy algorithm

Initialize distances: set the starting node's distance to 0 and all other nodes to $\infty$
Visit the nearest unvisited node: pick the unvisited node with the smallest known distance
Update neighbors: calculate the total distance from the starting node to all of its unvisited neighbors. If the new calculated distance is shorter than the neighbor's current known distance, update it.
Mark as visited: once all neighbors of the current node are evaluated, mark the current node as visited so it won't be processed again
Repeat: Continue until all reachable nodes have been visited.

Usually uses a min-heap to efficiently select the next closest unvisited node

Bellman-Ford

Finds the shortest path from a start node to all other nodes in positively and negatively weighted graphs. Slower than Dijkstra for standard positive-weighted graphs, but Dijkstra can't handle negative-weights (whilst BF can).

💡 Intuition: $V-1$ "relaxations" - progressively refines the distance estimates to each node.

Initialize distances: set the starting node's distance to 0 and all other nodes to $\infty$
Iterative relaxation: for every edge $(u,v)$ in the graph with weight $w$ , check if reaching node $v$ through node $u$ is shorter than the currently known path. If it is, update the distance to $v$ → $\text{distance}[v] = \min (\text{distance}[v], \text{distance}[u] + w)$
Repeat this process exactly $V-1$ times
Negative cycle detection: After $V-1$ iterations, do a $V$ th iteration. If any distance decreases during this final check, it indicates a negative weight cycle exists (a cycle where the total cost is negative, allowing paths to get infinitely shorter)

Why exactly $V-1$ iterations?

TL;DR: the Pigeonhole principle!

Let $V$ be the total number of vertices in the graph.
The absolute max number of edges a path can have without going in a circle (visiting the same node twice) is $V -1$ (a path connecting all the nodes).
Bellman-Ford works by building up paths edge by edge:
- Iteration 1: Finds the shortest paths using at most 1 edge
- Iteration 2: Finds the shortest paths using at most 2 edges
- ...
- Iteration $V - 1$ : Finds the shortest paths using at most $V - 1$ edges.
By the end of iteration $V-1$ , the algo has explored the longest possible non-cyclical path in the graph.
If a path of length $V$ has less distance than the $V-1$ path - we have a negative weight cycle!

Kosaraju's

Finds clusters in a directed graph where every node can reach every other node (strongly connected component).

First DFS (finish times): perform a standard DFS on the original graph. When a vertex and all its descendants are fully explored, push the vertex onto a stack - results in nodes being stacked in order of their finishing times
Reverse the graph: construct a transpose graph by flipping the direction of every edge in the original graph
Second DFS: pop nodes from the stack one-by-one. For every unvisited vertex, perform a DFS on the reversed graph. The entire set of nodes visited during this traversal represents a single SCC.

Union-find vs. Kosaraju

Union-Find works on undirected graphs - if A is connected to B, B is connected to A
Kosaraju's works on directed graphs - one-way flight from NYC to BOS doesn't entail a flight back.

Graph modeling manipulations

Trick 1: Virtual source

Use case: You have 5 different starting cities and want to find the shortest path to a destination - running Dijkstra's 5 separate times is too slow.
Solution: Create a fake "super node" (virtual source) - draw a directed edge with a weight of 0 from the super node to all 5 starting cities. Now, run Dijkstra once from the super node. Because the initial edges cost 0, the algo organically spreads into the 5 start cities simultaneously and finds the global shortest path.
Example problems: Rotting Oranges, 01 Matrix

Trick 2: State-space node splitting

Use case: "Find the shortest path from A to B, but you are only allowed to take a maximum of $K$ flights." (LC787 Cheapest Flight within $K$ stops)
Solution: Standard Dijkstra fails here because the "best" path might have too many stops. You can redefine what a node is - instead of a node being just City A, a node becomes a tuple (City A, stops left) - allowing Dijkstra or BFS to track both distance and constraints (e.g. goal state is (City B, >=0)).

Trick 3: Reversing the graph

Use case: You are given a DAG - find the shortest path from every node to one specific destination node (e.g. everyone driving to a stadium)
Solution: Instead of running Dijkstra from every single node (very slow), reverse the direction of all the edges and then run Dijkstra once from the stadium.

9. Priority Queues / Heaps

Used when you need to repeatedly find the minimum, maximum, or "top $K$ " elements efficiently.

Techniques: Min-heap, max-heap, maintaining a heap of fixed size $K$
Classic problems:
- Easy: Top $K$ frequent elements
- Hard: Merge $K$ sorted lists

Min/max heap

A min heap is a tree-based data structure where the value of each parent node is less than or equal to the values of its children - this means the minimum element is always at the root, providing $O(1)$ access to min.

To be a min-heap, the structure must satisfy two main rules:
1. Heap property: every parent node must be smaller than or equal to its child nodes
2. Complete binary tree property: every level of the tree must be fully filled, except possibly the last level (leaves), which must be filled from left to right.
- 💡 ^ because of this structural rule, min heaps can be implemented as a flat array rather than a pointer-based tree → if a parent node is at index i, the left child is at 2i + 1 and right child is at 2i + 2 [PROVE THIS]
$O(1)$ $O (1)$ to find min/max, $O(\log N)$ $O (lo g N)$ push/pop.
- Find min: return the root of the heap
- Insert: add a new element to the end of the tree and "bubble it up" (swap with its parent) until it reaches its correct spot - time complexity is $O(\log n)$ $O (lo g n)$
  - i.e. max "bubbling" length = height of complete binary tree → $O(\log n)$
- Remove min element: remove the root (smallest element), move the last element in the array to the root and "sink it down" (swap with its smaller child) to restore the heap property - $O(\log n)$

Why is the height of a balanced tree $O(\log N)$ ?

A complete binary tree fills every level completely before moving to the next level. Counting the max number of nodes ( $N$ ) that can fit at each depth (height $h$ ):

Level 0 (root): 1 node, $2^0$
Level 1: 2 nodes, $2^1$
Level 2: 4 nodes, $2^2$
Level $h$ : $2^h$ nodes

If a tree has a height $h$ , the total number of nodes $N$ is the sum of all these levels: $N = 2^0 + 2^1 + 2^2 + \cdots + 2^h$ This is a standard geometric series: $N = 2^{h+1} -1$ . Using basic algebra to solve for $h$ : $N+1 = 2^{h+1} \Rightarrow \log_2(N+1) = h + 1 \Rightarrow h = \log_2(N+1) - 1$ So, the height of the tree grows logarithmically with the number of nodes: $h \approx O(\log N)$ .

Python heaps

import heapq
min_heap = []
heapq.heappush(min_heap, 5) # O(log N)
smallest = heapq.heappop(min_heap) # O(log N)

# max heap: multiply values by -1 before pushing, and -1 after popping
max_heap = []
heapq.heappush(max_heap, -1*10)
heapq.heappush(max_heap, -1*2)
heapq.heappush(max_heap, -1*100)
heapq.heappush(max_heap, -1*50)
print(max_heap) # [-100, -50, -10, -2]
largest = -1 * heapq.heappop(max_heap)

🔑 heapq is a library of functions - it manipulates the standard list in-place
e.g. in the backend:
- heapq.heappush(min_heap, 5) does:
  1. min_heap.append(5)
  2. _siftdown (bubble up)
- heapq.heappop(min_heap)
  1. Saves min_heap[0] to return to user
  2. Moves the last element to overwrite the root
  3. _siftup (bubble down)
  4. Return the original min value saved in step 1

10. Dynamic Programming (DP)

Breaking down a problem into overlapping subproblems and caching the results (memoization) or building up from the bottom (tabulation).

Techniques: 1D arrays, 2D matrices, 0/1 Knapsack
Classic problems:
- 1D: Climbing Stairs
- 2D: Longest common subsequence

Memoization (Top-down)

Write a recursive function. Add a dictionary (cache) to store the result of function(state) so you don't calculate it twice.

Tabulation (Bottom-up)

Create a 1D or 2D array and build the solution iteratively from the base cases up.

0/1 Knapsack

Classic 2D DP problem where you decide to either "include" or "exclude" an item to maximize value without exceeding a weight limit.

Arrays & hashing

Checking if a key is in a Python dictionary is $O(1)$ $O (1)$ on average.
- Python dictionaries do not use chaining - they use open addressing with probing

General

isalnum is a standard library function in C (<ctype.h>) and a built-in method in Python (str.isalnum()) that checks if a character or string contains only alphanumeric characters (letters A-Z, a-z, and digits 0-9). It returns true/non-zero if all characters are alphanumeric, and false/zero otherwise.
Python tuples are compared item-by-item, so [(3, 3), (0, 1), (2, 3), (0, 2)] will sort to: [(0, 1), (0, 2), (2, 3), (3, 3)]
sorted(arr) returns a sorted duplicate, arr.sort() sorts in place

Algo Notes