Thinking in Chains

Here's an observation that changes how you see algorithms: almost every technique you've learned — DP, greedy, two pointers, BFS, monotonic stacks — is secretly about the same thing. You're building a chain of dependencies, where knowing one thing lets you figure out the next.

Two Sum? Fix one element, and the other is forced. Bipartite coloring? Color one node, and its neighbor's color is forced. Prefix sums? Each sum depends on the previous one. DP? Each state depends on earlier states.

They're all chains. The difference is what kind of chain you're building.

This page introduces the framework. Once you see problems as chain-construction tasks, the "which algorithm do I use?" question often answers itself.

What Is a Chain?

A chain is a sequence of elements where each one determines (or constrains) the next. Think of it as a series of directed arrows: \(x_1 \to x_2 \to x_3 \to \ldots\)

The arrows can mean different things:

"\(x_1\) implies \(x_2\)" (logical)
"\(x_1\) is less than \(x_2\)" (structural ordering)
"\(x_2\) is computed from \(x_1\)" (transition)
"\(x_2\) can't be resolved until \(x_1\) is" (dependency)

All four are chains. The difference is what the arrow represents. Let's look at each type.

The Four Types of Chains

1. Logical Chains

An arrow means implication: if \(x\) is true, then \(y\) must be true. Or: if \(x\) takes some value, then \(y\)'s value is forced.

The classic example: bipartite graph coloring.

You have a graph. You need to 2-color it — every node gets color 0 or 1, and no two adjacent nodes share a color. Where do you start?

Pick any node. Give it color 0. Now every neighbor must be color 1 — they're forced. And every neighbor of those nodes must be color 0. One decision cascades through the entire connected component.

That cascade is a logical chain. You made one choice, and the implications resolved everything else. If at any point two implications conflict (a node is forced to be both 0 and 1), the graph isn't bipartite. Otherwise, you're done.

This is the same pattern as the "fix one variable, deduce the rest" approach from the Fixing Mindset page — but now we're thinking about it as chain propagation rather than algebraic substitution.

2. Structural Chains

An arrow means ordering: \(x \le y\), or \(x\) comes before \(y\) in some structure. The chain is a sequence of elements that maintain a structural relationship.

Monotonic stacks, sorted arrays, and Cartesian trees are all structural chains. We'll cover these in depth on the next page.

3. Transition Chains

An arrow means computation: \(x_{i+1}\) is computed from \(x_i\) (and maybe \(x_{i-1}\), \(x_{i-2}\), etc.). This is dynamic programming. State \(i+1\) is built from state \(i\) by some formula.

The chain is the sequence of DP states, and the arrow is the recurrence relation.

4. Dependency Chains

An arrow means prerequisite: you can't process \(y\) until \(x\) is done. This is topological ordering. In a build system, you can't compile module B until module A (which B depends on) is compiled.

Dependency chains show up in DP too — you process states in an order where every state's prerequisites are already computed. That ordering is a dependency chain.

Logical Chains in Action

Let's go deeper on logical chains, since they're the most underappreciated type.

Prefix Sum Equivalence

Here's a problem: find all subarrays with sum zero.

The standard approach: compute the prefix sum array \(P\), where \(P[i] = A[0] + A[1] + \ldots + A[i-1]\). A subarray \(A[j..i-1]\) has sum zero exactly when \(P[i] = P[j]\).

So you need to find all pairs \((i, j)\) with \(P[i] = P[j]\). That sounds like it could be \(O(N^2)\) — check every pair.

But here's the chain insight. Group all indices by their prefix sum value. If indices \(\{3, 7, 12, 20\}\) all have prefix sum 5, then every pair among them gives a zero-sum subarray. You don't need to check them individually.

Why does this work as a chain? Because when you encounter \(P[20] = 5\), you don't need to compare against indices 3, 7, and 12 separately. Index 20 "chains" to the most recent index with the same prefix sum, and that connection automatically includes all previous ones. The chain is: \(3 \to 7 \to 12 \to 20\), linked by having the same prefix sum.

The count of zero-sum subarrays ending at index 20 is just "how many previous indices share this prefix sum" — which you track with a hash map. That's \(O(1)\) per element, \(O(N)\) total.

This is the power of logical chains: one connection to the chain gives you access to everything already on it.

Difference Constraints

Another logical chain pattern: a system of inequalities like \(x_j - x_i \le w_{ij}\).

Each inequality is an edge in a graph: \(i \to j\) with weight \(w\). Fixing one variable's value forces constraints on all connected variables. Solving the system is equivalent to running shortest paths (Bellman-Ford).

You don't need to think of this as "graph theory." It's a logical chain: fixing \(x_1\) forces a bound on \(x_2\), which forces a bound on \(x_3\), and so on. The graph is just a convenient way to organize the implications.

The Two-Pointer Chain

The two-pointer technique is a logical chain in disguise. Consider: find all pairs \((x, y)\) in a sorted array that satisfy \(y \ge x - 3\).

Fix \(y\). Then \(x\) can be anything in \([y - 3, y + 3]\) (depending on exact constraints). As \(y\) increases, the valid range for \(x\) shifts — but it only shifts forward. The right endpoint never moves left.

That's a chain: \(y_1\)'s valid range → \(y_2\)'s valid range → \(y_3\)'s valid range, each starting no earlier than the previous one. The two pointers march forward together because the chain is monotonic.

Why "Chain" Is the Right Word

You might wonder: why call these "chains" instead of just "relationships" or "dependencies"?

Because a chain has direction and order. It's not just that \(x\) and \(y\) are related — it's that \(x\) determines \(y\), which determines \(z\). The direction matters. And the key property of a chain is:

To resolve any link, you only need the previous link — not the entire history.

In bipartite coloring, you don't need to remember the full coloring so far. You just need the color of the current node's neighbor. In prefix sum chaining, you don't need all previous prefix sums — just the count of how many times the current value appeared. In DP, you typically need \(O(1)\) previous states, not all of them.

This is what makes chains efficient. Each link carries forward just enough information for the next link. That's why \(O(1)\) transitions are so common in DP — the chain structure naturally compresses the information.

Recognizing Chain Structure

When you read a problem, look for these signals:

Signal	Chain Type	Example
"If X then Y" / forced values	Logical	Bipartite coloring, 2-SAT
Elements maintain an ordering	Structural	Monotonic stack, sorted sequences
"Answer for size \(N\) depends on size \(N-1\)"	Transition	DP recurrences
"Can't do B until A is done"	Dependency	Topological sort, build systems
"Fix one variable, others are determined"	Logical	Two Sum, difference constraints
"Each element points to exactly one other"	Structural	Functional graphs

Often a problem involves multiple chain types. A DP on a tree uses structural chains (the tree edges) with transition chains (the recurrence) layered on top. Dijkstra's algorithm is a dependency chain (process nodes in order of distance) with logical chains (relaxing an edge forces a bound on a neighbor's distance).

The framework doesn't replace knowing specific algorithms. It gives you a lens for why those algorithms work and when to reach for them.

What's Next

This page introduced the four chain types and focused on logical chains. The next two pages dive into the others:

Structural Chains — monotonic stacks, chain disturbance, Cartesian trees, functional graphs
Chains in DP and Greedy — transition chains, \(O(1)\) DP logic, dependency resolution, greedy as path pruning