Algorithms Intermediate: Advanced & Graphs
Master the algorithms behind real systems — merge sort, heaps, Dijkstra, union-find, spanning trees, dynamic programming, tries, and segment trees. Build the patterns that solve interview and production problems.
Start LearningMerge Sort
24 minWhat you'll learn
- Learn divide-and-conquer sorting
- Achieve O(n log n)
- Understand merging
Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves. The merging step is the genius: two sorted lists merge into one in linear time. Result: guaranteed O(n log n) — dramatically faster than O(n²) sorting for large data, and stable (preserves equal-element order). It's Python's default sort foundation (Timsort).
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(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] < b[j]: result.append(a[i]); i += 1
else: result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
print(merge_sort([5, 2, 8, 1, 3, 9, 4]))
Try it yourself
Merge sort's time complexity is?
O(n log n) — log n splits, n work each level.
Quick Sort
24 minWhat you'll learn
- Learn pivot partitioning
- Understand average vs worst case
- Compare with merge sort
Quicksort picks a pivot, partitions the array into 'less than pivot' and 'greater than pivot', then recursively sorts both sides. It's O(n log n) average, in-place (unlike merge sort's extra memory), and often faster in practice — but O(n²) worst-case on already-sorted data with a bad pivot. Randomized pivot selection fixes that. It's the most widely used general-purpose sort.
def quick_sort(arr):
if len(arr) <= 1: return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([5, 2, 8, 1, 3, 9, 4]))
Try it yourself
When is quicksort O(n²)?
When the pivot is always the min/max (e.g., already-sorted data with first-element pivot).
Heaps & Priority Queues
22 minWhat you'll learn
- Understand heap structure
- Use min/max heaps
- Solve top-k problems
A heap is a binary tree where the parent is always larger (max-heap) or smaller (min-heap) than its children. The root is always the extreme value, so extracting it is O(log n) while insertion is O(log n). Python's heapq is a min-heap. Heaps power priority queues, task scheduling, Dijkstra's algorithm, and the classic 'top k' problem (k largest elements in a stream).
import heapq nums = [5, 1, 9, 3, 7] heapq.heapify(nums) # min-heap print(heapq.heappop(nums)) # 1 (smallest) heapq.heappush(nums, 0) print(nums[0]) # 0 (root = min)
Try it yourself
What's the time complexity of heappush and heappop?
O(log n) each.
Graph Representations
20 minWhat you'll learn
- Represent graphs as lists/matrices
- Know trade-offs
- Choose the right representation
Graphs model relationships — social networks, roads, dependencies. Two main representations: adjacency list (dict of lists — memory-efficient, fast iteration) and adjacency matrix (2D array — O(1) edge lookup, O(V²) memory). Adjacency lists are the default for sparse graphs (most real graphs); matrices shine for dense graphs. Choosing right affects every graph algorithm's performance.
# Adjacency list
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
# Adjacency matrix
matrix = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
]
print(graph[0], matrix[0])
Try it yourself
For a graph with 1M nodes and 2M edges, which representation?
Adjacency list — matrix would be 10¹² cells.
Dijkstra's Algorithm
26 minWhat you'll learn
- Find shortest paths
- Use a priority queue
- Handle weighted graphs
Dijkstra's algorithm finds the shortest path from a start node to all others in a weighted graph with non-negative edges. It greedily expands the closest unvisited node, updating distances to neighbors via a priority queue. Complexity O((V+E) log V) with a heap. This powers GPS navigation, network routing, and game pathfinding. It fails with negative edges — that's Bellman-Ford's job.
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist[node]: continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return dist
g = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2)], 3: []}
print(dijkstra(g, 0))
Try it yourself
What data structure makes Dijkstra efficient?
A min-heap (priority queue).
Bellman-Ford Algorithm
24 minWhat you'll learn
- Handle negative edges
- Detect negative cycles
- Compare with Dijkstra
Bellman-Ford finds shortest paths even with NEGATIVE edge weights — something Dijkstra can't handle. It relaxes every edge V-1 times, guaranteeing correct distances. A final relaxation pass detects negative cycles (if any distance still improves, a negative cycle exists). Slower than Dijkstra — O(V·E) — but more general. It's the fallback when weights go negative.
def bellman_ford(edges, V, start):
dist = [float('inf')] * V
dist[start] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges: # negative cycle check
if dist[u] + w < dist[v]:
return 'Negative cycle!'
return dist
print(bellman_ford([(0,1,4),(0,2,5),(1,2,-3)], 3, 0))
Try it yourself
What can Bellman-Ford detect that Dijkstra can't?
Negative cycles.
Union-Find (Disjoint Set)
22 minWhat you'll learn
- Track connected components
- Use path compression
- Solve connectivity queries
Union-Find (Disjoint Set Union) maintains groups of connected elements. It supports two operations: find (which group is x in?) and union (merge two groups). With path compression and union by rank, both are nearly O(1) (amortized). Applications: cycle detection, connected components, Kruskal's MST, and network connectivity. It's deceptively simple but extremely powerful.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compress
return self.parent[x]
def union(self, a, b):
self.parent[self.find(a)] = self.find(b)
dsu = DSU(5)
dsu.union(0, 1)
dsu.union(1, 2)
print(dsu.find(0) == dsu.find(2))
Try it yourself
What's the amortized complexity of union-find with compression?
O(α(n)) — inverse Ackermann, effectively constant.
Minimum Spanning Tree (Kruskal)
24 minWhat you'll learn
- Understand spanning trees
- Learn Kruskal's algorithm
- Connect all nodes cheapest
A minimum spanning tree (MST) connects all nodes using the minimum total edge weight — like laying cable or building roads at lowest cost. Kruskal's algorithm sorts edges by weight and greedily adds each if it doesn't create a cycle (checked via Union-Find). It's O(E log E) for sorting. Greedy + union-find = elegant and correct because MST has the greedy-choice property.
def kruskal(edges, V):
edges.sort(key=lambda x: x[2]) # sort by weight
dsu = DSU(V)
mst = []
for u, v, w in edges:
if dsu.find(u) != dsu.find(v):
dsu.union(u, v)
mst.append((u, v, w))
return mst
print(kruskal([(0,1,4),(0,2,1),(1,2,2),(1,3,5),(2,3,8)], 4))
Try it yourself
How does Kruskal avoid cycles?
It skips an edge if both endpoints are already in the same component.
Topological Sort
22 minWhat you'll learn
- Order dependent tasks
- Use DFS or Kahn's algorithm
- Detect cycles in DAGs
Topological sort orders nodes so every edge goes from earlier to later — essential for task dependencies (build systems, course prerequisites). It only works on directed ACYCLIC graphs (DAGs). Kahn's algorithm repeatedly removes nodes with no incoming edges, queueing them. If you can't order all nodes, a cycle exists. This is how make, pip, and npm resolve dependencies.
from collections import deque
def topo_sort(V, edges):
graph = {i: [] for i in range(V)}
indegree = {i: 0 for i in range(V)}
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
q = deque([n for n in range(V) if indegree[n] == 0])
result = []
while q:
node = q.popleft()
result.append(node)
for nxt in graph[node]:
indegree[nxt] -= 1
if indegree[nxt] == 0: q.append(nxt)
return result if len(result) == V else 'cycle!'
print(topo_sort(4, [(0,1),(0,2),(1,3),(2,3)]))
Try it yourself
Can you topologically sort a graph with a cycle?
No — a cycle has no valid ordering (that's the cycle detection).
Cycle Detection in Graphs
20 minWhat you'll learn
- Detect cycles in directed/undirected graphs
- Use DFS colors
- Apply to dependency cycles
Detecting cycles is critical — circular dependencies, deadlocks, infinite loops in state machines. For directed graphs, DFS with three colors (white=unvisited, gray=visiting, black=done) detects a cycle when you meet a gray node. For undirected graphs, a cycle exists if DFS reaches an already-visited node that isn't the parent. Cycle detection is the foundation of dependency safety.
def has_cycle(graph):
color = {n: 0 for n in graph} # 0=white,1=gray,2=black
def dfs(node):
color[node] = 1
for nxt in graph[node]:
if color[nxt] == 1: return True
if color[nxt] == 0 and dfs(nxt): return True
color[node] = 2
return False
return any(color[n] == 0 and dfs(n) for n in graph)
print(has_cycle({0:[1], 1:[2], 2:[0]}))
Try it yourself
What does a 'gray' node meeting in DFS mean?
A back edge to a node currently being visited — a cycle.
DP: 0/1 Knapsack
26 minWhat you'll learn
- Solve the classic DP problem
- Build a DP table
- Optimize value under weight
The 0/1 knapsack problem: given items with weights and values, pick a subset maximizing total value under a weight limit. It's the canonical DP problem because the recurrence is beautiful: either take the item (value + best without it) or skip it. DP table dp[i][w] = best value using first i items with capacity w. This pattern transfers to countless optimization problems.
def knapsack(values, weights, capacity):
n = len(values)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w-weights[i-1]])
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
print(knapsack([60, 100, 120], [10, 20, 30], 50))
DP table — best value 220
Try it yourself
Knapsack's time complexity is?
O(n·capacity).
DP: Longest Common Subsequence
24 minWhat you'll learn
- Compare sequences
- Build LCS DP table
- Apply to diff and DNA
LCS finds the longest sequence common to two strings (characters in order, not necessarily contiguous). It powers diff tools, version control, and DNA comparison. The recurrence: if characters match, 1 + LCS of prefixes; else max of skipping either. The DP table builds up the answer bottom-up. It's a two-string DP classic that teaches the matching pattern.
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]
print(lcs('abcde', 'ace'))
Try it yourself
LCS of 'abc' and 'abc' is?
3 (the whole string).
DP: Edit Distance
24 minWhat you'll learn
- Measure string difference
- Use insert/delete/replace ops
- Apply to spell check
Edit distance (Levenshtein distance) counts the minimum insertions, deletions, or replacements to transform one string into another. It's the algorithm behind spell checkers, fuzzy search, and DNA alignment. The recurrence considers all three operations and takes the minimum. This is the most general string-matching DP — and once you see it, many string problems become one variation.
def edit_distance(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1): dp[i][0] = i
for j in range(n + 1): dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
print(edit_distance('kitten', 'sitting'))
Try it yourself
What are the three operations in edit distance?
Insert, delete, replace.
Bit Manipulation
20 minWhat you'll learn
- Use bitwise operators
- Solve problems with bits
- Optimize space and speed
Bit manipulation works directly with binary — AND (&), OR (|), XOR (^), shifts (<<, >>). It's blazingly fast and memory-efficient: flags packed into one integer, XOR to find the unique number, shifts for powers of two. Niche in application code but essential in competitive programming and low-level systems. The XOR trick (a ^ a = 0) solves 'find the unique element' in O(n) time, O(1) space.
def find_unique(arr):
result = 0
for num in arr:
result ^= num # a ^ a = 0, so duplicates cancel
return result
print(find_unique([4, 1, 2, 1, 2]))
Try it yourself
What is 5 & 3 in binary?
1 (101 & 011 = 001).
Trie (Prefix Tree)
24 minWhat you'll learn
- Store strings efficiently
- Do prefix search fast
- Build autocomplete
A trie stores strings character by character in a tree — each path from root spells a word. It enables O(L) lookup (L = word length) and, crucially, prefix search: find all words starting with 'ca'. This powers autocomplete, spell check, and IP routing. Tries trade memory for speed: more nodes, but instant prefix queries.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self): self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children: return False
node = node.children[ch]
return node.is_end
t = Trie()
for w in ['cat', 'car', 'dog']: t.insert(w)
print(t.search('car'), t.search('can'))
Try it yourself
What's the lookup time in a trie for a word of length L?
O(L).
Segment Tree
26 minWhat you'll learn
- Answer range queries fast
- Support updates
- Solve RMQ problems
A segment tree answers range queries — sum, min, max over any subarray — in O(log n), and supports point updates in O(log n). It precomputes a binary tree where each node covers a segment. Applications: range minimum query, range sum with updates, computational geometry. It's the advanced structure for any 'query over a range, with updates' problem.
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self.build(arr, 0, 0, self.n - 1)
def build(self, arr, node, left, right):
if left == right:
self.tree[node] = arr[left]
else:
mid = (left + right) // 2
self.build(arr, node*2+1, left, mid)
self.build(arr, node*2+2, mid+1, right)
self.tree[node] = self.tree[node*2+1] + self.tree[node*2+2]
def query(self, node, left, right, ql, qr):
if ql > right or qr < left: return 0
if ql <= left and right <= qr: return self.tree[node]
mid = (left + right) // 2
return self.query(node*2+1, left, mid, ql, qr) + self.query(node*2+2, mid+1, right, ql, qr)
st = SegmentTree([1, 3, 5, 7, 9])
print(st.query(0, 0, 4, 1, 3))
Try it yourself
Segment tree query complexity is?
O(log n).
Binary Search Tree Operations
22 minWhat you'll learn
- Insert, search, delete in BST
- Understand BST property
- Know when trees degrade
A BST keeps left subtree < node < right subtree — enabling O(log n) search, insert, and delete on balanced trees. The danger: inserting sorted data creates a linked list (O(n) operations). That's why self-balancing trees (AVL, Red-Black) exist. Understanding BST operations is the foundation for all tree-based algorithms and database indexing.
class BST:
def __init__(self, val): self.val = val; self.left = self.right = None
def insert(self, val):
if val < self.val:
self.left = self.left.insert(val) if self.left else BST(val)
else:
self.right = self.right.insert(val) if self.right else BST(val)
return self
def search(self, val):
if self.val == val: return True
if val < self.val and self.left: return self.left.search(val)
if val > self.val and self.right: return self.right.search(val)
return False
root = BST(5)
for v in [3, 8, 1, 4]: root.insert(v)
print(root.search(4), root.search(9))
Try it yourself
What happens to a BST if you insert sorted data?
It becomes a linked list — O(n) operations.
Backtracking
26 minWhat you'll learn
- Explore all possibilities
- Prune dead ends
- Solve N-Queens and Sudoku
Backtracking systematically explores all solutions by building candidates and abandoning ('backtracking') when a partial solution can't work. It's the algorithm for constraint satisfaction — N-Queens, Sudoku, permutations, maze solving. The pattern: try a choice, recurse, undo if it fails. It's brute force with pruning, turning exponential into feasible for many problems.
def solve_n_queens(n):
def is_safe(board, row, col):
for i in range(row):
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
def backtrack(row, board):
if row == n: return 1
count = 0
for col in range(n):
if is_safe(board, row, col):
board[row] = col
count += backtrack(row + 1, board)
return count
return backtrack(0, [-1] * n)
print(solve_n_queens(4))
Try it yourself
What makes backtracking better than pure brute force?
Pruning — abandoning partial solutions that can't work.
Greedy vs DP: When to Use Which
22 minWhat you'll learn
- Compare greedy and DP
- Recognize greedy problems
- Choose the right approach
Greedy makes one local choice and never reconsiders — fast but only works when local best = global best. DP considers all possibilities, caching results — correct for overlapping subproblems but slower. Rule of thumb: if a greedy choice can be proven optimal (MST, activity selection), use greedy; if choices interact (knapsack, LCS), use DP. Recognizing which applies is a core problem-solving skill.
# Greedy: always pick the biggest coin (works for standard coins)
# DP: knapsack needs DP because items interact (weight limit)
print('Greedy: fast, local optimal. DP: thorough, global optimal.')
Try it yourself
Coin change with [1,5,10,25] — greedy or DP?
Greedy works for standard US coins (each is a multiple of previous).
Capstone: Shortest Route Finder
50 minWhat you'll learn
- Apply graph algorithms
- Build a route finder
- Analyze and document choices
Your capstone: build a shortest-route finder. Model a map as a weighted graph, run Dijkstra's algorithm, and output the shortest path and its cost. Then extend it: detect if negative edges require Bellman-Ford. You'll combine graph representation, priority queues, path reconstruction, and complexity analysis — proving you can apply algorithms to real problems.
def shortest_path(graph, start, end):
dist = dijkstra(graph, start)
return dist[end]
g = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2)], 3: []}
print(f'Shortest 0→3: {shortest_path(g, 0, 3)}')
Try it yourself
What does Dijkstra need to work correctly?
Non-negative edge weights.
You've completed all 20 intermediate lessons. Ready for advanced?
Continue to Algorithms Advanced for advanced graph algorithms, string algorithms, and competitive patterns.