We will be discussing the solution for both arrays and circular arrays. Once the logic for an array is clear, with minor changes the logic for the latter could be implemented easily.

1. Arrays

Problem Statement: For every element in the array, print the next greater element in the order of traversal from left to right. If no such element exists then print -1.

Example: Input: [1, 2, 5, 3] Output: [2, 5, -1, -1]

a. Bruteforce Solution

void printNGE(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        int next = -1;
        for(int j = i + 1; j < n; j++) {
            if(arr[j] > arr[i]) {
                next = arr[j];
                break;
            }
        }
        if(next == -1)
            cout << -1 << " ";
        else
            cout << next << " ";
    }
}

The above solution is pretty straightforward and takes O(n^2) time complexity. For every element we run a loop from its adjacent element, printing the first element greater than the current element under consideration. If no such element is encountered, we print '-1', indicating the absence of the next greater element.

b. Using Stack

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

vector<int> findNGE(int arr[], int n) {
    vector<int> result(n);
    stack<int> s; // store the indices of the elements.
    // for the last element
    for(int i = n - 1; i >= 0; i--) {
        while(!s.empty() and arr[s.top()] <= arr[i]) {
            s.pop();
        }
        result[i] = s.empty() ? -1 : arr[s.top()];
        s.push(i);
    }
    return result;
}

int main() {

    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    vector<int> result;
    result = findNGE(arr, n);    
    for(int i : result) {
        cout << i << " ";
    }

    return 0;
}

We will be using a vector to store the next greater element of the current array element under consideration. The answer for the last array element will always be '-1' since there is no element after that. The stack will be used in storing the index of the elements as this resolves the issue of duplicates if present in the array.

We will start iterating the loop from the last element.

while(!s.empty() and arr[s.top()] <= arr[i]) {
            s.pop();
        }

If the array element at the top of the stack is <= the current element, then arr[i] could be a candidate for the next greater element, hence we should pop the element at the top of the stack.

Note: The = sign plays a very important role as we are storing indices instead of array elements.

With the help of this loop, we will keep popping the elements of the stack until either the next greater element is encountered or the stack becomes empty.

result[i] = s.empty() ? -1 : arr[s.top()];

If the stack becomes empty, it indicates that there is no greater element on the right side of the current array element else the answer would be the array element at the index present at top of the stack.

With the help of this approach, the time complexity reduces to O(n) with extra space complexity of O(n).

2. Circular Arrays

Problem Statement: For every element in the array, print the next greater element. To find the next greater number for element A[i] , start from index i + 1 and go upto the last index after which we start looking for the greater number from the starting index of the array since array is circular. If no such element exists then print -1.

Example: Input: [4, -2, 5, 9, 8] Output: [5, 5, 9, -1, 9]

The approach to this problem is similar to the one discussed above. Let us unroll this circular array to make it a normal array. After unrolling the array becomes [4, -2, 5, 9, 8, 4, -2, 5, 9 , 8] Simply add the elements once again at the end of the array.

Apply the same logic to this normal array. There is no need to create a new array of size 2*n as we can use % operator to save us from the trouble.

a. Bruteforce Solution

void preintNGE(int arr[], int n) {
    for(int i = 0; i < n; i++) {
        int next = -1;
        for(int j = i + 1; j < n + i; j++) {
            if(arr[j % n] > arr[i]) {
                next = arr[j % n];
                break;
            }
        }
        if(next == -1)
            cout << -1 << " ";
        else
            cout << next << " ";
    }
}

For every element, we will traverse the array from i+1 till n + i - 1. This traversal includes going from left to right via i+1 to n and going right to left via 0 to n + i - 1.

For example: arr[] = {4, -2, 5, 9, 8}; n = size of array = 5

For element 5 at index '2'.
We will look for the first greater element 
from index j = i + 1 to n + i - 1.
ie indices 3 to 6
{3, 4, 5, 6 } % n = {3, 4, 0, 1}

Hence, by utilizing the % operator, we no longer need to reallocate an array of double the size of the current array.

b. Using Stack

 vector<int> findNGE(int arr[], int n) {
        vector<int> result(n); // to store the result
        stack<int> s; // to store the indices of the next greater number.
        // we are not storing numbers because of duplicates

        for(int i = 2 * n - 1; i >= 0; i--) {
        while(!s.empty() and arr[s.top()] <= arr[i%n]){
                s.pop();
            }
            result[i % n] = s.empty() ? -1 : arr[s.top()];
            // push the current index on the stack
            s.push(i % n);
        }
        return result;
 }

The code is similar to above discussed logic with 2 minor changes.

1. The last index of the array would be 2*n-1 since we rolled out the circular array.
2. Take % of the indices to avoid index out of bound error.

The remaining code stays exactly the same.

So if you understand the logic for a given problem then deriving the logic for the related problems become easy.

Hope you liked this article. Connect with me on github and linkedin.