Next Greater Element IV — Solution in Python, Java & C++
Next Greater Element IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Next Greater Element IV is a hard coding problem on arrays, sorting and stack, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Stack, Monotonic Stack
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For every index i of nums, find its second greater element: scanning to the right of i, ignore elements that are not strictly greater than nums[i]; the second strictly greater element you meet is the answer.
Formally it is nums[j] for the smallest j > i with nums[j] > nums[i] such that exactly one index k with i < k < j also has nums[k] > nums[i]. If no such j exists the answer is -1.
Return the array of answers.
Example 1
Input: nums = [1,5,2,4,3]
Output: [2,-1,3,-1,-1]
Explanation: For 1 the greater elements to its right are 5, 2, 4, 3 — the second is 2. For 2 they are 4 and 3, so the answer is 3.
Example 2
Input: nums = [6,1,8,3,9]
Output: [9,3,-1,-1,-1]
Example 3
Input: nums = [4,4,4]
Output: [-1,-1,-1]
Explanation: Equal values are not greater.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
Hints for Next Greater Element IV
Hint 1
The classic next-greater stack answers 'first greater'. What happens to an index at the moment its first greater element arrives?
Hint 2
Once an index has seen one greater element, it is waiting for a second one — keep those indices in a second stack.
Hint 3
For each new value: first settle indices of the second stack smaller than it, then move indices of the first stack smaller than it onto the second stack (keeping their order), then push the new index onto the first stack.
How to solve Next Greater Element IV
Track every index in one of two monotonic stacks: first holds indices that have not met any greater element yet, second holds indices that have met exactly one. A new value finishes some indices of second and promotes some of first.
Approach
- Fill
answith-1; keep two stacks of indices,firstandsecond, each with non-increasing values from bottom to top. - For index
iwith valuex, pop fromsecondwhile its top value is< xand set their answer tox— this is their second greater element. - Pop from
firstwhile its top value is< xinto a temporary list —xis their first greater element. - Push the temporary list onto
secondin reverse order of popping (largest value first), sosecondstays monotonic. - Push
iontofirst.
Why it works
An index moves first → second → done exactly when it meets its first and second strictly greater elements, because each stack is sorted: everything smaller than x sits at the top, so the pops touch exactly the indices that x exceeds. Settling second before promoting from first matters — an index promoted by x must not be finished by the same x. The promoted values are all < x <= everything left in second, so pushing them largest first keeps second monotonic.
Complexity
- Time —
O(n) — each index is pushed and popped at most twice - Space —
O(n)
Pitfalls
- Process the second stack first; otherwise an index would count the same element as both its first and second greater.
- Keep the moved indices in order — appending them reversed breaks the monotonic invariant of
second. - Strictly greater: equal values never count.
Reference solution
Python
from typing import List
def secondGreaterElement(nums: List[int]) -> List[int]:
ans = [-1] * len(nums)
first = []
second = []
for i, x in enumerate(nums):
while second and nums[second[-1]] < x:
ans[second.pop()] = x
moved = []
while first and nums[first[-1]] < x:
moved.append(first.pop())
second.extend(reversed(moved))
first.append(i)
return ansJava
public static int[] secondGreaterElement(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
int[] first = new int[n], second = new int[n], moved = new int[n];
int f = 0, s = 0;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (s > 0 && nums[second[s - 1]] < x) ans[second[--s]] = x;
int m = 0;
while (f > 0 && nums[first[f - 1]] < x) moved[m++] = first[--f];
for (int k = m - 1; k >= 0; k--) second[s++] = moved[k];
first[f++] = i;
}
return ans;
}C++
vector<int> secondGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1), first, second, moved;
for (int i = 0; i < n; i++) {
int x = nums[i];
while (!second.empty() && nums[second.back()] < x) {
ans[second.back()] = x;
second.pop_back();
}
moved.clear();
while (!first.empty() && nums[first.back()] < x) {
moved.push_back(first.back());
first.pop_back();
}
for (int k = (int)moved.size() - 1; k >= 0; k--) second.push_back(moved[k]);
first.push_back(i);
}
return ans;
}JavaScript
var secondGreaterElement = function(nums) {
var n = nums.length;
var ans = new Array(n).fill(-1);
var first = [], second = [];
for (var i = 0; i < n; i++) {
var x = nums[i];
while (second.length > 0 && nums[second[second.length - 1]] < x) ans[second.pop()] = x;
var moved = [];
while (first.length > 0 && nums[first[first.length - 1]] < x) moved.push(first.pop());
for (var k = moved.length - 1; k >= 0; k--) second.push(moved[k]);
first.push(i);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms