Problem overview
The next greater element of a number in an array is the first number to its right that is strictly larger. The method nextGreaterElement(nums) returns, for every position, the index of that element, or -1 when no larger element exists to the right.
For nums = [1, 3, 2, 4] the answer is [1, 3, 3, -1]:
- for the 1 at index 0, the first larger element to the right is 3, at index 1;
- for the 3 at index 1, it is the 4 at index 3;
- for the 2 at index 2, it is also the 4 at index 3;
- the 4 at index 3 has nothing to its right, so it gets
-1.
The result holds indices, not values. Equal numbers don't count as greater: for [5, 5, 5] the answer is [-1, -1, -1]. This is different from counting how many greater elements lie to the right, which is another problem.
Approach: a stack of indices that are still waiting
The direct method, for each index, scans to the right until it finds a larger number. That is easy to write, but a decreasing array such as [9, 8, 7, 6, ...] makes every scan run to the end, which gives O(n²) time.
The stack solution reverses the viewpoint. Instead of asking "who is greater than me?" for each index, it walks through the array once and asks, for each new number, "whom am I the answer for?". The stack holds the indices that haven't found their answer yet. When a new number nums[i] arrives, every waiting index whose value is smaller than nums[i] has just found its next greater element, namely i.
Two properties make this work in linear time:
- The stack is monotonic. The values at the indices on the stack never increase from bottom to top. If a waiting value were smaller than one above it, the larger value arriving later would already have removed it. So when the top of the stack is not smaller than
nums[i], nothing below it is either, and the popping can stop. - Every index is pushed once and popped at most once. The inner
whileloop can run many times in one turn, but over the whole array it runs at most n times in total.
Step by step
- Create
stack. An empty array declared withlet. A JavaScript array works as a stack:pushadds at the end andpopremoves from the end, so the most recent index is always on top. - Create
result.new Array(nums.length).fill(-1)makes an array of the right size with every entry set to -1, the answer for an element that never finds a larger one.fillreturns the array, so it chains right afternew Array(...). - Loop over the indices with
i. - Pop the indices that
nums[i]beats. Awhileloop runs while the stack is not empty and the value at the top index,nums[ stack[stack.length - 1] ], is smaller thannums[i]. The emptiness test comes first, so the top is never read from an empty stack. - Record the answer inside that loop:
result[ stack[stack.length - 1] ] = i. This must happen before the pop, while the index is still on top. - Pop the index with
stack.pop(). It has its answer now and stops waiting. - Push
iafter thewhileloop. It now waits for its own next greater element. Push the index, not the value, becauseresultneeds indices. - Return
result. Indices left on the stack never found a larger element, so their entries keep the -1 they started with.
The solution in JavaScript
class Solution {
nextGreaterElement(nums) {
let stack = [];
let result = new Array(nums.length).fill(-1);
for (let i = 0; i < nums.length; i++) {
while (stack.length > 0 && nums[ stack[stack.length - 1] ] < nums[i]) {
result[ stack[stack.length - 1] ] = i;
stack.pop();
}
stack.push(i);
}
return result;
}
}
Trace for [1, 3, 2, 4], writing the stack as a list of indices:
i | nums[i] | What happens | Stack after | result after |
|---|---|---|---|---|
| 0 | 1 | Stack is empty, push 0 | [0] | [-1, -1, -1, -1] |
| 1 | 3 | 1 < 3, so index 0 gets answer 1; push 1 | [1] | [1, -1, -1, -1] |
| 2 | 2 | 3 is not < 2, push 2 | [1, 2] | [1, -1, -1, -1] |
| 3 | 4 | 2 < 4 gives index 2 answer 3; 3 < 4 gives index 1 answer 3; push 3 | [3] | [1, 3, 3, -1] |
The index 3 stays on the stack at the end, so its entry stays -1.
JavaScript details
- Reading the top. JavaScript has no
peek, so the top of the stack isstack[stack.length - 1]. The newerstack.at(-1)gives the same value, and it returnsundefinedfor an empty array. new Array(n)alone isn't enough. It creates n empty slots. Withoutfill(-1), indices that never find an answer would stay empty instead of holding -1.popreturns the removed value. The code doesn't need it, because it already read the index from the top.
Complexity
- Time:
O(n). Each index is pushed once and popped at most once. The nested loops don't make it quadratic, since the total number of pops over the whole run can't exceed the number of pushes. - Space:
O(n). In the worst case, a non-increasing array such as[4, 3, 2, 1], no index is ever popped and the stack holds all n of them. The result array also takes n slots.
Edge cases and common mistakes
- Empty array. The loop doesn't run, and the method returns
[]. - Equal values. The test is strict (
<), so equal numbers don't pop each other.[5, 5, 5]returns[-1, -1, -1]. Using<=would count equals as greater. - Decreasing array.
[4, 3, 2, 1]returns[-1, -1, -1, -1], and the stack never shrinks. - Storing values instead of indices. The output needs positions, and the comparison also needs the value, which is just
nums[index]. Keeping indices gives both. - Writing the answer after the pop. Once the index is removed,
stack[stack.length - 1]is a different element. - Checking
stack.lengthsecond. If the emptiness test came after the value comparison, the first turn would readnums[undefined].
Testing
[1, 3, 2, 4]gives[1, 3, 3, -1].[7, 3, 2, 6, 11, 9, 8, 10, 13]gives[4, 3, 3, 4, 8, 7, 7, 8, -1].[5, 5, 5]gives[-1, -1, -1].[4, 3, 2, 1]gives[-1, -1, -1, -1].
