Chaining and Dependency (Beginner)
Here's a secret about algorithms: DP, greedy, BFS, monotonic stacks, and topological sort are all doing the same thing. They're building chains — sequences where each step depends on the previous one.
This page introduces the idea with simple examples. No advanced data structures. Just the core pattern: one thing determines the next.
What's a Chain?
A chain is a sequence where each element constrains or determines the next:
The arrow means "knowing \(x_1\) helps me figure out \(x_2\)."
You've already built chains without calling them that:
- Prefix sums: \(P[0] \to P[1] \to P[2] \to \ldots\) Each sum depends on the previous one.
- BFS layers: Distance 0 nodes → distance 1 nodes → distance 2 nodes. Each layer depends on the previous.
- DP tables: \(dp[0] \to dp[1] \to dp[2] \to \ldots\) Each state is computed from earlier states.
The interesting question is: what kind of chain are you building?
Chain Type 1: "If This, Then That" (Logical Chains)
A logical chain is a cascade of forced decisions. You make one choice, and everything else follows.
Example: Bipartite Coloring
You have a graph. You need to color every node either red or blue, with no two adjacent nodes sharing a color.
Pick any node. Color it red. Now every neighbor must be blue. And every neighbor of those must be red. One decision cascades through the entire graph.
Start: Node A = Red
→ Node B (neighbor of A) = Blue
→ Node C (neighbor of B) = Red
→ Node D (neighbor of C) = Blue
That cascade is a logical chain. You fixed one thing, and the implications determined the rest. (Sound familiar? It's the fixing mindset applied to graphs.)
If at any point a node is forced to be both colors, the graph can't be 2-colored — it's not bipartite.
Example: Prefix Sum Chaining
Find all subarrays with sum zero. The trick: compute prefix sums. A subarray from \(j\) to \(i\) has sum zero when \(P[i] = P[j]\).
Group indices by their prefix sum value. If indices 3, 7, and 12 all have prefix sum 5, then subarrays [3..7], [3..12], and [7..12] all have sum zero.
The chain: \(3 \to 7 \to 12\) — linked by having the same prefix sum. When you encounter index 12, you don't compare against 3 and 7 separately. You just ask "how many previous indices have this prefix sum?" That's the hash map count.
One connection to the chain gives you access to everything already on it.
Chain Type 2: "Bigger Than the Last" (Structural Chains)
A structural chain is a sequence of elements that maintain an ordering. The most common: monotonic stacks.
Example: Next Greater Element
For each element in an array, find the first element to its right that's bigger.
Think of maintaining a chain of decreasing values. As you scan left to right:
- 4 → start the chain:
[4] - 2 → smaller than 4, extend the chain:
[4, 2] - 1 → smaller than 2, extend:
[4, 2, 1] - 5 → bigger than 1, 2, AND 4. It breaks the chain.
When 5 arrives, it "resolves" everyone it's bigger than. 1's next greater is 5. 2's next greater is 5. 4's next greater is 5. Pop them all, push 5.
- 3 → smaller than 5, extend:
[5, 3]
End of array. 5 and 3 have no next greater.
Every element gets pushed once and popped once. Total work: \(O(N)\). That's why monotonic stacks are fast — the chain structure guarantees it.
Chain Type 3: "Computed from the Previous" (Transition Chains)
This is DP. Each state is computed from earlier states.
Example: Fibonacci
\(F(n) = F(n-1) + F(n-2)\)
The chain: \(F(0) \to F(1) \to F(2) \to F(3) \to \ldots\)
Each link needs only the two previous links. You don't need \(F(0)\) to compute \(F(10)\) — you just need \(F(8)\) and \(F(9)\). The chain carries forward only what's needed.
Example: Climbing Stairs
\(dp[i] = dp[i-1] + dp[i-2]\)
Same chain. The number of ways to reach stair 10 depends only on stairs 8 and 9. The chain compresses all the history into two numbers.
Most DP transitions look like this: the next state depends on a small, fixed number of previous states. That's what makes DP efficient — each link in the chain is \(O(1)\).
Chain Type 4: "Can't Do B Until A Is Done" (Dependency Chains)
A dependency chain is about ordering: what must be computed before what?
Example: Course Prerequisites
You have courses with prerequisites. Course B requires Course A. Course C requires Course B. You need to find a valid order to take them.
Process A first (no prerequisites), then B, then C, then D. That ordering is a dependency chain — each course can't start until its prerequisite is done.
This is topological sort. And it's exactly what DP does under the hood: process states in an order where every state's prerequisites are already computed.
- In 1D DP: process left to right (state \(i\) depends on \(i-1\))
- In tree DP: process leaves first, then parents (post-order)
- In interval DP: process short intervals first, then longer ones
The processing order is always "resolve dependencies first."
The Big Picture
| Algorithm | What it's really doing |
|---|---|
| BFS | Building chains layer by layer (distance 0, 1, 2, ...) |
| DP | Building chains where each state depends on previous states |
| Greedy | Building one chain, betting it's the best |
| Monotonic stack | Maintaining a structural chain, resolving it when disturbed |
| Topological sort | Finding the right order for a dependency chain |
These aren't five separate topics. They're five ways to build chains. The chain metaphor connects them all.
When you see a new problem, ask:
- What depends on what? That tells you the chain type.
- Can I compute each link from just the previous link? That tells you if it's \(O(1)\) per step.
- What order should I process things? That's the dependency chain.
Practice Problems
1. Valid Parentheses (LC 20)
A structural chain — the stack maintains matching brackets. Each close bracket resolves the most recent open bracket (like popping from a monotonic stack).
2. Course Schedule (LC 207)
A dependency chain. Can you take all courses? Check if the prerequisite graph has a cycle (topological sort).
3. Daily Temperatures (LC 739)
Next greater element in disguise. Maintain a decreasing stack of temperatures. When a warmer day arrives, it resolves (pops) all cooler days before it.
4. Climbing Stairs (LC 70)
A transition chain. dp[i] = dp[i-1] + dp[i-2]. Each link needs only the previous two.
5. Is Graph Bipartite? (LC 785)
A logical chain. Color one node, and the implications cascade through BFS/DFS. If a conflict arises, it's not bipartite.
Ready for more? The full versions cover functional graphs, Cartesian trees, greedy as path pruning, and Dijkstra reframed as dependency resolution: