Problem overview
For each number in nums, the next greater element is the first number to its right that is strictly larger. The method NextGreaterElement returns an int[] of the same length as nums. Entry i holds the index of the next greater element of nums[i], or -1 if there is none.
For nums = [1, 3, 2, 4] the answer is [1, 3, 3, -1]. The 1 is followed by 3 at index 1. The 3 has to wait until the 4 at index 3, because the 2 is smaller. The 2 also finds the 4. The 4 is last, 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]. The 7 skips over 3, 2 and 6 and stops at the 11 at index 4.
Approach: keep the unanswered indices on a stack
The direct method scans to the right of every element until it finds a larger one. That is O(n²) for something like a decreasing array, where most scans run to the end.
The faster idea is to read the array once, left to right, and keep a list of indices that are still waiting for an answer. When a new number nums[i] arrives, it may be the answer for some of them. The waiting indices have a useful property: their values never increase from bottom to top. Suppose a smaller value sat below a larger one. The larger one would be the smaller value's next greater element, so the smaller one would already have been answered and removed. That is why the stack top is always the smallest waiting value, and the only waiting value that the new number can beat first.
The stack therefore works like this. While the number at the top is smaller than nums[i], record i as its answer and pop it. Then push i, which now waits for its own answer. Every index is pushed once and popped at most once, so the total work is O(n).
For [1, 3, 2, 4]: index 0 is pushed. At index 1, the value 3 beats the value 1, so result[0] = 1, and index 1 is pushed. At index 2, the value 2 does not beat 3, so index 2 is pushed on top of index 1. At index 3, the value 4 beats 2 and then 3, so result[2] = 3 and result[1] = 3. Index 3 is pushed and never answered, so it keeps -1.
Step by step
- Create the stack. A
Stack<int>namedstackholds indices, not values. The index is what the result needs, and the value can always be looked up innums. - Create the result array of size
nums.Lengthand fill it with-1usingArray.Fill. A newintarray holds zeros, and 0 is a valid index, so an explicit fill is necessary. Indices that are never answered keep-1. - Loop over every index
ifrom left to right. - Answer the waiting indices. A
whileloop runs as long as the stack is not empty andnums[stack.Peek()]is smaller thannums[i]. - Record the answer with
result[stack.Peek()] = i, while that index is still on the stack. - Pop it. The index has its answer and stops waiting.
- Push
i. It now waits for its own greater element. - Return
resultafter the loop. Whatever is still on the stack keeps its-1.
The solution in C#
class Solution {
public int[] NextGreaterElement(int[] nums) {
Stack<int> stack = new Stack<int>();
int[] result = new int[nums.Length];
Array.Fill(result, -1);
for (int i = 0; i < nums.Length; i++) {
while (stack.Count > 0 && nums[stack.Peek()] < nums[i]) {
result[stack.Peek()] = i;
stack.Pop();
}
stack.Push(i);
}
return result;
}
}
Some C# details to notice:
Array.Fill.Array.Fill(result, -1)sets every element of the array to the given value. The method is generic, so the array type and the value type must agree.- Short-circuit
&&. Instack.Count > 0 && nums[stack.Peek()] < nums[i], the right side runs only when the left side is true. That keepsPeek()from being called on an empty stack, which would throw anInvalidOperationException. - Peek, then Pop.
Peek()reads the top without removing it, andPop()removes it. Since the answer is written before the pop,Peek()still sees the right index. Countis a property, so it has no parentheses.- Array length.
nums.Lengthis also a property. A C# array has a fixed length, and the result array is created with the same length as the input.
Complexity
Time: O(n). The for loop runs n times and pushes each index once. The inner while loop pops indices, and each index can be popped at most once, so all pops together cost at most n steps.
Space: O(n). The stack can hold all n indices at once, for instance when the array is decreasing. The result array also has n entries.
Edge cases and common mistakes
- "Greater" is strict. For
[2, 2, 2]the answer is[-1, -1, -1]. An equal value does not beat the one on top, because the test is<. Using<=would give[1, 2, -1]. - A decreasing array. For
[5, 4, 3]nothing is ever popped, and the result is[-1, -1, -1]. - An increasing array. Every new number pops the one before it. For
[1, 2, 3]the result is[1, 2, -1]. - Storing values instead of indices. The output asks for the position of the greater element, so the stack and the results must work with indices.
- Looking only at the top. One large number can answer several waiting indices at once, as the 4 does in the first example. That is why the inner loop is a
whileand not anif. - Forgetting the fill. Without
Array.Fill, unanswered elements would report index 0, which looks like a valid answer. - An empty array. The loop does not run and the method returns an empty array.
Testing
nums = [1, 3, 2, 4]gives[1, 3, 3, -1].nums = [7, 3, 2, 6, 11, 9, 8, 10, 13]gives[4, 3, 3, 4, 8, 7, 7, 8, -1].nums = [2, 2, 2]gives[-1, -1, -1].nums = [5, 4, 3]gives[-1, -1, -1].nums = [1, 2, 3]gives[1, 2, -1].