503. Next Greater Element II
Next Greater Element II (LeetCode 503) 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.
How to solve Next Greater Element II
Next Greater Element II is a Monotonic Stack problem, part of Stack Patterns. Master monotonic stack for next greater element, daily temperatures, and stock span problems.
Work towards the solution in these steps:
- Consider how you can efficiently track the next greater element for each item using an auxiliary data structure.
- A stack can help maintain elements for which you haven't found the next greater element yet; think about the properties this stack should have.
- Since the array is circular, you might need to simulate traversing it twice or use modulo operations to handle wrap-around indices.
The reference solution runs in O(n) time and O(n) space.
The Next Greater Element II solution and editorial walks through the full approach with reference code.
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:
- Car Fleet — Medium, same subpattern
- Daily Temperatures — Medium, same subpattern
- Final Prices With a Special Discount in a Shop — Easy, same subpattern
- Find the Most Competitive Subsequence — Medium, same subpattern
- Maximum Width Ramp — Medium, same subpattern
- Next Greater Element I — Easy, same subpattern
Next Greater Element II FAQ
What is the LeetCode number of Next Greater Element II?
Next Greater Element II is LeetCode problem 503, rated Medium.
What pattern is used to solve Next Greater Element II?
Next Greater Element II is a Monotonic Stack problem. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.
What is the time complexity of Next Greater Element II?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Next Greater Element II?
Next Greater Element II has been reported in interviews at Amazon, Bloomberg, Apple, Facebook.