Next Greater Element on Right
MediumPractice library · +20 XPstackmonotonic stackarrays
Given an array of N integers, for each element, find the first element to its right that is strictly greater than it. If no such element exists, output -1 for that position. Print the results for all elements in their original order.
Input
The first line contains an integer N. The second line contains N space-separated integers, the elements of the array.
Output
Print N space-separated integers, where the i-th integer is the next greater element to the right of the i-th input element, or -1 if none exists.
Constraints
1 <= N <= 200000 -10^9 <= A[i] <= 10^9
Time limit 1 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
5 2 1 2 4 3
Output
4 2 4 -1 -1
For 2, next greater is 4. For 1, next greater is 2. For 2, next greater is 4. For 4, none (-1). For 3, none (-1).
Example 2
Input
4 1 2 3 4
Output
2 3 4 -1
All elements have a next greater element to their right.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 2 1 2 4 3
Example 2 input
4 1 2 3 4