Given an array A[] of size n, you need to find the next greater element for each element in the array.

Problem Note

  • The next greater element is the first greater element on an element’s right side in the array. e.g., an element A[j] would be the next greater element of A[i] such that A[j] > A[i] , i < j and j - i is minimum.
  • Return an array that consists of the next greater element of A[i] at index i.
  • Elements for which no greater element exist, consider next greater element as -1.

Example 1

Input: A[] = [1, 2, 3, 4, 5]
Output: [2, 3, 4, 5, -1]

Example 2

Input: A[] = [12, 1, 0, 17, 10]
Output: [17, 17, 17, -1, -1]

Example 3

Input: A[] = [3, 2, 1] 
Output: [-1, -1, -1]