Consecutive Next Greater Elements — Problem Statement & Solution Guide
Problem Description
You are provided with a sequence of integers representing a time-series signal. For every position in this sequence, identify the first subsequent value that is strictly larger than the current value. This is known as the next greater element. If no such larger value exists in the remaining portion of the sequence, the result for that position is -1.
Your task is to construct and return an array of the same length as the input, where each element at index i corresponds to the next greater element of nums[i].
The solution must efficiently process the array, ideally in linear time, by leveraging the properties of a monotonic stack to track potential candidates for future greater elements.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Consecutive Next Greater Elements"
WHY DOES IT MATTER?
The monotonic stack pattern appears in many “next/previous greater/smaller” problems, which are common in stock span, histogram area, and temperature forecasting tasks. Mastering this pattern equips engineers to convert brute‑force scans into linear passes, a critical skill for performance‑critical code.
OPTIMIZATION CHALLENGE
The key insight is that any element smaller than the current one can never be the answer for any element to its left, so it can be safely discarded. By popping these dominated elements, the stack remains strictly decreasing, guaranteeing O(1) amortized work per element.
REAL-WORLD CONNECTION
Think of a conveyor belt with packages of varying heights. As you walk backward, you keep a stack of the tallest packages seen so far; when you encounter a shorter package, you know the next taller one ahead without looking ahead again. This mirrors how distributed systems propagate the next higher priority event without scanning the entire backlog.
During an interview, write the loop from right to left, push the current element after resolving its answer, and remember to handle equal values by popping them as well—this avoids infinite loops and ensures strict ‘greater than’ semantics.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The Next Greater Element (NGE) problem asks for, for each index i in an array, the first element to the right that is strictly larger than arr[i]. A naïve solution scans the suffix of each element, leading to O(n^2) time, which quickly becomes infeasible for large inputs (n up to 10^5 or more) because the number of comparisons grows quadratically. The optimal paradigm leverages a monotonic stack: we traverse the array from right to left, maintaining a stack of candidate elements that are in decreasing order. When we encounter a new element, we pop all stack values that are less than or equal to it because they can never serve as a next greater for any earlier element. The element that remains on top of the stack (if any) is the immediate next greater for the current position. This yields a linear O(n) solution because each element is pushed and popped at most once. The stack thus encodes the “future” of the sequence in a compact, ordered fashion, turning a potentially quadratic search into a single pass with constant‑amortized work per element.
Interview Questions on This Problem
Q1How would you modify the Next Greater Element algorithm to return the distance (number of indices) to the next greater element instead of the value?
Maintain the same monotonic stack but store pairs (value, index). When you find the next greater for arr[i], compute distance as stackTop.index - i and store it; if the stack is empty, store -1.
Q2Can you solve the Next Greater Element problem for a circular array where the search wraps around to the beginning?
Yes. Iterate the array twice (2*n steps) using modulo indexing while applying the same monotonic stack logic; this ensures elements at the start can see candidates from the end.
Q3Explain why a priority queue cannot achieve O(n) time for the Next Greater Element problem, whereas a stack can.
A priority queue requires O(log n) insertion and removal, leading to O(n log n) total time. The stack works because it only needs to compare with the top element and pop while maintaining a monotonic order, guaranteeing each element is processed in O(1) amortized time.
Examples
Input
nums = [4, 2, 5, 1, 3]
Output
[5, 5, -1, 3, -1]
Explanation: For index 0 (value 4), the next greater element is 5 at index 2. For index 1 (value 2), the next greater element is 5 at index 2. For index 2 (value 5), no greater element exists to the right, so the result is -1. For index 3 (value 1), the next greater element is 3 at index 4. For index 4 (value 3), no greater element exists, so the result is -1.
Input
nums = [10, 11, 12, 13, 14]
Output
[11, 12, 13, 14, -1]
Explanation: The array is strictly increasing. For each element, the immediate next element is greater. For the last element (14), no greater element exists, so the result is -1.
Input
nums = [5, 5, 5, 5, 5]
Output
[-1, -1, -1, -1, -1]
Explanation: All elements are equal. Since the next greater element must be strictly larger, no element has a next greater element. Thus, all results are -1.
Input
nums = [3, 1, 4, 1, 5, 9, 2, 6]
Output
[4, 4, 5, 5, 9, -1, 6, -1]
Explanation: For index 0 (3), the next greater is 4 at index 2. For index 1 (1), the next greater is 4 at index 2. For index 2 (4), the next greater is 5 at index 4. For index 3 (1), the next greater is 5 at index 4. For index 4 (5), the next greater is 9 at index 5. For index 5 (9), no greater element exists. For index 6 (2), the next greater is 6 at index 7. For index 7 (6), no greater element exists.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The input array may contain duplicate values.
- The solution must run in O(n) time complexity.
- The solution must use O(n) auxiliary space.
Optimal Approach & Strategy
Traverse the array from right to left using a monotonic decreasing stack, popping smaller elements and using the stack top as the next greater, achieving O(n) time.
Brute Force Approach
For each index, scan forward until you find a larger value or reach the end, resulting in O(n^2) time.
Verified Code Solutions
/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
};class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && nums[st.top()] < nums[i]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
}
};class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
int idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}
}class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < n; i++) {
while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
};Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.