In this article, we will learn a simple algorithm to find the next greater element for every element in the array. For example, if we have an array {2, 4, 7, 1, 6, 8, 11, 5, 14, 12} then for element 6, the next greater element will be 8 and for element 11, the next greater element will be 14, and so on.
Problem Statement
You are given an array consisting of some integer values, you have to find the next greater element for every element, if not found, print -1.
For the rightmost element of an array, the next greater element will always be -1. And for an array sorted in descending order, none of the elements will have a greater element to their right hence for all the elements of a decreasing order array, -1 will get printed.
Brainstorming
While thinking of a solution for finding the next greater element for every element in a given array, the first thing that should appear to us is traversing the array and comparing each element with its next elements till the last element of the array and if we find a greater number then printing its value else printing -1.
But for this solution, we need two loops, the outer loop to traverse the elements of the array and an inner loop that starts from the next element(from the element picked up by the outer loop) till the last element. The time complexity of the algorithm will be O(n^2), and the best case will be when all the array elements are sorted in increasing order but if it is in decreasing order then it will lead to the worst case.
So we may have to look beyond traversing the array using loops.
Using a Stack on the other hand can improve the operation and is a better approach to this problem.
Implementation using Stack
Following are the steps that we must follow when writing this algorithm using Stack data structure.
- If the Stack is empty(which it is initially), then push the element in it.
- Then take the next element from the array, and compare it with the first poped element from the Stack, if the incoming element is greater than it is the next greater element for the top Stack element.
- Similarly compare the incoming element with the next element in Stack(use
pop() method), until we find the first element in the Stack which is greater than the incoming element. In that case, we will push the incoming element into the Stack.
- Then pick another element from the array and repeat Steps 2 and 3.
- In the end, when all the array elements have been traversed, for the remaining elements in the Stack, we can simply print -1.
Algorithm
The algorithm for the above problem statement will be as follows:
Step 1: Declare a stack and push the first array element into the stack.
Step 2: Traverse the array and pick the array element one by one.
Step 3: If the incoming array element is greater than the top element of the stack, then for the top element in the Stack, the incoming element is the next greater element. If not, then push the incoming array element into the Stack.
Step4: When an incoming array element is greater than the top element in the stack, the top stack element is popped out, the incoming array element is printed as the next greater element for it, and then the next top stack element is compared with the incoming array element and so on until we come across a stack element which is greater than the incoming array element.
Step 5: When all the array elements are traversed, check whether the stack is empty or not if the stack is not empty then print the result as -1 for the remaining elements in the stack else terminate the program.
Implementation Of The Above Algorithm
#include<bits/stdc++.h>
using namespace std;
void findnextgreater(int arr[], int n) {
int i;
/* initialize the stack. */
stack<int>s;
/* Push the first element into the stack. */
s.push(arr[0]);
for(i = 1; i < n; i++){
/* While the array is not empty and the current element is greater than the top stack element. */
while(!s.empty() && s.top() < arr[i]) {
/* Print the greater element. */
cout<<arr[i]<<" ";
s.pop();
}
/* Push the current element. */
s.push(arr[i]);
}
/* If no greater element then print -1. */
while(!s.empty()) {
cout<<"-1"<<" ";
s.pop();
}
}
/* Driver function to check the above algorithm. */
int main() {
int arr[] = {11, 13, 21, 3, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
findnextgreater(arr, n);
return 0;
}
The running Time Complexity Of The Above Algorithm is: O(n^2)
Output:
13 21 4 -1 -1 -1
Explanation Of The Above Algorithm:
Let us consider an example for the above algorithm, let the array be as shown in the above diagram.
Now follow the following steps to find the next greater element:
Push the first element i.e. 11 in the stack(on the left) as shown in the above diagram.
Now traverse through the array from the index as 1 and now, since our stack is not empty and the array element at index 1 i.e. 13 which is greater than the element in the stack, hence we will output 13 and pop out the top element from the stack and push the current array element into the stack as shown in the above diagram.
Now since the stack is not empty and also the next array element is greater than the top stack element, so we will output 21 and pop out the top element from the stack and push the current array element into the stack as shown in the above diagram.
Now again the stack is not empty but the current array element i.e. 3 is not greater than the top stack element and hence the number 3 is pushed into the stack as shown in the above diagram.
This time, the stack is not empty and now the current array element i.e. 4 is greater than the top stack element so, we output the current array element and pop out the top stack element and push the current array element as shown in the above diagram.
Now again the stack is not empty and the next array element i.e. 2 is less than the top stack element hence, the current array element is pushed into the stack as shown in the above diagram.
Now the whole of the array is traversed and now we have all the elements whose next greater element is not found in the array, so we will pop them and print -1 with our complete output as shown in the above diagram.
Conclusion
Congratulations! You have now acquired a solid understanding of how to find the next greater element for each element in an array.
By exploring different approaches such as stack-based algorithms, brute-force methods, and optimized solutions, you have expanded your problem-solving toolkit. Remember to consider the time and space complexity of your chosen approach to ensure efficiency when dealing with larger arrays.
As you continue your journey in algorithmic problem-solving, explore additional array-related challenges, refine your skills, and embrace the joy of unraveling complex puzzles.
Frequently Asked Questions(FAQs)
1. What does "next greater element" mean in the context of an array?
The "next greater element" refers to finding the closest greater value to the right of each element in an array. It is the element that comes immediately after the given element and has a value greater than the given element.
2. How can I solve the next greater element problem efficiently?
One efficient approach to solve the next greater element problem is by using a stack-based algorithm. This algorithm allows you to traverse the array from right to left, maintaining a stack of elements in decreasing order. By comparing each element with the stack's top, you can determine the next greater element for that element.
3. What is the time complexity of finding the next greater element using a stack-based algorithm?
Using a stack-based algorithm, finding the next greater element can be achieved in linear time complexity, O(n), where n is the size of the array. This makes it an efficient solution for larger arrays.
4. Are there any brute-force methods to solve the next greater element problem?
Yes, a brute-force approach involves nested loops to compare each element with the subsequent elements in the array. While it provides a straightforward solution, its time complexity is O(n^2), making it less efficient for larger arrays.
5. Can the next greater element problem be solved for arrays with duplicate elements?
Yes, the next greater element problem can be solved for arrays with duplicate elements. In such cases, you can modify the stack-based algorithm by storing the indices of elements in the stack instead of the elements themselves. This way, you can handle duplicates while finding the next greater element efficiently.
You may also like:
