Find the next greater element in a Circular Array | Set 2

0 0 6 minutes read

Given a circular array arr[] consisting of N integers, the task is to print the Next Greater Element for every element of the circular array. Elements for which no greater element exist, print “-1”.

Examples:

Input: arr[] = {5, 6, 7}
Output: 6 7 -1
Explanation: The next greater element for every array element are as follows:
For arr[0] (= 5) -> 6
For arr[1] (= 6) -> 7
For arr[2] (= 7), no greater element is present in the array. Therefore, print -1.

Input: arr[] = {4, -2, 5, 3}
Output: 5 5 -1 4
Explanation: The next greater element for every array element are as follows:
For arr[0] (= 4) -> 5
For arr[1] (= -2) -> 5
For arr[2] (= 5), no greater element is present in the array. Therefore, print -1.
For arr[3] (= 3) -> 4

Naive Approach: The simplest approach to solve this problem is discussed in the previous post of this article.

Time Complexity: O(N²)
Auxiliary Space: O(N)

Alternate Approach: Refer to the previous post of this article for space-optimization of the naive approach.

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to use the concept of Next Greater Element which uses a Stack data structure. Follow the steps below to solve the problem:

Initialize a stack to store the indices of the array and an array nge[] of size N which stores the next greater element for each array element.
Traverse the array and for each index, perform the following:
- If the stack is non-empty and the current i^th array element is greater than the top element of the stack, then pop the top element of the stack and update nge[st.top()] by storing arr[i % N] in it. Repeat this until the stack is empty or the current element is less than the element at the top of the stack.
- If the stack is empty or the current element is less than the top of the stack, push (i % N) into the stack.
After a single traversal of N elements, the stack contains the elements which do not have a next greater element till the (N – 1)^th index. As the array is circular, consider all the elements from the 0^th index again and find the next greater element of the remaining elements.
Since the array is traversed 2 times, it is better to use i % N instead of i.
After completing the above steps, print the array nge[].

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the NGE for the
// given circular array arr[]
void printNGE(int* arr, int n)
{
    // Initialize stack and nge[] array
    stack<int> s;
    int nge[n], i = 0;
 
    // Initialize nge[] array to -1
    for (i = 0; i < n; i++) {
        nge[i] = -1;
    }
    i = 0;
 
    // Traverse the array
    while (i < 2 * n) {
 
        // If stack is not empty and
        // current element is greater
        // than top element of the stack
        while (!s.empty()
               && arr[i % n] > arr[s.top()]) {
 
            // Assign next greater element
            // for the top element of the stack
            nge[s.top()] = arr[i % n];
 
            // Pop the top element
            // of the stack
            s.pop();
        }
 
        s.push(i % n);
        i++;
    }
 
    // Print the nge[] array
    for (i = 0; i < n; i++) {
        cout << nge[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 4, -2, 5, 8 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    printNGE(arr, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find the NGE for the
// given circular array arr[]
static void printNGE(int arr[], int n)
{
     
    // Initialize stack and nge[] array
    Stack<Integer> s = new Stack<>();
    int nge[] = new int[n];
    int i = 0;
 
    // Initialize nge[] array to -1
    for(i = 0; i < n; i++) 
    {
        nge[i] = -1;
    }
    i = 0;
 
    // Traverse the array
    while (i < 2 * n)
    {
         
        // If stack is not empty and
        // current element is greater
        // than top element of the stack
        while (!s.isEmpty() && 
               arr[i % n] > arr[s.peek()])
        {
             
            // Assign next greater element
            // for the top element of the stack
            nge[s.peek()] = arr[i % n];
             
            // Pop the top element
            // of the stack
            s.pop();
        }
        s.push(i % n);
        i++;
    }
     
    // Print the nge[] array
    for(i = 0; i < n; i++)
    {
        System.out.print(nge[i] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 4, -2, 5, 8 };
    int N = arr.length;
 
    // Function Call
    printNGE(arr, N);
}
}
 
// This code is contributed by yashbeersingh42

Python3

# Python3 program for the above approach
 
# Function to find the NGE for the
# given circular array arr[]
def printNGE(arr, n) :
     
    # create stack list
    s = [];
     
    # Initialize nge[] array to -1
    nge = [-1] * n;
 
    i = 0;
 
    # Traverse the array
    while (i < 2 * n) :
 
        # If stack is not empty and
        # current element is greater
        # than top element of the stack
        while (len(s) != 0 and arr[i % n] > arr[s[-1]]) :
 
            # Assign next greater element
            # for the top element of the stack
            nge[s[-1]] = arr[i % n];
 
            # Pop the top element
            # of the stack
            s.pop();
 
        s.append(i % n);
        i += 1;
 
    # Print the nge[] array
    for i in range(n) :
        print(nge[i], end= " ");
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 4, -2, 5, 8 ];
    N = len(arr);
 
    # Function Call
    printNGE(arr, N);
     
    # This code is contributed by AnkitRai01

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
// Function to find the NGE for the
// given circular array []arr
static void printNGE(int []arr, int n)
{
     
    // Initialize stack and nge[] array
    Stack<int> s = new Stack<int>();
    int []nge = new int[n];
    int i = 0;
 
    // Initialize nge[] array to -1
    for(i = 0; i < n; i++) 
    {
        nge[i] = -1;
    }
    i = 0;
 
    // Traverse the array
    while (i < 2 * n)
    {
         
        // If stack is not empty and
        // current element is greater
        // than top element of the stack
        while (s.Count != 0 && 
               arr[i % n] > arr[s.Peek()])
        {
             
            // Assign next greater element
            // for the top element of the stack
            nge[s.Peek()] = arr[i % n];
             
            // Pop the top element
            // of the stack
            s.Pop();
        }
        s.Push(i % n);
        i++;
    }
     
    // Print the nge[] array
    for(i = 0; i < n; i++)
    {
        Console.Write(nge[i] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 4, -2, 5, 8 };
    int N = arr.Length;
 
    // Function Call
    printNGE(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
    // Javascript program for the above approach
     
    // Function to find the NGE for the
    // given circular array []arr
    function printNGE(arr, n)
    {
 
        // Initialize stack and nge[] array
        let s = [];
        let nge = new Array(n);
        let i = 0;
 
        // Initialize nge[] array to -1
        for(i = 0; i < n; i++)
        {
            nge[i] = -1;
        }
        i = 0;
 
        // Traverse the array
        while (i < 2 * n)
        {
 
            // If stack is not empty and
            // current element is greater
            // than top element of the stack
            while (s.length != 0 &&
                   arr[i % n] > arr[s[s.length - 1]])
            {
 
                // Assign next greater element
                // for the top element of the stack
                nge[s[s.length - 1]] = arr[i % n];
 
                // Pop the top element
                // of the stack
                s.pop();
            }
            s.push(i % n);
            i++;
        }
 
        // Print the nge[] array
        for(i = 0; i < n; i++)
        {
            document.write(nge[i] + " ");
        }
    }
     
    let arr = [ 4, -2, 5, 8 ];
    let N = arr.length;
  
    // Function Call
    printNGE(arr, N);
 
// This code is contributed by suresh07.
</script>

Output:

5 5 8 -1

Time Complexity: O(N)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!