{"post":"

Given: An array, we have to print the next greater element for each element. The Next greater Element for an element p is the first greater element on the right side of p in array. Elements for which there is no greater element, we consider next greater element as -1.

Example:

Input array: { 37, 23, 64, 10, 25, 7 }\nOutput:\nNext greater element for 37 = 64\nNext greater element for 23 = 25\nNext greater element for 64 = -1\nNext greater element for 10 = 23\nNext greater element for 25 = 37\nNext greater element for 7 = 10

# Brute Force Approach

Code:

#include <iostream>\n\n// prints NGE for all elements of array[]  \nvoid nextgren(int array[], int size)\n{\n    int next;\n    for (int i = 0; i < size; i++)\n    {\n        next = -1;\n        for (int j = i + 1; j < size; j++)\n        {\n            if (array[i] < array[j])\n            {\n                next = array[j];\n                break;\n            }\n        }\n        std::cout << \"Next greater element for \" << array[i] << \" = \" << next << std::endl;\n    }\n}\n\n// Driver Code\nint main()\n{\n    int array[] = { 5, 4, 7, 15 };\n    int size = sizeof(array) / sizeof(array[0]);\n    nextgren(array, size);\n    return 0;\n}\n\n

Output

Next greater element for 5 = 7\nNext greater element for 4 = 7\nNext greater element for 7 = 15\nNext greater element for 15 = -1\n\n

Time Complexity: O(n2).

# Optimised Approach(Using Stack)

Code:

// C++ program to find next greater element using stack\n#include <bits/stdc++.h>\n\n// prints NGE for all elements of array\nvoid nextgren(int array[], int size)\n{\n    std::stack<int> stck;\n    // push first element to stck \n    stck.push(array[0]);\n    // iterating for next elements\n    for (int i = 1; i < size; i++)\n    {\n        if (stck.empty())\n        {\n            stck.push(array[i]);\n            continue;\n        }\n        /*if stck is not empty, then pop an element from stck.\n        If the popped element is smaller than next, then\n        1) print the element and next\n        2) keep popping while elements are smaller and stck is not empty */\n        while ((stck.empty() == false) && (stck.top() < array[i]))\n        {\n            std::cout << \"Next greater element for \" << stck.top() << \" = \" << array[i] << std::endl;\n            stck.pop();\n        }\n        // push next to stck so we can find next greater for it\n        stck.push(array[i]);\n    }\n    /*After iteration is over, the remaining\n    elements in stck do not have the next greater\n    element, so we print -1 for them */\n    while (stck.empty() == false)\n    {\n        std::cout << stck.top() << \" --> \" << -1 << \" (No greater element in given input) \" << std::endl;\n        stck.pop();\n    }\n}\n\n// Driver code\nint main()\n{\n    int array[] = { 6, 10, 12, 9 };\n    int size = sizeof(array) / sizeof(array[0]);\n    nextgren(array, size);\n    return 0;\n}\n\n

Output

Next greater element for 6 = 10\nNext greater element for 10 = 12\n12 --> -1 (No greater element in given input) \n9 --> -1 (No greater element in given input) \n\n

Time Complexity: O(n).

\n","title":"Program to find Next Greater Element","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"description":"Find the next greater element (NGE) in a given array of integers using brute force and optimal algorithms with this program. ","slug":"next-greater-element-problem/","articleId":"636a83447bb1ce5072622b5d","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}