Given a circular integer array arr[] of length N, the task is to return the next greater element for every element in arr[].
The next greater element for an element is the first greater element on the right side of the array.
If no greater element exists, consider the next greater element as -1.
Input: arr[] = [3, 2, 8, 7, 6, 17, 12], Output: [8, 8, 17, 17, 17, -1, 17]
Input: arr[] = [4, 5, 2, 25, 10], Output: [5, 25, 25, -1, 25]
Solutions
Method 1: Using Stack
This problem is a variant of this, and can be solved easily using a Stack.
The idea is to maintain elements in a stack in descending order so that for every element in the array, the next greatest element can be obtained from the stack.
Traverse the array from the right and keep removing elements from the stack until the top element in the stack is less than the current element in the array.
If the stack is still not empty, the top () element will be the next greater for the current element in the array; otherwise, assign -1.
In order to make it work in a circular array, we need to consider the array twice, i.e., run the loop from 2n-1 to 0. Also, use index "i" as "i% n" to avoid out-of-bounds errors.
Complexity
The time complexity of this solution is O(N) and space complexity is O(N).