Find the next greater element in a Circular Array | Set 2
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 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)
Contact Us