Algorithms Worth Remembering

This is a living reference — algorithms that intrigue me because of how efficient they are at solving the problems they target. I’m starting with graph algorithms because they come up surprisingly often and are somewhat relatable — even finding the shortest path to my lunch place is a graph problem. Fun fact: I’ve noticed that when I travel from A to B (read: office to lunch), I usually take a different route back from B to A. I attribute it to how our brains are inherently greedy and pick whichever path looks nearest, even though there’s probably one path that’s shorter overall.

Graphs

Dijkstra’s Shortest Path

Dijkstra’s algorithm finds the shortest path from a single source to all other nodes in a weighted graph with non-negative edge weights. It’s greedy: at each step, it commits to the closest unvisited node.

(A)--2--(B)--3--(D)
 |       |       |
 4       1       2
 |       |       |
(C)--5--(E)--1--(F)

The key insight: once a node is popped from the priority queue, its distance is guaranteed to be the shortest. Any future path to that node would have to go through nodes that are farther away — so it can only be longer. This is why negative weights break the algorithm.

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

    return dist

Time complexity: O((V + E) log V) with a binary heap.

When NOT to use: If the graph has negative edge weights, Dijkstra’s greedy assumption breaks. Use Bellman-Ford instead — it’s slower at O(VE), but handles negative weights correctly.

Minimum Spanning Trees

A minimum spanning tree (MST) connects all vertices in an undirected weighted graph with the minimum total edge weight, using exactly V − 1 edges and no cycles. There are two classic greedy approaches — one thinks about edges globally, the other grows a tree from a single vertex.

Original Graph          MST (cost = 12)

(A)-4-(B)               (A)   (B)
 |\    |                  \     |
 8  2  3                   2    3
 |   \ |                    \   |
(C)-7-(D)               (C)-7-(D)

Kruskal’s Algorithm

Kruskal’s is edge-centric: sort all edges globally by weight, then greedily pick the smallest edge that doesn’t form a cycle. It uses Union-Find (Disjoint Set Union) to efficiently detect whether adding an edge would create a cycle.

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # path compression
    return parent[x]

def union(parent, rank, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return False
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True

def kruskal(n, edges):
    edges.sort(key=lambda e: e[2])  # sort by weight
    parent = list(range(n))
    rank = [0] * n
    mst = []

    for u, v, w in edges:
        if union(parent, rank, u, v):
            mst.append((u, v, w))
        if len(mst) == n - 1:
            break

    return mst

Time complexity: O(E log E) — dominated by the sort. Union-Find operations are nearly O(1) amortised with path compression and union by rank.

Memory aid: “Kruskal’s is edge-centric — sort globally, pick greedily.”

Prim’s Algorithm

Prim’s is vertex-centric: start from any vertex and grow the MST outward, always adding the cheapest edge that connects a new vertex to the existing tree. It uses a priority queue, similar to Dijkstra’s.

import heapq

def prim(graph, start=0):
    visited = set()
    pq = [(0, start, -1)]  # (weight, node, from)
    mst = []
    total = 0

    while pq and len(visited) < len(graph):
        w, u, frm = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        if frm != -1:
            mst.append((frm, u, w))
            total += w
        for v, weight in graph[u]:
            if v not in visited:
                heapq.heappush(pq, (weight, v, u))

    return mst, total

Time complexity: O((V + E) log V) with a binary heap — same as Dijkstra’s.

Memory aid: “Prim’s is vertex-centric — grow from a seed.”

When to Use Which

• Kruskal’s works best on sparse graphs (E ≈ V) and when you already have an edge list. The sort dominates, so fewer edges means faster runtime.
• Prim’s works best on dense graphs (E ≈ V²) and when you have an adjacency list or matrix. It avoids sorting all edges upfront.
• Both produce valid MSTs. If edge weights are unique, the MST is unique regardless of which algorithm you use.

Lowest Common Ancestor

Given a rooted tree and two nodes, the Lowest Common Ancestor (LCA) is the deepest node that is an ancestor of both. The classic setup is to build an adjacency list and run BFS or DFS to compute the depth and parent arrays.

      (1) depth 0
     / | \
   (2)(3)(4) depth 1
   /|     |
 (5)(6)  (7) depth 2
 /
(8)         depth 3

LCA(8, 7) = ?

The Naive Approach

1. Equalise depths — walk the deeper node up until both nodes are at the same depth
2. Walk both nodes up in lockstep until they meet

This gives the correct answer but takes O(n) per query in the worst case (e.g., a long chain). For a single query that’s fine. For thousands of queries on a large tree, we need something faster.

Binary Lifting

Binary lifting precomputes ancestors at power-of-two distances, letting us jump up the tree in O(log n) per query instead of O(n).

The core data structure is a 2D table up[k][v], where up[k][v] stores the ancestor of node v that is 2^k levels above it:

up[k][v]  |  1   2   3   4   5   6   7   8
----------+--------------------------------
k=0 (2⁰)  |  -   1   1   1   2   2   4   5
k=1 (2¹)  |  -   -   -   -   1   1   1   2
k=2 (2²)  |  -   -   -   -   -   -   -   1

Build rule: Row 0 is the direct parent. Each subsequent row is built from the previous: up[k][v] = up[k-1][up[k-1][v]] — to jump 2^k levels, jump 2^(k-1) twice.

Query in two steps:

1. Equalise depths using binary decomposition. If the depth difference is 6 (= 110 in binary), jump 4 levels (2²) then 2 levels (2¹) — two hops instead of six.

2. Find the LCA by iterating from the highest power down to 0. At each level k:

   • If up[k][u] == up[k][v] → skip (the LCA is at or above this level)
   • If up[k][u] != up[k][v] → jump both nodes (the LCA is below this level)

   After the loop, both nodes sit one level below the LCA, so the answer is parent[u].

import math

def build_binary_lifting(n, parent, depth, root=1):
    LOG = max(1, math.ceil(math.log2(n + 1)))
    up = [[0] * (n + 1) for _ in range(LOG)]
    up[0] = parent[:]

    for k in range(1, LOG):
        for v in range(1, n + 1):
            up[k][v] = up[k - 1][up[k - 1][v]]

    return up, LOG

def lca(u, v, up, depth, LOG):
    # Step 1: equalise depths
    if depth[u] < depth[v]:
        u, v = v, u
    diff = depth[u] - depth[v]
    for k in range(LOG):
        if (diff >> k) & 1:
            u = up[k][u]

    if u == v:
        return u

    # Step 2: jump both nodes upward
    for k in range(LOG - 1, -1, -1):
        if up[k][u] != up[k][v]:
            u = up[k][u]
            v = up[k][v]

    return up[0][u]

Preprocessing: O(n log n) time and space to build the table. Query: O(log n) per query — a massive improvement over the naive O(n) when handling many queries.

---

Every algorithm solves a different problem, but they share the same instinct: do less work by exploiting structure. Dijkstra’s trusts the priority queue. Kruskal’s trusts the sort order. Binary lifting trusts powers of two. Lazy people find shortcuts. Sometimes, that’s the best way to do things.