Next Greater Element II

Next Greater Element II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.

Problem statement

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

Input: nums = [1,2,3,4,3] Output: [2,3,4,-1,4]

Constraints:

- 1 <= nums.length <= 104

- -109 <= nums[i] <= 109

Topics and companies

Topics: Array, Stack, Monotonic Stack.

Reported in interviews at Amazon, Bloomberg, Apple, Facebook.

How to practise Next Greater Element II on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Next Greater Element II in the code editor, or read the Next Greater Element II editorial for a worked solution with its approach and complexity analysis.

Where Next Greater Element II sits in the DSA pattern sheet

Problems related to Next Greater Element II

Other problems that use the same Monotonic Stack and Stack Patterns techniques:

Opening the problem

Progress is saved as you study.