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 the ans 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.
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 variable n.
- Create an answer array ans of the same length as nums, 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.
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 by i % n.
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 stack nums[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.
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.
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. The ans array is returned as the final result.

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 Evaluator

Example 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 is n = 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.
Double Iteration Over The Array:
- We loop over the range of 2n, which is 6 in this case, to simulate the circular array.
Iteration Details:
- First Pass ([4, 1, 2]): We start with i = 0 (i % n = 0), and the stack is empty. We push the index 0 to the stack.
- Move to i = 1 (i % n = 1). nums[1] = 1 is not greater than nums[0] = 4, so we push 1 onto the stack.
- Move to i = 2 (i % n = 2). nums[2] = 2 is not greater than nums[1] = 1 but is also not greater than nums[0] = 4, so we push 2 onto the stack.
- Second Pass ([4, 1, 2] again):
- Now, i = 3 (i % n = 0). nums[3 % n] = nums[0] = 4 is not greater than nums[2] = 2, so nothing changes.
- Move to i = 4 (i % n = 1). nums[4 % n] = nums[1] = 1 is not greater than nums[2] = 2 or than nums[0] = 4. Nothing changes.
- Move to i = 5 (i % n = 2). nums[5 % n] = nums[2] = 2. Here, we see nums[2] = 2 is greater than nums[1] = 1 which is at the top of the stack. So, we pop 1 from the stack and update ans[1] to 2. Now stk = [0, 2].
Finish the Stack Processing:
- Since we reached the end of our second pass and there is no greater element for indices 0 and 2, we leave their corresponding values in ans as -1.
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 is 2, and for the third element (2) there is no next greater number considering the circular nature of the array. We return ans as the result.

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 where n is the length of the input array nums. This is evident from the loop construction for i in range(n << 1), which is equivalent to for 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, the while loop runs O(1) time for each iteration of the for 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 size n is created to store the results so this takes O(n) space.
Additionally, a stack stk is used to store indices. In the worst case, this stack can grow to store n 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know