Stack Topological Sort Simulation
Learner Level

Implement the nextGreaterElementArray method that returns the next greater value for each array element.

The input contains an integer array nums and its length size. For each element, your task is to find the next greater value on its right side.

If no greater value exists to the right of an element, store -1 for that position.

For example, for [2,1,2,4,3], the result is [4,2,4,-1,-1].

Example 1
Input:
nums (int[]) = [2,1,2,4,3]
size (int) = 5
Return:
(int[]) [4,2,4,-1,-1]
Example 2
Input:
nums (int[]) = [1,2,3]
size (int) = 3
Return:
(int[]) [2,3,-1]
Example 3
Input:
nums (int[]) = [3,2,1]
size (int) = 3
Return:
(int[]) [-1,-1,-1]

Use a monotonic stack of indexes whose next greater value has not been found yet.

Scan the array from left to right. While the current value is greater than the value at the index stored on top of the stack, the current value is the next greater element for that stored index.

Set those answers and pop the indexes. Push the current index so it can also wait for a future greater value.

Pseudocode:

function nextGreaterElementArray(nums, size):
    result = array of size filled with -1
    stack = empty stack of indexes
    for i from 0 to size - 1:
        while stack is not empty and nums[i] > nums[top of stack]:
            index = pop from stack
            result[index] = nums[i]
        push i into stack
    return result
Run your code to see the result.