Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Method 1 - Brute force 
3.
Method 2 - Using stack
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Next Greater Element

Author Aditi
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The next greater element is to find the greater element from the previous one. In the program, you will be given an array of numbers. Now, the task is to find the element greater than the element present in the current index of the array. In this blog, we will see different ways by which we will achieve this result. For better understanding, see the example given below.

Given array : [5, 10, 4, 12, 2]

Element -> Next greater element
5 -> 10
10 -> 12
4 -> 12
12 -> -1
2 -> -1

Note : 

  1. If the array elements are in decreasing order, all elements will have their next greater element as -1.
  2. The rightmost element always has -1 as the next greater element in an array.

Also read, Application of Oops

Method 1 - Brute force 

It is the simplest way to get the next greater element. In this, we will use two loops where the outer loop will pick elements one by one, and the inner loop will look for the next greater element. If found, then print the element; otherwise, print -1.

#include<iostream>
using namespace std;

void nextGreaterEle(int numArr[])
{
    int nge, i, j;
    for (i = 0; i < 5; i++)
    {
        nge = -1;
        for (j = i + 1; j < 5; j++)
        {
            if (numArr[i] < numArr[j])
            {
                nge = numArr[j];
                break;
            }
        }
        cout << numArr[i] << " -> "<< nge << endl;
    }
}

int main()
{
    int arr[] = {5, 10, 4, 12, 2};
    nextGreaterEle(arr);
    return 0;
}

Output:

5 -> 10
10 -> 12
4 -> 12
12 -> -1
2 -> -1

The time complexity of the above code is O(n^2), and space complexity is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Method 2 - Using stack

The other way to program is by using a stack data structure. First, push only the first element from the array to the stack. Then pick left-out elements of the array one by one and follow the steps in the loop.

  • Mark current element as nge.
  • Compare the top element of the stack if not empty with nge.
  • If the top element is less than nge, then pop element from the stack. Popped element will have the next greater element in nge.
  • Keep following the above step while the popped element is smaller than nge. Nge will be the next greater element for all those elements.

After that, push the nge element in the stack. After the loop is finished, pop each element and print -1 as their next greater element for them.

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

void nextGreaterEle(int numArr[])
{
    stack<int> st;
    st.push(numArr[0]);
    for (int i = 1; i < 5; i++)
    {
        if (st.empty()) {
            st.push(numArr[i]);
            continue;
        }

        while (st.empty() == false && st.top() < numArr[i])
        {
            cout << st.top()<< " -> " << numArr[i] << endl;
            st.pop();
        }

        st.push(numArr[i]);
    }
 
    while (st.empty() == false) {
        cout << st.top() << " -> " << -1 << endl;
        st.pop();
    }
}
 
/* Driver code */
int main()
{
    int arr[] = {5, 10, 4, 12, 2};
    nextGreaterEle(arr);
    return 0;
}

Output:

5 -> 10
10 -> 12
4 -> 12
12 -> -1
2 -> -1

The time complexity of the above code is O(n) and space complexity is also O(n).

The worst case of the above program will occur when all elements are present in decreasing order. In this case, each element will be processed at most four times. This program may also print the output in a different order.

So, to reduce complexity and get the output in the same order, we can traverse from behind, i.e., in reverse order. Implementation of this is shown below through codes.

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

void nextGreaterEle(int numArr[])
{
    stack<int> s;
    int res[5];
    for (int i = 4; i >= 0; i--) {

        if (!s.empty()) {
            while (!s.empty() && s.top() <= numArr[i]) {
                s.pop();
            }
        }
        res[i] = s.empty() ? -1 : s.top();
        s.push(numArr[i]);
    }
    for (int i = 0; i < 5; i++)
        cout << numArr[i] << " -> " << res[i] << endl;
}
// Driver Code
int main()
{
    int arr[] = {5, 10, 4, 12, 2};
    nextGreaterEle(arr); // Function call
    return 0;
}

Output:

5 -> 10
10 -> 12
4 -> 12
12 -> -1
2 -> -1

Time and space complexity will be the same, i.e., O(n).

Try and compile by yourself with the help of online C++ Compiler for better understanding.

Also read -  Decimal to Binary c++

FAQs

  1. Which data structure is used to find the next greater element with an array?
    Stack is used with the array in the program.
     
  2. What are the different functions used that are related to the stack?
    push(), pop(), empty() and top() are the inbuilt functions of stack that are used in the program.
     
  3. How can we find the size of the array in the program?
    The size of an array can be calculated with the help of the sizeof() function.
    Size = sizeof(arr) / sizeof(arr[0]) will be used.

Key Takeaways

In this article, we have extensively discussed how to find the next greater element and its implementation in C++. The blog contains different ways by which we can find the next greater element with their time complexity and space complexity.

Check out this problem - Next Smaller Element

We hope that this blog has helped you enhance your knowledge of finding the next greater element. Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Count the number of occurrences in a sorted Array
Next article
Turn an image by 90 degrees
Live masterclass