Find next larger element [Pattern Introduction] in C++

Problem Description:

Given an array A having N elements, the task is to find the next greater element(NGE) for each element of the array in order of their appearance in the array. If no such element exists, output -1. This should be achieved with a time complexity of O(n).
Input format


There are 2 lines of input

The first line contains an integer N denoting the size of the array.

The second line contains N space separated positive integers denoting the values in the array A.

Output format
Print N space separated integers, which are the next greater element for each array element. If no such greater element exists for any element, output -1
Function definition

You have to implement the given function. It accepts the original array as an argument, and returns the new next greater element array.

Constraints
1 <= N <= 10^5
0 <= Values in the array <= 10^9

Sample Input 1
4

1 3 2 4

Sample Output 1
3 4 4 -1

Explanation 1


In the array, the next larger element to 1 is 3 , 3 is 4 , 2 is 4 and for 4, there is no such greater element, hence -1.

Solution:

Here is the implementation of the "next greater element" algorithm in C++:


#include <iostream>
#include <vector>
#include <stack>

std::vector<int> nextGreaterElements(const std::vector<int>& arr) {
int n = arr.size();
std::vector<int> result(n, -1); // Initialize the result vector with -1
std::stack<int> s; // Stack to keep track of the elements for which we need to find the next greater element
// Traverse the array from right to left
for (int i = n - 1; i >= 0; --i) {
// Maintain the stack such that the top of the stack is the next greater element
// for the current element arr[i]
while (!s.empty() && s.top() <= arr[i]) {
s.pop();
}
// If stack is not empty, then the top element is the next greater element
if (!s.empty()) {
result[i] = s.top();
}
// Push the current element onto the stack
s.push(arr[i]);
}
return result;
}

int main() {
// Sample input
int N = 4;
std::vector<int> A = {1, 3, 2, 4};
// Function call
std::vector<int> result = nextGreaterElements(A);
// Print the result
for (int num : result) {
std::cout << num << " ";

}
return 0;
}
//---------- End of Code --------------------------

### Explanation of the Code

1. **Initialization**:

- `result`: A vector initialized to `-1` with the same size as the input vector.

- `s`: A stack used to store elements for which we are trying to find the next greater element.


2. **Traverse the Array from Right to Left**:

- For each element in the array starting from the end:

- **Pop Elements from the Stack**: Remove elements from the stack that are less than or equal to the current element because they can't be the next greater element for the current or any future elements.

- **Update the Result**: If the stack is not empty after the popping, the element on the top of the stack is the next greater element for the current element.

- **Push Current Element to Stack**: Push the current element onto the stack to possibly be the next greater element for future elements.


3. **Output the Result**:

- The `result` vector now contains the next greater elements for each element in the original vector, as required.


This code will correctly compute the next greater element for each element in the input array and print the result. You can compile and run this code using any standard C++ compiler.