Do you know the monotonic stack? You’ll learn something easier to understand with shorter code!

We’re going to discuss a common fundamental problem that you may face as part of other problems. The Next Smaller Element (NSE) problem.

Problem Statement

Given an array $$$a$$$, for each index $$$i$$$, find $$$next_i$$$, which is the first index to the right of $$$i$$$ that is smaller than $$$a_i$$$.

Example

Let's say $$$a = [5, 8, 2, 6, 7, 9, 1, 2]$$$. The output (zero-based) is $$$next = [2, 2, 6, 6, 6, 6, 7, 7]$$$.

NSJ Algorithm

Let’s begin with a simple, non-optimal solution.

for (int i = n - 1; i >= 0; --i) {
	next[i] = i + 1;
	while (next[i] != n && a[i] <= a[next[i]])
		++next[i];
}

The time complexity of the above code is $$$\mathcal{O}(n^2)$$$. What if I reduce it to $$$\mathcal{O}(n)$$$ by changing only one line?

Think before you continue...

for (int i = n - 1; i >= 0; --i) {
	next[i] = i + 1;
	while (next[i] != n && a[i] <= a[next[i]])
		next[i] = next[next[i]];
}

for (int i = n — 1; i >= 0; --i) {
	while (!st.empty() && a[st.top()] >= a[i])
		st.pop();
	next[i] = st.empty() ? n : st.top();
	st.push(i);
}

for (int i = n — 1; i >= 0; --i) {
	next[i] = i + 1;
	while (next[i] != n && a[i] <= a[next[i]])
		next[i] = next[next[i]];
}

For a better understanding, check out the GIF below:

Trying to generate counterexamples? I did a lot at the beginning, too. Let’s prove it.

Why the next values are correct

We know that $$$next_i$$$ is either $$$n$$$ or $$$a_{next_i} \lt a_i$$$. So we need to prove that it really is the first smaller index—i.e., no $$$j$$$ with $$$i \lt j \lt \text{next}_i$$$ has $$$a_j \lt a_i$$$. Let’s define $$$nextChain_i$$$ to be a sequence of indices we see in our while loop to finally find the $$$next_i$$$. Formally, $$$nextChain_{i, 0} = i + 1$$$, $$$nextChain_{i, k} = next_{nextChain_{i, k - 1}}$$$. The sequence continues until $$$a_i \gt a_{nextChain_{i, k}}$$$.

Consider there exists a $$$j$$$ s.t. $$$i \lt j \lt next_i$$$ where $$$a_j \lt a_i$$$. One can simply observe that $$$j$$$ can not be contained in the $$$nextChain$$$, because the algorithm will stop at that. So there exists a $$$k$$$ where $$$nextChain_{i, k - 1} \lt j \lt nextChain_{i, k}$$$. As we know $$$a_j \lt a_i \lt a_{nextChain_{i, k - 1}}$$$, it follows that $$$next_{nextChain_{i, k - 1}} = j$$$. This is a contradiction, so no such $$$j$$$ exists—and our argument is complete.

Why this is O(n)

Lemma

Consider the line next[i] = next[next[i]]. Let k = next[i] (before the update). The pointer next[i] effectively skips over k to point to next[k]. An index k can be skipped over in this manner at most once.

Proof of lemma

Consider two indices $$$i \lt i'$$$ that skip over $$$k$$$ while finding their $$$next$$$. We know $$$a_{i'} \lt a_k$$$ and $$$i' \lt k$$$, so when we were finding $$$next_i$$$, we should reach $$$i'$$$ before we reach $$$k$$$, and then we never meet $$$k$$$. Formally, there is integer $$$l$$$ where $$$nextChain_{i, l} \lt i' \lt nextChain_{i, l + 1}$$$. Given $$$a_{i'} \lt a_k \lt nextChain_{i, l + 1}$$$, $$$next_{nextChain_{i, l}}$$$ is not $$$nextChain_{i, l + 1}$$$ because there is at least an element ($$$a_{i'}$$$) which is smaller than $$$a_{nextChain_{i, l}}$$$ and it's nearer to $$$nextChain_{i, l}$$$ than $$$nextChain_{i, l + 1}$$$. This is a contradiction, and our argument is proven.

Now, with the lemma, we know the number of times next[i] = next[next[i]] happens is $$$\mathcal{O}(n)$$$, so the total time complexity is $$$\mathcal{O}(n)$$$.

Shorter proofs are welcome!

Why This Was Undiscovered?

The NSE problem is very popular and fundamental, I think I faced it 50 times over the past 13 years since I started CP. But I never saw anyone know NSJ. I checked dozens of submissions on Codeforces and LeetCode—none used the NSJ trick. I also queried several AI tools to see whether this algorithm had been used or discovered anywhere and found out it is used in this paper to solve another problem. However, it hasn’t become popular enough in the community to replace the monotonic stack. Why do you think that is?

I think the reason is that people try to learn from others instead of discovering things on their own. If you tried finding a solution for the NSE problem, what was the probability that you ended up with monotonic stack? How about NSJ?

This again confirms my teaching method slogan: "Be a fellow traveller, not a travel leader" (see my profile picture, and check out more here).

Problems for practicing:

• CSES — Nearest Smaller Values   Python Solution   C++ Solution
• HackerRank — The Next Greater Element
• LeetCode — Final Prices With a Special Discount in a Shop
• Codeforces — 547B
• CodeChef — COCU3
• Codeforces — 675E

Update (June 10): I know monotonic stack has other applications. But NSJ seems like a magic that you think gets TLE, but it works, and it's worth learning.