Problem overview
The method nextGreaterElement receives an array of integers, nums. For each element, the next greater element is the first element to its right that is strictly greater. The method returns an array of the same length holding the index of that element for each position, or -1 when there isn't one.
For nums = [1, 3, 2, 4] the result is [1, 3, 3, -1]. The first greater value after the 1 is the 3 at index 1. After the 3 it is the 4 at index 3. After the 2 it is also the 4 at index 3. The 4 has nothing to its right, so it gets -1.
The second example, [7, 3, 2, 6, 11, 9, 8, 10, 13], gives [4, 3, 3, 4, 8, 7, 7, 8, -1]. Notice that the 7 skips over 3, 2 and 6 and lands on 11 at index 4, because only a value larger than 7 counts.
Approach: keep the unanswered indices on a stack
The direct solution looks to the right of every element until it finds a larger one. That is O(n²) on inputs such as a decreasing array, where every element scans to the end.
The faster idea reverses the question. Instead of each element searching, scan once from left to right and keep the indices of elements that haven't found their answer yet. When a new value nums[i] arrives, it is the next greater element for every waiting index whose value is smaller. Those indices get their answer and leave. Then i joins the waiting list.
The waiting list is a stack, and the values behind its indices never increase from bottom to top. If a larger value sat above a smaller one, the smaller one would already have been answered by it. So the top of the stack is the smallest waiting value. As soon as the top isn't smaller than nums[i], nothing below it is either, and the popping can stop.
On [1, 3, 2, 4]:
- Index 0 (value 1): the stack is empty, so push 0.
- Index 1 (value 3): the top, value 1, is smaller. Set
result[0] = 1, pop. Push 1. - Index 2 (value 2): the top, value 3, isn't smaller. Push 2. The stack holds 1 and 2.
- Index 3 (value 4): the top, value 2, is smaller, so
result[2] = 3. The next top, value 3, is smaller too, soresult[1] = 3. Push 3. - Index 3 is left on the stack and keeps its
-1.
Step by step
- Create the stack as an empty
number[]. It holds the indices still waiting for an answer. The annotation is needed because TypeScript can't infer the element type of an empty array literal. - Create
result, an array withnums.lengthslots, all filled with-1usingfill. Anything that never finds a greater element keeps that-1. - Loop over the indices with
i. Each index is pushed once and popped at most once, so the algorithm is linear. - Pop the beaten indices. A
whileloop runs while the stack isn't empty and the value at the top index,nums[stack[stack.length - 1]], is smaller thannums[i]. - Record the answer by setting
result[stack[stack.length - 1]]toi. Do this before popping, while the top is still on the stack. - Pop that index with
pop(). It has its answer. - Push
iafter thewhileloop. It is the index that now waits. - Return
resultafter the main loop.
The solution in TypeScript
class Solution {
nextGreaterElement(nums: number[]): number[] {
let stack: number[] = [];
let result: number[] = 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;
}
}
The TypeScript details worth a closer look:
new Array(n).fill(-1).new Array(n)makes an array ofnempty slots, andfill(-1)puts-1in every slot and returns the same array. Withoutfill, reading a slot givesundefined. Printing such an array shows[ <3 empty items> ], not a list of numbers.- Beware
new Array(n)with one number. It means "length n", not "an array containing n".new Array(3)has three empty slots, while[3]holds the number 3. - Indices, not values, on the stack. The comparison needs the value,
nums[index], and the answer needs the index. Storing the index gives you both. - Peeking uses
stack[stack.length - 1]. It reads the top without removing it. The checkstack.length > 0comes first in the condition:&&stops at the first false operand, so the top is never read on an empty stack. - Annotations are compile-time only.
: number[]doesn't exist in the JavaScript that runs.
Complexity
Time: O(n). The loop visits each index once. Each index is pushed exactly once and popped at most once, so the inner while loop does at most n pops over the whole run, even though it sits inside the for loop.
Space: O(n). The stack can hold every index, for example when the array is strictly decreasing. The result array has n entries too, and the problem requires it.
Edge cases and common mistakes
- Empty array. The loop doesn't run, and the result is an empty array.
- Equal values. The comparison is strict, so
[2, 2]gives[-1, -1]. An equal value is not greater. - Decreasing array.
[5, 4, 3]gives[-1, -1, -1], and nothing is ever popped. - Increasing array.
[1, 2, 3]gives[1, 2, -1], and the stack never holds more than one index. - Storing values on the stack. You could compare, but you could no longer tell which position to write the answer to.
- Popping before writing. Once you call
pop(), the top index is gone, so you can't usestack[stack.length - 1]to write the answer. - Returning values instead of indices. The answer for
[1, 3, 2, 4]is[1, 3, 3, -1], not[3, 4, 4, -1].
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].[2, 2]gives[-1, -1].[1, 2, 3]gives[1, 2, -1].[]gives[].