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



Related Contents to follow