Next Greater Element

In this article, we will solve the problem of finding the next greater element for each element in an array.

Problem Statement: Given an array of integers, the task is to find the next greater element (NGE) for every element in the array. The next greater element for an element x is the first greater element on the right side of x in the array. If no such element exists, output -1 for that element.

Examples:

Input: arr = [4, 5, 2, 25] Output: [5, 25, 25, -1]

Explanation:

• The next greater element for 4 is 5.

• The next greater element for 5 is 25.

• The next greater element for 2 is 25.

• There is no greater element for 25, so the output is -1.

Solution:

To solve this problem efficiently, we will use a stack to keep track of the elements for which we are yet to find the next greater element.

Steps to Solve:

1.    Initialize an Empty Stack:

o   Use a stack to store indices of the elements.

2.    Iterate Through the Array:

o   For each element in the array:

§  While the stack is not empty and the current element is greater than the element corresponding to the index on the top of the stack, update the next greater element for the element at the index on the top of the stack and pop the stack.

§  Push the current index onto the stack.

3.    Handle Remaining Elements in the Stack:

o   After processing all elements, the elements left in the stack do not have any greater elements on their right. Set their next greater element as -1.

Time Complexity: O(N)

Space Complexity: O(N)