Next greater element problem

[1vf9z8AR]

There is an input of a number N. Then there are N inputs in the next line.

Each input denotes the height of the Nth building.
Spiderman can only go to next higher building.

How many buildings can spiderman go to for each building?

for input
5
1 2 2 3 1
output
2 1 1 0 0

My logic:
Using a stack to find the next greater element during input.
Use the already found values to compute the answer.

  #include<iostream>
#include<stack>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n],nge[n];
    stack<int>s;
    for(int i=0;i<n;i++)
    {
        nge[i]=0;
        cin>>arr[i];
        if(s.empty()==true)
            s.push(i);
        else
        {
            while(arr[s.top()]<arr[i] && s.empty()==false)
            {
                nge[s.top()]=arr[i];
                s.pop();
            }
            s.push(i);
        }
    }
    while(s.empty()==false)
    {
        nge[s.top()]=0;
        s.pop();
    }
    for(int i=0;i<n;i++)
        cout<<nge[i]<<" ";
}

No output is coming.

[Handy Andy]

Hello suyashsing234,

The first problem I found if line 8. "n" has to be a constant value either 10 or a variable defined as a constant. This type of array needs a constant value at compile time so the compiler will know how much memory to set aside for the array.

If you need to input a value for "n" and use it then you will have to create a dynamic array.

For what you have you are stuck with something like this:

int main()
{
	constexpr int MAXSIZE{ 10 };

	int n;
	cin >> n;
	int arr[MAXSIZE], nge[MAXSIZE];
	stack<int> s;

Now that it compiles I will test it shortly and see if I find anything else.

Hope that helps,

Andy

[Thomas1965]

@Handy Andy,
this looks like a problem on codechef or spoj where they use GCC so the use of VLA isn't a problem.

[Handy Andy]

@Thomas1965,

Thank you. That is nice to know.

Andy