2454. Second Next Greater

A Brief Review: First Next Greater Element

Next Greater Element I

GeeksforGeeks explanation of First Next Greater Element

The First Next Greater Element problem is well-known. On LeetCode it's problem 496.

Today we look at problem 496's twin: problem 2454, hard level.

Next Greater Element IV

Problem 2454 is called Next Greater Element IV, but Second Next Greater Element is a more appropriate name.

For each element $nums[i]$, we need to find the second element to its right that is greater than it.

Finding just the first one isn't enough.

How Popular Sites Handle Problem 2454

Algo Monster uses pure binary search.

LeetCode Wiki Solution 1 uses an ordered set with sorting.

Both are $O(n \log n)$ solutions. They do get AC.

But... we can still follow professor Tim Roughgarden, former Stanford and now Columbia CS professor, who opens data structures and algorithms lectures on YouTube and Coursera with this famous line:

Professor Roughgarden's Courses Are Amazing

Update: if you scroll down too fast in LeetCode Wiki link and see a double stacks solution, don't hesitate

As this double stacks solution is from my pull request merged into LeetCode Wiki

However, I still recommend that you stay in my blog, as words here are more interesting😉

How I Think About "Second" Next Greater

First, ask a foundational question:

what kind of element has the right — or more precisely, the eligibility to ask "where is my Second Next Greater? 🥲"

It must be an element that has already encountered its first right-side element greater than itself, and is now searching for the next one greater than itself.

Searching for the next element to the right that is greater than itself... sound familiar?

An element that hasn't seen any right-side greater element is searching for the next element to the right that is greater than itself.

So we immediately see: if element $x$ eventually finds its second next greater,

$x$ must have successfully completed two rounds of "find the next greater element to the right".

Actions are the same, but states differ:

1. First search: state of $x$— has not yet encountered any right-side greater element.
2. Second search: state of $x$— has encountered exactly one right-side greater element.

Since the first task is well-known to be solvable by a monotonic decreasing stack, the second task can obviously also be solved with a stack — no binary search or ordered set needed.

We just need stack 1 for the first task and stack 2 for the second task, managing elements in different states.

During traversal of $nums$, when we reach element $y$:

first check stack 2 — while it has elements and its top is less than $y$,

congratulations, that top element has found $y$ as its second next greater.

Pop it off stack 2 and record $y$ as its answer.

Once stack 2 is empty or its top is no longer less than $y$, $y$ can no longer be anyone's second next greater.

Now $y$ checks stack 1 to see if it can be anyone's first next greater.

Similarly, while stack 1 has elements and its top is less than $y$, $y$ is that top element's first next greater.

Remove those elements off stack 1 and load them onto a vector serving as a transporter 🚚.

Once stack 1 is empty or its top is no longer less than $y$, $y$ enters stack 1 to wait for future.

Transporter vector 🚚 then heads to stack 2. One essential thing here:

since both stacks are monotonically decreasing, elements were pushed onto transporter vector 🚚 in ascending order.

When transporter vector 🚚 transfers elements to stack 2, larger elements must enter stack 2 before smaller elements.

Otherwise, we can't maintain stack 2's necessary monotonically decreasing property.

Since each element is traversed once, pushed into stack 1 exactly once, and enters stack 2 at most once,

our double-stack approach runs in $O(n)$ time and $O(n)$ space.

Double stacks C++ performance: AC in 31ms.

(Quietly noting: Algo Monster method and LeetCode Wiki solution 1 took 350+ ms in C++, which stretched time distribution chart significantly in the other direction. See horizontal axis.)

Takeaway: 2 = 1 + 1

Second next greater element problem is essentially the identity 2 = 1 + 1 in action.

Think of it as doing first next greater element problem "twice", and you naturally arrive at double stacks solution.

In fact, the team match process at big tech giants is a real-life second next greater element problem:

however, our array isn't infinite. Once inside stack 2, every traversed element is a chance to rise. Team match works this way.

C++

#include <stack>
#include <vector>
using namespace std;

vector<int> find_second_next_greater(vector<int>& nums) // LeetCode Q.2454.
{
    vector<int> secondNextGreater(nums.size(), -1);

    // Decreasing monotonic stacks: {num, idx}.
    stack<pair<int, int>> stackOne, stackTwo;

    vector<pair<int, int>> transporter; // Format: {num, idx}.

    for (int idx = 0; idx < nums.size(); idx++) {
        int num = nums[idx];

        while (!stackTwo.empty() && stackTwo.top().first < num) {
            int pastIdx = stackTwo.top().second;
            secondNextGreater[pastIdx] = num;
            stackTwo.pop();
        }

        while (!stackOne.empty() && stackOne.top().first < num) {
            transporter.push_back(stackOne.top()); // Keep decreasing monotonicity.
            stackOne.pop();
        }

        while (!transporter.empty()) {
            stackTwo.push(transporter.back());
            transporter.pop_back();
        }

        stackOne.push({num, idx});
    }

    return secondNextGreater;
}

Python

def find_second_next_greater(nums: list[int]) -> list[int]:  # LeetCode Q.2454.
    second_next_greater = [-1] * len(nums)

    stack_1: list[tuple[int, int]] = []  # Decreasing monotonic stacks: (num, idx).
    stack_2: list[tuple[int, int]] = []

    transporter: list[tuple[int, int]] = []  # Transport tuples from stack 1 to stack 2.

    for idx, num in enumerate(nums):
        while stack_2 and stack_2[-1][0] < num:
            _, past_idx = stack_2.pop(-1)
            second_next_greater[past_idx] = num

        while stack_1 and stack_1[-1][0] < num:
            transporter.append(stack_1.pop(-1))
        
        while transporter:
            stack_2.append(transporter.pop(-1))  # Ensure decreasing monotonicity.
        stack_1.append((num, idx))

    return second_next_greater

Follow-up Problems

Now that we've seen both first and second next greater, consider:

1. For an array of length $n$, find $k^{\text{th}}$ greater element to the right for each element, where $k$ is a positive integer variable. What are our time and space complexities?
2. Following the above: does the worst-case time complexity depend on $k$? If not, why not? What's time complexity in that case?
3. Continuing from question 1. For an array of length $n = 1,000,000$, which value of $k$ most easily produces results for all elements? (A) $k = 1$ (B) $k = 10^2$ (C) $k = 10^4$ (D) $k = 10^6$

Think through all three questions, and you'll solidly grasp philosophy behind monotonic stacks 🤓