Find the next greater element for every element in a circular array

Posted by on Mar 31, 2024

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).

Related


Implementation of Stack data structure using Array

Implement Queue using Stack in amortized O(1) time

Find the next greater element for every element in an array

Implement Stack using Queue (using single queue)

Implementation of Queue data structure using Array