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(N2)
Auxiliary Space: O(N)
Alternate Approach: Refer to the previous post of this article for space-optimization of the naive approach.
Time Complexity: O(N2)
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 ith 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 0th 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 Codeint 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 approachimport 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 Codepublic 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{ // Function to find the NGE for the// given circular array []arrstatic 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 Codepublic 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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!