Skip to content

Structural Chains

A structural chain is a sequence of elements that maintain a fixed relationship — usually an ordering like \(x \le y \le z\). The chain exists because the structure of the data forces it.

This page covers three structural chains that show up constantly: monotonic stacks, Cartesian trees, and functional graphs. They look like different topics, but they're all the same idea: elements linked by a structural relationship, where adding or removing an element either extends or disturbs the chain.

Monotonic Stacks: Chains of Inequality

You have an array. For each element, you want to find the next greater element — the first element to its right that's larger.

Array:  [4, 2, 1, 5, 3]
Answer: [5, 5, 5, -1, -1]

Element 4's next greater is 5. Element 2's next greater is also 5. Element 1's next greater is 5. Element 5 has nothing greater to its right. Neither does 3.

The brute force: for each element, scan right until you find something bigger. \(O(N^2)\).

The monotonic stack approach: \(O(N)\). But instead of memorizing the implementation, let's understand what's really happening in terms of chains.

Building the Chain

Imagine processing elements left to right and maintaining a chain where each element is smaller than the one below it in the stack. The stack holds a decreasing chain: the bottom element is the largest, and each element above it is smaller.

Process [4, 2, 1, 5, 3]:

Push 4. Stack: [4]. Chain: just 4.

Push 2. 2 < 4, so it extends the chain. Stack: [4, 2]. Chain: \(4 \leftarrow 2\) (2 is "under" 4 in the ordering, waiting for something bigger).

Push 1. 1 < 2, extends further. Stack: [4, 2, 1]. Chain: \(4 \leftarrow 2 \leftarrow 1\).

Push 5. Here's where it gets interesting. 5 is bigger than 1, 2, and 4. It breaks the chain.

Chain Disturbance

When a new element is bigger than the top of the stack, it disturbs the chain. Elements get popped off because their "next greater" has been found — it's the new element.

5 arrives:

  • Pop 1. Next greater of 1 is 5. ✓
  • Pop 2. Next greater of 2 is 5. ✓
  • Pop 4. Next greater of 4 is 5. ✓
  • Push 5. Stack: [5].

Push 3. 3 < 5, extends the chain. Stack: [5, 3].

End of array. Everything left on the stack (5 and 3) has no next greater element.

Why Think in Chains?

The standard explanation of monotonic stacks focuses on the while loop: "while the stack isn't empty and the top is less than the current element, pop." That's correct but mechanical. You're told what to do, not why it works.

The chain perspective is clearer: you're maintaining a decreasing chain. Every new element either extends the chain (it's smaller, push it) or disturbs it (it's larger, pop everything it dominates). Each pop resolves one "next greater" query. And since every element is pushed once and popped at most once, the total work is \(O(N)\).

The chain metaphor also helps you modify the algorithm. Want next smaller instead of next greater? Maintain an increasing chain. Want previous greater? Process right to left. The chain logic stays the same — only the direction and comparison flip.

The Code

stack<int> st;  // stores indices
vector<int> nextGreater(n, -1);

for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] < A[i]) {
        nextGreater[st.top()] = A[i];  // chain disturbed — resolved!
        st.pop();
    }
    st.push(i);  // extend the chain
}

Every push extends the chain. Every pop resolves a link. Total pushes + pops = \(2N\) at most. That's the \(O(N)\) guarantee.

Variants

Problem Chain Type Direction
Next greater element Decreasing stack Left → Right
Next smaller element Increasing stack Left → Right
Previous greater element Decreasing stack Right → Left
Previous smaller element Increasing stack Right → Left
Largest rectangle in histogram Both directions (combine results) —

All four variants are the same algorithm with different comparison operators and scan directions.

Cartesian Trees and Visibility

A Cartesian tree is what you get when you build a binary search tree from an array using values as priorities and indices as keys. The root is the minimum (or maximum) element. Its left subtree contains all elements to its left in the array, and its right subtree contains all elements to its right.

Building a Cartesian tree is intimately connected to monotonic stacks. As you process elements left to right and maintain a decreasing chain (monotonic stack), the chain relationships define the tree's edges.

Visibility Problems

Here's a concrete application. A row of people with different heights stands in a line. Person \(i\) can "see" person \(j\) (to their right) if no one between them is taller than both. How many visible pairs are there?

This is a structural chain problem. For each person, the chain of "who can I see" is determined by the monotonic structure of heights. A taller person blocks the view, disturbing the chain of visibility for shorter people behind them.

The connection to monotonic stacks: maintain a decreasing stack of heights. When a new person arrives:

  • They can see everyone they pop off the stack (those shorter people were visible to them).
  • They can see the new top of the stack (if the stack isn't empty — that's the first taller person still visible).
  • The popped people can no longer see anyone further right — the new person blocks them.

Same chain disturbance logic, different application.

Functional Graphs: One Arrow Per Node

A functional graph has a special constraint: every node has exactly one outgoing edge. Node \(i\) points to \(A[i]\). That's it — one arrow out, and you follow it.

This constraint creates a very specific structure. Let's figure out what it is.

What the Structure Looks Like

Start at any node and follow the arrows. You visit \(i \to A[i] \to A[A[i]] \to \ldots\) Since the graph has finitely many nodes, you must eventually revisit a node. The moment you do, you've found a cycle.

So following any chain of arrows eventually leads to a cycle. And then you stay on that cycle forever.

Now here's the key structural fact: each connected component has exactly one cycle.

Why? Because every node has out-degree exactly 1. Suppose a component had two separate cycles. To be connected, some node would need a path to both cycles. But that node has only one outgoing edge — it can reach only one cycle. So the component can't contain two.

The picture: each connected component looks like a rho shape (ρ). A "tail" of nodes leads into a cycle. Nodes not on the cycle live on tails feeding into it. Nodes on the cycle go around forever.

Tail:    a → b → c → d
                       ↓
Cycle:          g ← f ← e
                ↓       ↑
                h → i → j

Problems on Functional Graphs

Three common questions:

1. Where am I after \(K\) jumps?

Starting from node \(s\), follow the arrows \(K\) times. Where do you end up? For small \(K\), just simulate. For large \(K\) (say, \(10^{18}\)), use binary lifting: precompute \(\text{jump}[i][k]\) = where you end up starting from \(i\) after \(2^k\) jumps. Then decompose \(K\) into powers of 2 and chain the jumps.

This takes \(O(N \log K)\) preprocessing and \(O(\log K)\) per query.

2. Does this node reach a cycle? If so, which one?

Follow the arrows until you revisit a node. Floyd's cycle detection (tortoise and hare) finds the cycle in \(O(N)\) time and \(O(1)\) space: run two pointers, one moving at speed 1, the other at speed 2. When they meet, you've detected the cycle.

3. How long is the cycle?

Once you detect the cycle (using Floyd's), keep one pointer where they met and advance it until it returns to the same spot. Count the steps. That's the cycle length.

Classic Problems

  • Find the Duplicate Number (LC 287) — the array defines a functional graph. The duplicate creates a cycle. Floyd's algorithm finds it.
  • Linked List Cycle II (LC 142) — literally a functional graph. Find the cycle's starting node.
  • Longest Cycle in a Graph — each connected component has one cycle; find the longest.

The key insight: whenever you see "each element maps to exactly one other element" (or equivalently, next[i] is a function), you have a functional graph. The rho structure is guaranteed.

The Common Thread

Monotonic stacks, Cartesian trees, and functional graphs look like three unrelated data structures. But they share a core property:

The structure is determined by the data. You don't choose the shape — the values in the array force it. A monotonic stack's shape is forced by which elements are larger than which. A Cartesian tree's shape is forced by the min/max structure. A functional graph's shape is forced by the mapping \(i \to A[i]\).

This is what makes them structural chains, as opposed to logical chains (where choices propagate implications) or transition chains (where you compute new states). In a structural chain, the chain already exists — you're discovering it, not building it.

And discovering it efficiently is almost always about maintaining the chain as you process elements one by one, handling the "disturbances" when a new element breaks the current chain's ordering.

What's Next

Structural chains are about the shape of your data. The next page — Chains in DP and Greedy — covers transition chains (how DP builds solutions link by link) and dependency chains (the order in which you must process things). It also explains why greedy algorithms are just chain-building with aggressive pruning.