DSA interview question

Next Greater Element

Medium · Data structures · Topics: stack, monotonic stack

The problem

A stock-analysis tool, for each day's closing price, wants the first later day with a strictly higher price (reported as that price, or −1 if prices never go higher). Checking every later day for each day is O(n²). A monotonic stack does it in O(n). Scan from right to left while keeping the candidates to the right on a stack. Before answering for the current price, pop every candidate that is ≤ it, since those can never be the next greater element for anything further left. Whatever remains on top is the answer.

Example: [4, 5, 2, 25] → [5, 25, 25, -1].

Function signature

vector<int> nextGreaterElements(const vector<int>& a);  // -1 where no greater element exists to the right

Test cases

Input	Output	Explanation
`[4, 5, 2, 25]`	`[5, 25, 25, -1]`
`[13, 7, 6, 12]`	`[-1, 12, 12, -1]`
`[1, 3, 2, 4]`	`[3, 4, 4, -1]`
`[5, 4, 3, 2, 1]`	`[-1, -1, -1, -1, -1]`	Decreasing
`[2, 2, 3]`	`[3, 3, -1]`	Strictly greater: an equal value doesn't count

(Confirm: "next" means the nearest element to the right that is strictly greater; the answer is its value, or −1.)

How interviewers phrase it

"Find the next greater element for every element of the array" (GeeksforGeeks).
LeetCode 496 asks it for a subset nums1 of nums2; the same stack plus a hash map from value to answer solves it.

Clarifying questions to ask

Strictly greater, or greater-or-equal?
Return the value or the index?
Is the array circular? (See Next Greater Element II.)

Follow-ups to expect

"Why can you pop elements that are ≤ the current one?"
"Why is it O(n) when there's a loop inside a loop?"
"What does the stack look like?"
"How do you get indices instead of values?"
"How do you get the previous greater element?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview