Full lesson preview

Find the next greater element in a circular array

Given a circular array of integers, find the next greater element for every entry. Use a monotonic stack and a two-pass approach to achieve O(n) time.

Python practice25 minStacks & QueuesAdvancedLast updated March 27, 2026

Problem statement

You are given a circular array nums of integers. For each element nums[i], find the next greater element to its right considering the array as circular (i.e., after the last element you continue from the first). The next greater element of nums[i] is the first element nums[j] such that j > i (mod n) and nums[j] > nums[i]. If no such element exists, return -1 for that position. Your solution must run in O(n) time and O(n) additional space in the worst case. Use a monotonic stack and iterate the array twice (or simulate a circular pass) to compute answers efficiently. Return a list of integers where the i-th element is the next greater number for nums[i], or -1 if it does not exist.

Task

Implement next_greater_element_circular(nums) that returns an array where each position contains the next greater element to the right in a circular manner, or -1 if none exists.

Examples

Example 1

Input

nums = [1, 2, 1]

Output

[2, -1, 2]

For the first 1 the next greater is 2. For the middle 2 there is no greater element in the circular array, so -1. For the last 1 the next greater (wrapping) is 2.

Input format

A single list of integers nums passed to next_greater_element_circular(nums).

Output format

A list of integers of the same length as nums, where each value is the next greater element or -1.

Constraints

- 1 <= len(nums) <= 10^5 - -10^9 <= nums[i] <= 10^9 - Time complexity: O(n) - Space complexity: O(n)

Samples

Sample 1

Input

[5, 4, 3, 2, 1]

Output

[-1, 5, 5, 5, 5]

5 has no greater element. The others find 5 by wrapping around.