Write a c++ code to print next greater element for every element.  Time Complexity of Brute for solution would be O(n^2).

Example

Input 12 15 22 9 7 2 18 23 27
Output 15 22 23 18 18 18 23 27 -1

Here is sample code having time complexity O(N)  and O(N) extra memory space with the help of two stacks (one for indices and other for values).

```Input  12 15 22  9  7  2 18 23 27

Initialize Output Array O[] as all -1.

1. Start from the first element. Set CurrentElement = A[0] (12). index = 0
2. Push A[index] in a Stack arr_values. Push index in a Stack arr_index.
3. Increment index.
4. while ( arr_values is not empty && A[index] is > than arr_values.top() )
- Set output_index = arr_index.top()
- set O[output_index] = A[index].
- arr_values.pop()
- arr_index.pop().
5. If index < length(Input)-1 Goto Step 2.
6. Set O[index] = -1. // Last element.```
```#include <iostream>
#include <stack>
using namespace std;

int main()
{
int inp_arr[] = { 12, 15, 22,  9,  7,  2, 18, 23, 27};
int size = sizeof(inp_arr)/sizeof(inp_arr[0]);
int out_arr[size];

stack<int> arr_values, arr_index;
arr_values.push( inp_arr[0] );
arr_index.push( 0 );

int i=0;
for ( i = 1; i < size; ++i )
{
while ( !arr_values.empty() && inp_arr[i] > arr_values.top() )
{
size_t output_i = arr_index.top();
out_arr[ output_i] = inp_arr[ i ];
arr_values.pop();
arr_index.pop();

}
arr_values.push( inp_arr[i] );
arr_index.push( i );
}

for ( i=0;i<size ;i++ )
cout << inp_arr[i]<<" --> "<< out_arr[i] <<endl;

return 0;
}```

Ref:http://stackoverflow.com/questions/24103061/need-to-find-the-next-greater-element-of-every-element-in-an-array