Stack: Get the next greater element in a circular array

Problem Statement:

You are given an integer array you need to return the next greater element.

You can search circularly.

Example

Input: nums = [1,2,1]
Output: [2,-1,2]

For “1” the next greater element is 2.
For “2” there is no next greater element “-1”
For “1”, the next greater element is “2”, if you search circularly.

Solution

We can reduce this problem to next greater element problem by concatenating the array.

Suppose the array is “1,2,1”, we concatenate the same array [1, 2, 1, 1, 2, 1].
Then we find the next greater element and display the result.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

void get_next_greater_element(vector<int>& nums) 
{
    int n = nums.size();
    nums.resize(2*n);
    
    //concatenate the same array
    for(int i=n; i<2*n; i++) 
    {
        nums[i] = nums[i-n];
    }
    
    //final result to be returned
    vector<int> res(n, -1);

    stack<int> st;
    
    for(int i=0; i<2*n; i++)
    {
        int ele = nums[i];
        
        while(!st.empty() && ele > nums[st.top()])
        {
            if(st.top() >= n) 
            {
                st.top() = st.top() - n;
            }
            
            res[st.top()] = ele;
            st.pop();
        }
        
        st.push(i);
    }
    
    cout<<"The next greater element is "<<endl;

    for (auto i = res.begin(); i != res.end(); ++i)
        cout << *i << " ";

    return;
}

int main()
{ 
  vector<int> arr = {1, 2, 1};
  get_next_greater_element(arr);
}

Output:

The next greater element is
2 -1 2