Problem overview
For each number in nums, its next greater element is the first number to its right that is strictly larger. The function returns, for each position, the index of that element, or -1 when there is none.
For [1, 3, 2, 4] the result is [1, 3, 3, -1]:
- for 1, the next greater is 3, at index 1;
- for 3, it is 4, at index 3;
- for 2, it is 4, at index 3;
- for 4, there is nothing to its right, so the entry is
-1.
The statement does not set a complexity, but the stack solution below runs in O(n) time.
Approach
The direct way checks, for each element, every element to its right until it finds a larger one. This is O(n^2) in the worst case, for example when the array is in descending order and nothing ever finds an answer.
A stack turns this around. Instead of asking each element to look right, we scan once from left to right and let each new element answer the questions of the earlier elements:
- The stack holds the indices of elements that are still waiting for a greater element.
- When
nums[i]arrives, it is the next greater element for every waiting index whose value is smaller thannums[i]. Those indices get their answer and leave the stack. - Then
iitself starts waiting, so it is pushed.
The values of the waiting indices never increase from bottom to top. If a larger value were above a smaller one, the smaller one would have been answered already. That is why the loop can stop at the first top that is not smaller than nums[i]: everything below it is at least as large.
Step by step
- The stack.
stackis an emptyArrayDeque<Int>. Its last element is the top, and it stores indices. - The answers.
resultis anIntArrayof sizenums.sizewhose initializer{ -1 }fills every position with-1. This is already the right answer for elements that never find a greater one. - The scan. A
forloop overnums.indicesvisits each indexi. - Answer the waiting ones. A
whileloop runs as long as the stack is not empty andnums[stack.last()] < nums[i]. The top index is waiting, andnums[i]is greater than its value. - Record it. Inside the loop,
result[stack.last()] = i. Write the answer before popping, while the index is still on top. - Pop.
stack.removeLast()removes that index, which has its answer and no longer waits. The loop then looks at the next index down. - Wait. After the
whileloop,stack.addLast(i)pushes the current index. Push the index and not the value, becauseresultneeds positions. - Return
result. Any index left on the stack never met a greater element, and its entry still holds-1.
The solution in Kotlin
class Solution {
fun nextGreaterElement(nums: IntArray): IntArray {
val stack = ArrayDeque<Int>()
val result = IntArray(nums.size) { -1 }
for (i in nums.indices) {
while (stack.isNotEmpty() && nums[stack.last()] < nums[i]) {
result[stack.last()] = i
stack.removeLast()
}
stack.addLast(i)
}
return result
}
}
Kotlin details worth knowing:
IntArray(n) { -1 }calls the lambda once per index and stores what it returns. Here the lambda ignores the index and always returns-1. Without it,IntArray(n)would fill the array with zeros, and zero is a valid index.ArrayDequeneeds no import.last()reads the top,addLastpushes andremoveLast()pops.last()andremoveLast()throw on an empty deque, so theisNotEmpty()check comes first in the loop condition. The&&operator stops at the first false part, sostack.last()is never evaluated on an empty stack.nums.indicesis the range0 until nums.size.- The comparison is
<, not<=. A value equal to the new one is not greater, so it keeps waiting.
Following the second example
For [7, 3, 2, 6, 11, 9, 8, 10, 13] the stack evolves like this:
- Indices 0, 1 and 2 (values 7, 3, 2) are pushed, because each is smaller than the one before.
- Index 3 (value 6) beats 2 and 3, so
result[2] = 3andresult[1] = 3. The 7 stays, and index 3 is pushed. - Index 4 (value 11) beats 6 and 7:
result[3] = 4andresult[0] = 4. - Indices 5 and 6 (values 9 and 8) are pushed on top of 11.
- Index 7 (value 10) beats 8 and 9:
result[6] = 7andresult[5] = 7. - Index 8 (value 13) beats 10 and 11:
result[7] = 8andresult[4] = 8. Index 8 stays on the stack with its-1.
The final array is [4, 3, 3, 4, 8, 7, 7, 8, -1].
Complexity
Time: O(n). The inner loop sits inside the outer loop, but each index is pushed exactly once and popped at most once. Over the whole run the inner loop does at most n pops in total.
Space: O(n). The stack can hold all n indices, for instance when the array is in descending order, and the result array has n entries.
Edge cases and common mistakes
- Descending or equal values. For
[5, 5, 5]nothing is strictly greater, so the result is[-1, -1, -1]. - Returning values. The result holds indices. For
[1, 3, 2, 4]the first entry is 1 (the index of the 3), not 3. - Pushing values instead of indices. The stack must hold indices, because
resultis addressed by index and values can repeat. - Popping before recording. After
removeLast()the old top is gone, andstack.last()gives a different index. - Zero as the default. Initializing
resultwith zeros makes "no answer" look like "the answer is index 0".
Testing
[1, 3, 2, 4]returns[1, 3, 3, -1].[7, 3, 2, 6, 11, 9, 8, 10, 13]returns[4, 3, 3, 4, 8, 7, 7, 8, -1].[5, 5, 5]returns[-1, -1, -1].