Given an array, print the Next Greater Element (NGE) for every element

PROBLEM :


Given an array A [ ] having distinct elements, the task is to find the next greater element for each element of the array in order of their appearance in the array. If no such element exists, output -1

Input:
The first line of input contains a single integer T denoting the number of test cases.Then T test cases follow. Each test case consists of two lines. The first line contains an integer N denoting the size of the array. The Second line of each test case contains N space separated positive integers denoting the values/elements in the array A[ ].

Output:
For each test case, print in a new line, the next greater element for each array element separated by space in order.

Constraints:
1<=T<=100
1<=N<=1000
1<=A[i]<=1000

Example:
Input
1
4
1 3 2 4

Output
3 4 4 -1

Explanation
In the array, the next larger element to 1 is 3 , 3 is 4 , 2 is 4 and for 4 ? since it doesn't exist hence -1.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

Method 1 (Simple)
Use two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by outer loop. If a greater element is found then that element is printed as next, otherwise -1 is printed.
Time Complexity: O(n^2). The worst case occurs when all elements are sorted in decreasing order.

BETTER SOLUTION (using STACK)

#include<iostream>
using namespace std;
#include<malloc.h>

typedef struct STACK
{
    int top ;
    int capasity ;
    int *array ;
}stack ;

stack* create_stack(stack *,int ) ;
int top(stack *) ;
void push(stack **,int  ) ;
int pop(stack **) ;

int main()
 {
 int t,no,a[1000],i,ele ;
 cin>>t ;
 while(t--)
 {
     cin>>no ;
     for(i=0;i<no;i++)
         cin>>a[i] ;
     
    stack *s,*f ;
    s=create_stack(s,no) ;
    f=create_stack(f,no) ;
 
    for(i=no-1;i>=0;i--)
    {
        ele=top(s) ;
     
        if(ele!=-1)
        while(ele<a[i])
        {
            ele=pop(&s) ;
            ele=top(s) ;
            if(ele==-1)
                 break ;
        }
        push(&f,ele) ;
     
        push(&s,a[i]) ;
    }
 
    while(f->top!=-1)
    {
        ele=pop(&f) ;
        cout<<ele<<" " ;
    }  
    cout<<endl ;
 }
 return 0;
}

stack* create_stack(stack *s,int no)
{
    s=(stack*)malloc(sizeof(stack)) ;
    s->top=-1 ;
    s->capasity=no ;
    s->array=(int*)malloc(sizeof(int)) ;
    return s ;
}

int top(stack *s)
{
    if(s->top==-1)
        return -1 ;
    return(s->array[s->top]) ;
}

void push(stack **s,int ele )
{
    if((*s)->top==(*s)->capasity)
        return ;
    (*s)->array[++((*s)->top)]=ele ;
}

int pop(stack **s)
{
    if((*s)->top==-1)
        return -1 ;
    return((*s)->array[((*s)->top)--]) ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(Using STL)
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<stack>
#define MAX 1000
int main()
{
int t,no,i,ele ;
int arr[MAX] ;

cin>>t ;
while(t--)
{
   cin>>no ;
   for(i=0;i<no;i++)
       cin>>arr[i] ;
     
   stack<int> sta1 ;
   stack<int> sta2 ;
 
   for(i=no-1;i>=0;i--)
   {
       if(sta1.empty())
       {
           sta1.push(arr[i]) ;
           sta2.push(-1) ;
       }
       else
       {
           ele=sta1.top() ;
           while(arr[i]>ele)
           {
               sta1.pop() ;
               if(sta1.empty())
               {
                   ele=-1 ;
                   break ;
               }
             
               ele=sta1.top() ;
           }
         
           sta1.push(arr[i]) ;
           sta2.push(ele) ;
       }
   }
 
   while(!sta2.empty())
   {
       cout<<sta2.top()<<" " ;
       sta2.pop() ;
   }
   cout<<endl ;
}
return 0;
}

---------------------------------------------------------------------------------