Next Largest Element using Stack in C++

Hello Guys, in this article we will provide you the code of the Next Largest Element also known as Nearest Greater to Right. We will solve this problem with the use of the Stack of Nearest Greater to Right also known as the Next Largest Element.

The idea is to store the elements for which we have to find the next greater element in a stack and while traversing the array, if we find a greater element, we will pair it with the elements from the stack till the top element of the stack is less than the current element.

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

We earn a commission if you make a purchase, at no additional cost to you.

Approach to Finding the Next Largest Element

To find the next largest element using a stack, we traverse the array from left to right. For each element, we push it onto the stack. If the next element is larger than the top element of the stack, we have found the next largest element for that particular element. We continue this process until we have processed all the elements in the array.

Steps to Solve the Problem

  • Push the first element to stack.
  • Pick the rest of the elements one by one and follow the following steps in the loop.
    • Mark the current element as next.
    • If the stack is not empty, compare top most elements of the stack with the next.
    • If the next is greater than the top element, Pop the element from the stack. next is the next greater element for the popped element.
    • Keep popping from the stack while the popped element is smaller than the next. next becomes the next greater element for all such popped elements.
  • Finally, push the next in the stack.
  • After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them. 

Implementation in C++

Here’s an implementation of finding the next largest element using a stack in C++:

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

void printNGE(int arr[], int n)
{
	stack<int> s;
	vector<int> v;
	
	for (int i=n-1;i>=0;i--){
		
		if(s.size()==0){
			v.push_back(-1);
		}
		else if (s.size()>0 && s.top()>arr[i]){
			v.push_back(s.top());
		}
		
		else if(s.size()>0 && s.top()<=arr[i]){
			
			while(s.size()>0 && s.top()<=arr[i]){
				s.pop();
			}
			
			if(s.size()==0){
				v.push_back(-1);
				
			}
			else
			{ v.push_back(s.top());
			}
			

		}
		
	s.push(arr[i]);
	}
	
	reverse(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
}

int main()
{
    int arr[] = {4, 5, 2, 10, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    printNGE(arr, n);
    return 0;
}

/// contributed by Iresh Singla

Output

5 10 10 -1 -1

Time Complexity: O(N) 
Auxiliary Space: O(N) 

Time Complexity Analysis

The time complexity of finding the next largest element using a stack in C++ is O(N), where N is the number of elements in the array. This is because we iterate through the array only once.

Benefits of Using Stack for this Problem

Using a stack data structure provides an efficient solution to finding the next largest element. It allows us to traverse the array in a single pass and retrieve the next largest element for each element efficiently.

Conclusion

In this article, we explored the concept of finding the next largest element using a stack in C++. We learned about the stack data structure and how it can be utilized to efficiently solve this problem. With the provided implementation and example code, you should now be able to apply this technique to your own projects.

FAQs

Q1: Can I use this technique for arrays with duplicate elements?

Yes, the technique can handle arrays with duplicate elements. It will find the next largest element based on their positions in the array.

Q2: What happens if there are no larger elements for a particular element?

In such cases, we assign -1 as the next largest element for that element.

Q3: Is the order of elements preserved in the output?

Yes, the order of elements in the output corresponds to their positions in the input array.

Leave a Reply