Next Greater Element In An Array

This blog will discuss the famous interview problem: find the Next greater element in an array that has been previously asked in companies like Amazon, Samsung, Zoho, Payu, etc.

Problem Statement: An array of elements is given. The task is to find the next greater for each element in the array. If there is no greater element to the right of the element, then return -1.

Example:

Input: 2 1 4 3
Output: 4  4 -1 -1

Explanation:

• 4 is the next greater element after 2.
• 4 is the next greater element after 1.
• There is no next greater element after 4, so -1 is printed.
• There is no next greater element after 3, so -1 is printed.

Recommended: Please try to solve the “ Next Greater Element” on GFG first before moving on to the solution.

Now let’s see various approaches to find the next greater element in an array.

Brute force approach

The outer loop traverses the array from left to right. The inner loop will compare the current element with all the elements to its right until it finds an element greater (in the next greater element function) than the current element. If no such element is present, -1 is printed.

Steps:

1. Traverse the array from left to right in the outer loop.
2. Initialize nextGreater with -1.
3. In the inner loop, traverse the array through the elements at the right of the current element.
4. In the next greater function: if any element greater than the current element is present, the next greater element is obtained.

Code:

Complexity Analysis:

• Time Complexity: O(n²)as two nested for loops are used.
• Space Complexity: O(1) as no extra space is required.

Where “n” is the size of the array.

Stack approach

In this approach, a monotonic stack is used. In the case to find the next greater element, decreasing monotonic stack is used.

In a decreasing monotonic stack, the top element is removed if the element to be inserted is greater than the top element. This procedure is repeated until the monotonic stack becomes empty or the top element is greater than the item to be inserted.

Steps:

1. Initialize a stack and array.
2. Traverse the array from the end.
3. Update the monotonic stack as explained above.
4. Add the next greater element in the array. If the stack is empty, i.e., no element is present, then add -1.
5. Add the current element to the stack.

Code:

Complexity Analysis:

• Time Complexity: O(n) as only a single traversal is required.
• Space Complexity: O(n) as extra space is required for the stack and array.

That’s it from my side, I hope you found this post useful 😊.

Let’s get connected on Github/LinkedIn/Website/Twitter/Quora ;)

And if you have any suggestions, feel free to get in touch with me over LinkedIn & the comment section is also all yours.

If you liked this story, hit the clap button as it motivates me to write more & better.