Next Larger Element

Task: Given an array of N distinct elements, Find the next greater element for each element of the array in order of their appearance in the array. If no such element exists, print -1.

Example:

Input:

1

4

1 3 2 4

Output:

3 4 4 -1

---

Here is the Code:

Program in C++:

 

1. #include<iostream>
2. #include<bits/stdc++.h>
3. using namespace std;
4. int nextLargerElement(int n,long long *a)
5. {
6.     stack<long long> st;
7.     for(int i=n-1;i>=0;i--)
8.     {
9.         while(st.empty()==false&&st.top()<a[i])
10.         {
11.             st.pop();
12.         }
13.         long long t = a[i];
14.         if(st.empty())
15.         {
16.             a[i]=-1;
17.         }
18.         else
19.         {
20.             a[i]=st.top();
21.         }
22.         st.push(t);
23.     }
24.     for(int i=0;i<n;i++)
25.     {
26.         cout<<a[i]<<" ";
27.     }
28. }
29. int main()
30.  {
31. int t;
32. cin>>t;
33. while(t--)
34. {
35.     int n;
36.     cin>>n;
37.     long long a[n];
38.     for(int i=0;i<n;i++)
39.     {
40.         cin>>a[i];
41.     }
42.     nextLargerElement(n,a);
43.     cout<<endl;
44. }
45. return 0;
46. }

---

Here is the Video:

---