CLOSE

   Algorithm  Stack  Array  Data Structure  
   Technology    Programming

Finding Next Greater Element for every Element in an Array

           
 MARCH 14, 2019   by swapnilkant11

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 the element 6, the next greater element will be 8 and for the 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 right most element of an array, the next greater element will always be -1. And for an array sorted in descending order none of the element will have 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 it's next elements till the last element of the array and if we find a greater number then printing it's 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 which 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 wirting this algorithm using Stack data structure.

  1. If the Stack is empty(which it is initially), then push the element in it.
  2. Then take the next element from the array, 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.
  3. Similarly compare the incoming element with 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.
  4. Then pick another element from the array and repeat Step 2 and 3.
  5. At 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 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.

Step5: When all the array elements are traversed, check while the stack is empty or not if the stack is not empty then print the result as -1 for remaining elements in 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;
}

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 and 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, and so we will pop them and print -1 with our complete output as shown in the above diagram.


SHARE YOUR THOUGHTS WITH US!




       

Made with by Abhishek Ahlawat

© 2019 Studytonight.   All rights reserved.

DMCA.com Protection Status