DSA interview question

Next Greater Element II (Circular Array)

Medium · Data structures · Topics: stack, monotonic stack

The problem

A round-robin tournament arranges players in a circle. For each player, the organisers want the rating of the first stronger player found by walking clockwise, wrapping past the end back to the start, or −1 if nobody is stronger. The monotonic-stack trick still works if you pretend the array is written twice in a row: scan indices from 2n − 1 down to 0 using a[i % n], but only record answers for the first copy. The second copy just preloads the stack with the elements that come "after" the end.

Example: [1, 2, 1] → [2, -1, 2].

Function signature

vector<int> nextGreaterElementsCircular(const vector<int>& a);

Test cases

Input	Output	Explanation
`[1, 2, 1]`	`[2, -1, 2]`	The last 1 wraps around to find 2
`[1, 2, 3, 4, 3]`	`[2, 3, 4, -1, 4]`
`[5, 4, 3, 2, 1]`	`[-1, 5, 5, 5, 5]`	Everything wraps back to 5
`[3, 3, 3]`	`[-1, -1, -1]`	Strictly greater
`[7]`	`[-1]`

(Confirm: the array is circular; "greater" is strict; the answer is the value, or −1.)

How interviewers phrase it

"Given a circular integer array, return the next greater number for every element" (LeetCode 503).

Clarifying questions to ask

Circular: after the last element comes the first? (Yes.)
Strictly greater?
Return values or indices?

Follow-ups to expect

"Why iterate 2n times?"
"Do you need to copy the array?"
"Why only record answers for i < n?"
"Why is it still O(n)?"
"What about the maximum 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