Next Greater Element II
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through the array for each element to find its next greater number. Due to the circular nature of the array, the search for a greater number wraps around from the end to the beginning.
Algorithm
-
- Initialize a result array
resof the same size asnumsand fill it with-1.
- Initialize a result array
-
- Iterate through the input array
numswith an indexifrom0ton-1.
- Iterate through the input array
-
- For each element
nums[i], start a second loop to search for its next greater element.
- For each element
-
- The search index
jwill traverse fromi+1up toi+n-1. We use the modulo operator(i+k) % n(wherekgoes from 1 ton-1) to handle the circular nature of the array.
- The search index
-
- In the inner loop, if we find an element
nums[j]such thatnums[j] > nums[i], we setres[i] = nums[j]and break the inner loop.
- In the inner loop, if we find an element
-
- If the inner loop completes without finding a greater element,
res[i]remains-1.
- If the inner loop completes without finding a greater element,
-
- After iterating through all elements, return the
resarray.
- After iterating through all elements, return the
Walkthrough
The simplest way to solve this problem is by using nested loops. The outer loop iterates through each element of the array, say nums[i], for which we want to find the next greater element.
The inner loop then searches for the first element nums[j] that is greater than nums[i]. The search starts from the element right after i and continues circularly until we have checked all other n-1 elements.
To handle the circularity, we can use the modulo operator (%). The index j for the inner loop will be (i + 1) % n, (i + 2) % n, and so on, for n-1 steps.
If a greater element is found, we store it in our result array and break the inner loop to move to the next element in the outer loop.
If the inner loop completes without finding any greater element, it means no such element exists. In this case, we assign -1 to the result for nums[i]. We can pre-fill the result array with -1s to handle this case automatically.
import java.util.Arrays; class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] result = new int[n]; Arrays.fill(result, -1); for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { int nextIndex = (i + j) % n; if (nums[nextIndex] > nums[i]) { result[i] = nums[nextIndex]; break; // Found the first greater element, move to the next i } } } return result; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. For each element, we may have to scan the entire array in the worst case.
Space
O(n) to store the result array. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Very simple and straightforward to understand.
Easy to implement without any complex data structures.
Cons
Highly inefficient for large arrays, likely to result in a 'Time Limit Exceeded' error on most coding platforms.
Solutions
Solution
class Solution {public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); Deque<Integer> stk = new ArrayDeque<>(); for (int i = 0; i < (n << 1); ++i) { while (!stk.isEmpty() && nums[stk.peek()] < nums[i % n]) { ans[stk.pop()] = nums[i % n]; } stk.push(i % n); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.