Stack: Given an array, you need to find the previous greater element

Problem Statement:

Given an array of distinct elements, you need to find the previous greater element.

If there is no greater element, return -1.

Example:

Input: [11, 5, 3, 21, 41, 15, 35]
Output: [-1, 11, 5, -1, -1, 41, 41]

Solution 1: Naive Approach

Run 2 nested loops.

Outer loop pick an element and take the inner loop to find the previous element that is greater.

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution 2: Efficient Solution

We will use stack DS.

We maintain previous greater element in the stack.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream> 
#include <stack> 
using namespace std;

void solution_1(int arr[], int n)
{ 
    // initially for index 0, the value will be -1
    cout << "-1, ";

    // check for the next elements 
    for (int i = 1; i < n; i++) 
    {

        int j;

        for (j = i-1; j >= 0; j--) 
        {
            if (arr[i] < arr[j]) 
            {
            	cout << arr[j] << ", ";
            	break;
            }             
        }

        // if all the elements on left smaller
        if (j == -1)
        cout << "-1, ";
    }
    cout<<endl;
}

void solution_2 (int arr[], int n)
{
    // create a stack and push the first element
    stack<int> s;
    s.push(arr[0]);
        
    cout << "-1, ";

    for (int i = 1; i < n; i++) 
    {

        while (s.empty() == false && s.top() < arr[i])
            s.pop();

        s.empty() ? cout << "-1, " : cout << s.top() << ", ";

        s.push(arr[i]);
    }
}

int main()
{
    int arr[] = { 11, 5, 3, 21, 41, 15, 35 };
    int n = sizeof(arr) / sizeof(arr[0]);
    solution_1(arr, n);
    solution_2(arr, n);
    return 0;
}

Output

-1, 11, 5, -1, -1, 41, 41, 
-1, 11, 5, -1, -1, 41, 41,