Next Greater Element

Question

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int arr[n];
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        stack<int>s;
        stack<int>q;
        for (int i = n - 1; i > 0; i--)
        {
            s.push(arr[i]);
        }
        while (!s.empty())
        {
            int a = s.top();
            s.pop();
            int flag = 0;
            while (!s.empty())
            {
                int p = s.top();
                if (a >= p)
                {
                    q.push(p);
                    s.pop();
                }
                else {
                    cout << p;
                    flag = 1;
                    break;
                }
                p = s.top();
            }
            if (flag == 0)
            {
                cout << -1;
            }
            while (!q.empty())
            {
                s.push(q.top());
                q.pop();
            }

        }
    }
    return 0;
}

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1. Why is this code giving segmentation fault?

Answer 1

#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int test;
cin >> test;
while(test--)
{
    int n;
    cin >> n ;
    vector<int>v(n);
    for(int i=0;i<n;i++)
    cin >> v[i];
    vector<int>output(n,-1);
    stack<int>s;
    s.push(0);
    for(int i=0;i<n;i++)
    {
        while(!s.empty() && v[s.top()]<v[i])
        {
            output[s.top()]=v[i];
            s.pop();
        }
        s.push(i);
    }
    for(auto x:output)
    cout << x << " ";
    cout << "\n";
}
return 0;
} 

---

SAMPLE INPUT : 1 4 4 5 2 25 SAMPLE OUTPUT: 5 25 25 -1

Answer 2

Solution in Python

a = [1, 5, 2, 9]

a.reverse()

if a == sorted(a):
    print("No")
else:
    for i in range(len(a)-1):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            break

a.reverse()
print(a)

Output : [1, 5, 9, 2]

Answer 3

After solving the issue in my previous answer, one could based on @VladFromMoscow's comment, and use loops to achieve this, without using two additional data structures.

The strategy could be the following:

For every element `e` in the array
  Check if next element of `e` is greater than `e`
    If yes, print it

That implies the use of two for loops, where the first loop would scan the whole array. The second loop would scan the array from the next element of e, until the end of the array.

Note: You can skip the last element in the first loop, since it's guaranteed not to have any next element (thus no greater next element as well).

However, it might be that you need to store these greater elements, and for sure you could use a stack (LIFO Data Structure) for that, but I find it more natural to use a FIFO Data Structure, such as a queue. An array could also be used, for sure.

Notice that even in the case that you need to store the elements, with this loop-based approach, you use one additional data structures, not two (as in your code).

Example:

#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
  int n;
  cin >> n;
  if(!n)
  {
    cout << "Array will be empty, exiting..\n";
    return 1;
  }
  int arr[n];
  for (int i = 0; i < n; i++)
  {
    cin >> arr[i];
  }
  queue<int> q;
  // start 1st element until pre-last.
  for(int i = 0; i < n - 1; ++i)
  {
    // start from next element of i-th element, until last.
    for(int j = i + 1; j < n; ++j)
    {
      if(arr[j] > arr[i])
      {
        q.push(arr[j]);
        break;
      }
    }
  }
  while(!q.empty())
  {
    cout << q.front() << ", ";
    q.pop();
  }
  // last element of array does not have any next element
  cout << "-1\n";
  return 0;
}

Input:

3 1 2 3

Output:

2, 3, -1

Note: If you don't need to store the next greater elements, then simply print arr[j] instead of doing q.push(arr[j]);, and then break the loop.

Answer 4

Change this:

for (int i = n - 1; i > 0; i--)

to this:

for (int i = n - 1; i >= 0; i--)

since you want to push all elements to the stack.

After that, for this input:

1
3
1
2
3

I got the expected output:

23-1

Note: As @John said, p = s.top(); does nothing, so it can safely be removed (since p is going to go out of scope anyway).

Answer 5

p=s.top();

Crash here I suspect. No guarantee that s is not empty at that point.

The line of code has no effect (except maybe crashing the program) since p is a local variable about to go out of scope. It can be safely removed.