Stare at this code for a moment:

for (let i = 0; i < n; i++) {

  while (stack.length && arr[stack.at(-1)!] < arr[i]) {

    stack.pop();

  }

  stack.push(i);

}

A while loop nested inside a for loop. If someone showed you this in an interview and asked “what's the time complexity?”, your gut reaction would probably be O(n^2). A loop inside a loop — that's the pattern you learned to fear.

But your instinct is wrong. This code is O(n).

How can a nested loop be linear? The standard complexity analysis you learned — “multiply the bounds of each loop” — assumes the inner loop runs its full range on every outer iteration. That's true for something like matrix traversal, where the inner loop genuinely runs m times for each of the n outer iterations. But the monotonic stack's while loop doesn't work that way. Its fuel supply is limited, and once the fuel is spent, the loop has nothing left to burn.

To see why, you need to stop counting iterations per step and start counting total operations across the entire algorithm. The answer will surprise you.

Here's the question that unlocks it: how many times can stack.pop() execute across the entire run of the algorithm?

Not per iteration — total. Across all n iterations of the outer for loop combined.

Think about what feeds the while loop. Each pop() removes an element from the stack. But elements only get onto the stack through stack.push(i), which happens exactly once per outer iteration. That's n pushes total.

An element can only be popped if it was previously pushed. And once it's popped, it's gone forever — it never goes back on the stack. So the total number of pops across the entire algorithm is at most n.

n pushes + at most n pops = at most 2n total operations. That's O(n).

The while loop might fire 5 times on one iteration and 0 times on the next three. The work isn't evenly distributed — it's amortized. Some iterations do more, some do less, but the total is bounded.

Let's make this concrete. Imagine every element gets a push token and a pop token — that's its total budget for the entire algorithm. A push costs one token. A pop costs one token. No element can spend more than two tokens total.

With n elements, the total budget is 2n tokens. If the algorithm ever tried to spend more than 2n, it would mean some element was pushed or popped more than once — which is impossible.

Track the spending yourself. Watch each element enter the stack (spend a push token) and leave the stack (spend a pop token). The total never exceeds 2n. Even when the while loop fires five times in a row — that's five pop tokens spent, all of which were earned by previous pushes. The burst doesn't break the budget; it drains tokens that were already allocated.

function nextGreater(arr) {

  const stack = [];

  const result = Array(arr.length).fill(-1);

  for (let i = 0; i < arr.length; i++) {

    while (stack.length && arr[stack[stack.length-1]] <= arr[i]) {

      result[stack.pop()] = arr[i];  // pop

    }

    stack.push(i);                    // push

  }

  return result;

}

Here's the punchline: the while loop doesn't multiply the work. It redistributes it.

In a true O(n^2) algorithm, the inner loop's total work is proportional to n on every outer iteration. In the monotonic stack, the inner while loop's total work across all outer iterations is bounded by n. Some iterations see a burst of pops (when a large element clears the stack), but those pops were “prepaid” by earlier pushes.

This is the amortized analysis pattern. You'll see it again and again:

• Two pointers — each pointer moves at most n times total
• Union-Find with path compression — each find shortens the path for future finds
• Dynamic array doubling — most appends are O(1), occasional resizes are O(n), but averaged out it's O(1) per append
• Splay trees — individual operations can be O(n), but any sequence of m operations is O(m log n)

The recipe is always the same: instead of analyzing the worst case of a single operation, count the total work across all operations. If that total is linear, each operation is O(1) amortized — even if some individual operations are expensive.

Next time you see a loop inside a loop, don't panic. Ask: “what feeds the inner loop? How many times can it fire in total?” If the inner loop is consuming a resource that's produced at most n times, the whole thing is O(n).

This is one of the most useful mental models in algorithm analysis. Interviewers love to test whether you'll fall for the “nested loop = quadratic” trap, and the amortized argument is how you break out. Don't count the worst-case cost of one iteration — count the total cost of all iterations. That's the whole trick.