Log inSign up
mediumLeetCodeNot Started

Next Greater Element II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on LeetCode
Lesson

Problem Statement

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example 1 · Standard Circular Array:

Input: nums = [1, 2, 1]
Output: [2, -1, 2]
Explanation: The first 1's next greater is 2. The 2 has no greater element even circularly -> -1. The second 1 searches circularly and finds 2 at index 1.

Example 2 · Decreasing Circular Array:

Input: nums = [1, 2, 3, 4, 3]
Output: [2, 3, 4, -1, 4]
Explanation: The last element 3 wraps around to find 4.

Constraints:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Learn the standard 2N modulo technique to handle circular array problems without physical array concatenation.
  • Understand why two passes are sufficient to resolve all circular next-greater dependencies.
  • Maintain stack monotonicity across cyclic boundaries.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Iterate i from 2 * N - 1 down to 0.
  • Use nums[i % N] to access circular elements.
  • Maintain a decreasing monotonic stack.
  • Pop stack while stack.top() <= nums[i % N].
  • If i < N, assign res[i] = stack.empty() ? -1 : stack.top().
  • Push nums[i % N] onto the stack.

Connected Patterns:

Next Greater Element IDaily TemperaturesNext Smaller Element

1. Circular Nested Search

Intuition

For each element at index i, scan (i + 1) % N, (i + 2) % N, ..., (i + N - 1) % N until a strictly greater element is found.

Algorithm

  1. Step 1: Initialize array res of size N filled with -1.
  2. Step 2: Loop i from 0 to N - 1.
  3. Step 3: Loop offset from 1 to N - 1.
  4. Step 4: Check index j = (i + offset) % N. If nums[j] > nums[i], set res[i] = nums[j] and break.
  5. Step 5: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> nextGreaterElements(std::vector<int>& nums) {
7 int n = nums.size();
8 std::vector<int> res(n, -1);
9 for (int i = 0; i < n; i++) {
10 for (int offset = 1; offset < n; offset++) {
11 int j = (i + offset) % n;
12 if (nums[j] > nums[i]) {
13 res[i] = nums[j];
14 break;
15 }
16 }
17 }
18 return res;
19 }
20};
21
22int main() {
23 Solution solver;
24 std::vector<int> nums = {1, 2, 1};
25 std::vector<int> ans = solver.nextGreaterElements(nums);
26 std::cout << "Output: [";
27 for (size_t i = 0; i < ans.size(); i++) {
28 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
29 }
30 std::cout << "]" << std::endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(N^2) — For each index i, we search up to N - 1 subsequent circular positions using modulo indexing.
  • Space complexity: O(1) — O(1) auxiliary space beyond the output array.

Why Brute Force Doesn't Scale:

Circular quadratic scan re-evaluates all N-1 offsets per element.

With N = 10,000, 2N Modulo Stack runs in 20,000 operations vs 100,000,000 operations for brute force.

2. Concatenated Array Monotonic Stack

Intuition

Double the array by appending nums to itself (nums + nums), then run standard monotonic stack on the 2N array.

Algorithm

  1. Step 1: Create array doubled = nums + nums of size 2N.
  2. Step 2: Run standard backward monotonic stack on doubled.
  3. Step 3: Extract the first N results.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 std::vector<int> nextGreaterElements(std::vector<int>& nums) {
8 int n = nums.size();
9 std::vector<int> doubled;
10 doubled.reserve(2 * n);
11 for (int x : nums) doubled.push_back(x);
12 for (int x : nums) doubled.push_back(x);
13
14 std::vector<int> res(2 * n, -1);
15 std::stack<int> st;
16 for (int i = 2 * n - 1; i >= 0; i--) {
17 while (!st.empty() && st.top() <= doubled[i]) {
18 st.pop();
19 }
20 if (!st.empty()) {
21 res[i] = st.top();
22 }
23 st.push(doubled[i]);
24 }
25 res.resize(n);
26 return res;
27 }
28};
29
30int main() {
31 Solution solver;
32 std::vector<int> nums = {1, 2, 1};
33 std::vector<int> ans = solver.nextGreaterElements(nums);
34 std::cout << "Output: [";
35 for (size_t i = 0; i < ans.size(); i++) {
36 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
37 }
38 std::cout << "]" << std::endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Explicitly creating a doubled array of size 2N and running monotonic stack on it takes linear O(N) time.
  • Space complexity: O(N) — O(N) space for the 2N duplicated array.

3. Optimal Virtual 2N Modulo Monotonic Stack

Intuition

Instead of allocating 2N array memory, simulate 2 passes in-place using index modulo arithmetic i % N from 2N - 1 down to 0.

Algorithm

  1. Step 1: Initialize result array res of size N filled with -1 and an empty stack st.
  2. Step 2: Loop i from 2 * N - 1 down to 0.
  3. Step 3: Let curr = nums[i % N].
  4. Step 4: While stack is non-empty and st.top() <= curr, pop st.
  5. Step 5: If i < N and stack is non-empty, set res[i] = st.top().
  6. Step 6: Push curr onto st.
  7. Step 7: Return res.

Virtual 2N Modulo Execution Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Stack: [1]
Visual state
Values and pointers at this exact step
stack
This stack trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Stack: [1]

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4
5class Solution {
6public:
7 std::vector<int> nextGreaterElements(std::vector<int>& nums) {
8 int n = nums.size();
9 std::vector<int> res(n, -1);
10 std::stack<int> st; // stores values
11 for (int i = 2 * n - 1; i >= 0; i--) {
12 int curr = nums[i % n];
13 while (!st.empty() && st.top() <= curr) {
14 st.pop();
15 }
16 if (i < n && !st.empty()) {
17 res[i] = st.top();
18 }
19 st.push(curr);
20 }
21 return res;
22 }
23};
24
25int main() {
26 Solution solver;
27 std::vector<int> nums = {1, 2, 1};
28 std::vector<int> ans = solver.nextGreaterElements(nums);
29 std::cout << "Output: [";
30 for (size_t i = 0; i < ans.size(); i++) {
31 std::cout << ans[i] << (i + 1 < ans.size() ? ", " : "");
32 }
33 std::cout << "]" << std::endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N) — 2N total iterations where each index modulo N is pushed and popped at most twice, preserving strict O(N) runtime without extra array memory.
  • Space complexity: O(N) — O(N) stack space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Circular Nested SearchO(N^2)O(1)Nested modulo offsets scanning circularly for each item.Re-scanning identical elements in cyclic loops.
2.Concatenated Array Monotonic StackO(N)O(N)Double the array length to 2N and run linear monotonic stack.Memory allocation overhead.
3.Optimal Virtual 2N Modulo Monotonic StackOptimalO(N)O(N)Virtual 2N backward traversal using modulo arithmetic i % N.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting to check i < n before setting the result array.

Pitfall 2:

Using < instead of <= in the monotonic stack condition (which leaves equal elements).

Pitfall 3:

Looping 2N times forward without clearing stack correctly.

Crucial Edge Cases to Validate:

  • All elements equal (e.g. `[5, 5, 5, 5]`) — Strictly greater is required, so all answers are -1.
  • Single element array `[10]` — No other element exists; returns [-1].
  • Strictly decreasing array `[5, 4, 3, 2, 1]` — Every element except 5 has next greater 5.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the circular pattern immediately: 'Circular array search is equivalent to a linear search on a duplicated array of length 2N'.
  2. Explain the modulo optimization: nums[i % n] avoids the physical memory overhead of creating a 2N array.
  3. Clarify why we use st.top() <= curr (to find strictly greater elements).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is looping 2N times sufficient to cover all circular next greater possibilities?

2.Why do we only record the answer when i < N?

Back to DSA Sheet