503. Next Greater Element II
Problem Description
The problem gives us a circular integer array, which means that after the last element of the array, it wraps around back to the first element. We are tasked with finding the next greater number for each element in the array. The "next greater number" is defined as the first number that is bigger than the given number when you traverse the array from the current position, considering the circular nature of the array. If no such number exists, we are to return -1
for that element.
Example: Suppose the array is [1, 2, 1]
. For the first element (1), the next greater number is 2. For the second element (2), there is no greater number in the array, so the output is -1. For the last element (1), the next greater number is again 2 because we can traverse the array circularly.
Intuition
To solve this problem, we need to consider each element and find the next element that is greater than it. Since the array is circular, we can't just iterate linearly from the start to the end. Once we reach the end, we need to loop back to the beginning of the array and continue our search. This effectively doubles the "length" of our search space.
A naive approach would be to check each element against all others, but this would be inefficient with time complexity O(n^2), where n is the length of the array. Instead, we can use a stack to keep track of the indices of elements for which we haven't found the next greater number yet.
Here is the intuition for how the efficient solution works:
- Create an array
ans
to store the next greater numbers, initialized with-1
, signifying we haven't found the answer for any element yet. - Use a stack to store the indices of elements in decreasing order of their values.
- Iterate through the array twice (because it's circular) using the index
i
. For each element:- While there is an element in the stack, and the current element is greater than the element pointed to by the index at the top of the stack (
nums[stk[-1]] < nums[i % n]
), it means we have found the next greater number for the element at the top of the stack. We then pop the index from the stack and update theans
array. - Push the current index modulo the length of the array
i % n
onto the stack. This ensures we are in bounds of the array when the loop wraps around.
- While there is an element in the stack, and the current element is greater than the element pointed to by the index at the top of the stack (
- The reason to loop twice is to simulate the circular array by giving each element a second chance to find its next greater value.
By using the stack, each element is pushed and popped at most once, yielding a linear time complexity solution, O(n), where n is the length of the array.
Learn more about Stack and Monotonic Stack patterns.
Solution Approach
The reference solution provided uses a stack to keep track of the indices of elements for which we need to find the next greater number. Let's break down the steps taken in the implementation:
-
Initialize Necessary Variables:
- Calculate the length of the
nums
array and store it in a variablen
. - Create an answer array
ans
of the same length asnums
, initialized with-1
. This will hold the next greater elements for the respective indices. - Initialize an empty list
stk
which will serve as the stack.
- Calculate the length of the
-
Double Iteration Over The Array:
- Iterate over a range that is double the length of
nums
to simulate the circular nature of the array. The current index in the array is given byi % n
.
- Iterate over a range that is double the length of
-
Finding the Next Greater Element Using Stack:
- As we iterate, we continuously check whether the stack is non-empty and the current number
nums[i % n]
is greater than the number at the index at the top of the stacknums[stk[-1]]
. - If that's the case, we have found a next greater number for the element at the top of the stack. We update the
ans
array at the index popped from the stack with the current number. - This process is repeated until no such element is found or the stack becomes empty.
- As we iterate, we continuously check whether the stack is non-empty and the current number
-
Maintain Decreasing Stack:
- Each index
i % n
is added to the stack. The modulo operation ensures we cycle back to the starting indices after reaching the end of the array. - The stack maintains indices of elements in decreasing order. When an element with a greater value comes up, it signifies the "next greater number" for all elements on the stack it is compared against.
- Each index
-
Return the Answer:
- The
ans
array now contains either the next greater elements for each index, or-1
if no greater element was found in the circular traversal. Theans
array is returned as the final result.
- The
The key patterns used in this implementation are stack usage for maintaining a decreasing sequence and modulus arithmetic to handle circular array traversal efficiently. This algorithm is efficient because each element is pushed onto the stack once and popped at most once, leading to a time complexity of O(n), where n is the length of the nums
array.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use an example to illustrate the solution approach described above. Suppose we are given the circular array nums = [4, 1, 2]
.
-
Initialize Necessary Variables:
- The length of
nums
isn = 3
. - We create an answer array
ans = [-1, -1, -1]
. This will hold the next greater elements. - We initialize an empty list
stk
as our stack.
- The length of
-
Double Iteration Over The Array:
- We loop over the range of
2n
, which is6
in this case, to simulate the circular array.
- We loop over the range of
-
Iteration Details:
-
First Pass ([4, 1, 2]): We start with
i = 0
(i % n = 0
), and the stack is empty. We push the index0
to the stack. -
Move to
i = 1
(i % n = 1
).nums[1] = 1
is not greater thannums[0] = 4
, so we push1
onto the stack. -
Move to
i = 2
(i % n = 2
).nums[2] = 2
is not greater thannums[1] = 1
but is also not greater thannums[0] = 4
, so we push2
onto the stack. -
Second Pass ([4, 1, 2] again):
-
Now,
i = 3
(i % n = 0
).nums[3 % n] = nums[0] = 4
is not greater thannums[2] = 2
, so nothing changes. -
Move to
i = 4
(i % n = 1
).nums[4 % n] = nums[1] = 1
is not greater thannums[2] = 2
or thannums[0] = 4
. Nothing changes. -
Move to
i = 5
(i % n = 2
).nums[5 % n] = nums[2] = 2
. Here, we seenums[2] = 2
is greater thannums[1] = 1
which is at the top of the stack. So, we pop1
from the stack and updateans[1]
to2
. Nowstk = [0, 2]
.
-
-
Finish the Stack Processing:
- Since we reached the end of our second pass and there is no greater element for indices
0
and2
, we leave their corresponding values inans
as-1
.
- Since we reached the end of our second pass and there is no greater element for indices
-
Return the Answer:
- Our answer array
ans
is now[-1, 2, -1]
, which correctly reflects that the next greater number for the first element (4
) doesn't exist in the array, for the second element (1
) the next greater number is2
, and for the third element (2
) there is no next greater number considering the circular nature of the array. We returnans
as the result.
- Our answer array
Solution Implementation
1class Solution:
2 def nextGreaterElements(self, nums):
3 """
4 Finds the next greater element for each element in a circular array.
5
6 :param nums: List[int] - List of integers where we need to find the next greater element for each.
7 :return: List[int] - List containing the next greater elements.
8 """
9 # The number of elements in the input list.
10 n = len(nums)
11
12 # Initialize the result list with -1 for each element.
13 result = [-1] * n
14
15 # Stack to keep indexes of nums for which we haven't found the next greater element.
16 stack = []
17
18 # Iterate over the list twice to simulate circular array behavior.
19 for i in range(2 * n): # Shorthand for n << 1.
20 # Get the index in the original nums array.
21 index = i % n
22
23 # While stack is not empty and the current element is greater than the element at
24 # the index of the last element in stack, update the result for the index at the
25 # top of the stack.
26 while stack and nums[stack[-1]] < nums[index]:
27 result[stack.pop()] = nums[index]
28
29 # For the first pass, we need to fill the stack with index.
30 # Avoid pushing index onto the stack in the second pass to prevent duplicating work.
31 if i < n:
32 stack.append(index)
33
34 # Return the result list containing next greater elements.
35 return result
36
1import java.util.Arrays;
2import java.util.Deque;
3import java.util.ArrayDeque;
4
5class Solution {
6 public int[] nextGreaterElements(int[] nums) {
7 // Determine the length of the input array.
8 int n = nums.length;
9 // Initialize the answer array with -1 (assuming no next greater element).
10 int[] answer = new int[n];
11 Arrays.fill(answer, -1);
12 // Use a deque as a stack to keep track of indices.
13 Deque<Integer> stack = new ArrayDeque<>();
14
15 // Iterate through the array twice to simulate a circular array.
16 for (int i = 0; i < 2 * n; ++i) {
17 // While the stack is not empty and the current element is greater than the
18 // element at index at the top of the stack - it means we have found the
19 // next greater element for the index at the top of the stack.
20 while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
21 // Update the answer for the index at the top of the stack.
22 answer[stack.pop()] = nums[i % n];
23 }
24 // If this index is within the original array, push its index on the stack.
25 // During the second iteration, we don’t push the index into the stack
26 // to avoid duplicates.
27 if (i < n) {
28 stack.push(i);
29 }
30 }
31 // Return the answer array with next greater elements for each index.
32 return answer;
33 }
34}
35
1#include <vector>
2#include <stack>
3
4class Solution {
5public:
6 // Function to find the next greater elements for each element in a circular array.
7 vector<int> nextGreaterElements(vector<int>& nums) {
8 int n = nums.size(); // Size of the input array
9 vector<int> answers(n, -1); // Initialize the answer vector with -1, which means no greater element
10 stack<int> indicesStack; // Stack to store the indices of elements
11
12 // Loop through the array twice to simulate circular array traversal.
13 for (int i = 0; i < 2 * n; ++i) {
14 // While stack is not empty and the current element is greater
15 // than the element corresponding to the index on the top of the stack
16 while (!indicesStack.empty() && nums[indicesStack.top()] < nums[i % n]) {
17 // Update the answer for the index at the top of stack as we have found
18 // a next greater element
19 answers[indicesStack.top()] = nums[i % n];
20 // Pop the index from the stack as we've found a next greater element for it
21 indicesStack.pop();
22 }
23
24 // We only push the index of the element to the stack
25 // as long as we are in the first iteration over the array.
26 if (i < n) {
27 indicesStack.push(i);
28 }
29 }
30 return answers;
31 }
32};
33
1function nextGreaterElements(nums: number[]): number[] {
2 // Stack to keep indexes where we haven't found the next greater element yet
3 const indexStack: number[] = [];
4 const length = nums.length;
5 // Result array initialized with -1, assuming we don't find a next greater element
6 const result: number[] = new Array(length).fill(-1);
7
8 // Iterate twice over the array to simulate a circular array
9 for (let i = 0; i < 2 * length - 1; i++) {
10 // Actual index for the original nums array (using modulo for wrap-around)
11 const currentIndex = i % length;
12
13 // Pop all elements from the stack smaller than the current element in nums
14 while (indexStack.length !== 0 && nums[indexStack[indexStack.length - 1]] < nums[currentIndex]) {
15 // Set the next greater element for the index on the top of the stack
16 result[indexStack[indexStack.length - 1]] = nums[currentIndex];
17 // Remove the index from the stack as we have found a next greater element
18 indexStack.pop();
19 }
20
21 // If we're in the first pass, add the current index to the stack
22 if (i < length) {
23 indexStack.push(currentIndex);
24 }
25 }
26 return result;
27}
28
Time and Space Complexity
Time Complexity
The time complexity of the provided code can be analyzed as follows:
- The code consists of a for loop that iterates
2n
times wheren
is the length of the input arraynums
. This is evident from the loop constructionfor i in range(n << 1)
, which is equivalent tofor i in range(2 * n)
. - Inside the loop, the
while
loop can potentially run for each element of the stack. However, considering that no element is pushed onto the stack more than twice (once for its original position and once for its virtual copied position due to the circular nature of the problem), each element is also popped only once. Therefore, in amortized analysis, thewhile
loop runsO(1)
time for each iteration of thefor
loop. - Accordingly, the overall time complexity is
O(n)
for the single pass in the doubled array, counting the amortized constant time operations inside the loop.
Thus, the time complexity is O(n)
.
Space Complexity
The space complexity can be considered in the following points:
- A new list
ans
of sizen
is created to store the results so this takesO(n)
space. - Additionally, a stack
stk
is used to store indices. In the worst case, this stack can grow to storen
indices before elements are popped. - There are no other significant contributors to space complexity.
Taking these into account, the space complexity is also O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.