Next Greater Element II

Med

#0490Time: 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).2 companies

Data structures

Array Stack Monotonic Stack

Companies

Intuit Zeta

Prompt

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 <= 10⁴
-10⁹ <= nums[i] <= 10⁹

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

1. Initialize a result array res of the same size as nums and fill it with -1.
1. Iterate through the input array nums with an index i from 0 to n-1.
1. For each element nums[i], start a second loop to search for its next greater element.
1. The search index j will traverse from i+1 up to i+n-1. We use the modulo operator (i+k) % n (where k goes from 1 to n-1) to handle the circular nature of the array.
1. In the inner loop, if we find an element nums[j] such that nums[j] > nums[i], we set res[i] = nums[j] and break the inner loop.
1. If the inner loop completes without finding a greater element, res[i] remains -1.
1. After iterating through all elements, return the res array.

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.

1import java.util.Arrays;2 3class Solution {4    public int[] nextGreaterElements(int[] nums) {5        int n = nums.length;6        int[] result = new int[n];7        Arrays.fill(result, -1);8 9        for (int i = 0; i < n; i++) {10            for (int j = 1; j < n; j++) {11                int nextIndex = (i + j) % n;12                if (nums[nextIndex] > nums[i]) {13                    result[i] = nums[nextIndex];14                    break; // Found the first greater element, move to the next i15                }16            }17        }18        return result;19    }20}

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.

A more efficient solution uses a monotonic stack. By iterating through the array twice (conceptually), we can find the next greater element for each number in a single pass. The stack helps keep track of elements for which we are still seeking a next greater element.

Algorithm

1. Get the length of the array, n.
1. Create a result array res of size n and initialize all its elements to -1.
1. Initialize an empty stack (e.g., a Deque) to store indices.
1. Loop from i = 0 to 2*n - 1. This simulates iterating through the array twice.
1. In each iteration, get the current number num = nums[i % n].
1. While the stack is not empty and the element corresponding to the index at the top of the stack (nums[stack.peek()]) is less than num:
- a. This means num is the next greater element for the index at the top of the stack.
- b. Pop the index from the stack and set res[popped_index] = num.
1. If i < n, push the current index i onto the stack. This ensures each index is pushed only once.
1. After the loop finishes, the res array contains the next greater element for each index. Return res.

Walkthrough

This approach leverages a monotonic stack (specifically, a decreasing stack) to find the next greater element in linear time. A monotonic stack maintains its elements in a specific order (either increasing or decreasing). To handle the circularity of the array, we can imagine the array is concatenated with itself (e.g., [1,2,1] becomes [1,2,1,1,2,1]). A simpler way to implement this is to iterate through 2*n elements, using the modulo operator i % n to access the array elements. This simulates a second pass over the array, which is necessary to find circular next greater elements. We iterate from i = 0 to 2*n - 1. We use a stack to store the indices of elements. In each iteration, we consider the current number nums[i % n]. We check the top of the stack. If the stack is not empty and the number corresponding to the index at the top of the stack is smaller than the current number, it means we've found the next greater element for the index on the stack. We pop the index, update its result in the result array, and repeat until the stack is empty or the condition is false. After checking, we push the current index i onto the stack, but only during the first pass (i < n) to ensure each index is only considered once as a potential candidate needing a greater element. Elements whose indices remain in the stack after the loop have no next greater element, so their result remains -1 (our initial value).

1import java.util.Arrays;2import java.util.Deque;3import java.util.ArrayDeque;4 5class Solution {6    public int[] nextGreaterElements(int[] nums) {7        int n = nums.length;8        int[] result = new int[n];9        Arrays.fill(result, -1);10        11        // Stack stores indices of the numbers12        Deque<Integer> stack = new ArrayDeque<>(); 13        14        // Iterate twice through the array to handle circularity15        for (int i = 0; i < 2 * n; i++) {16            int num = nums[i % n];17            // While stack is not empty and the current number is greater than18            // the number at the index stored at the top of the stack19            while (!stack.isEmpty() && nums[stack.peek()] < num) {20                // The current number is the next greater element for the index at the top21                result[stack.pop()] = num;22            }23            // Push the current index onto the stack for the first pass24            if (i < n) {25                stack.push(i);26            }27        }28        29        return result;30    }31}

Complexity

Time

O(n). We iterate `2*n` times. Each index is pushed onto the stack once and popped once. Therefore, the total time complexity is linear with respect to the number of elements.

Space

O(n). In the worst-case scenario (a strictly decreasing array), the stack can hold up to `n` indices. The result array also requires O(n) space.

Trade-offs

Pros

Optimal time complexity of O(n).
Efficiently handles the circular nature of the array with a single conceptual pass.

Cons

Requires extra space for the stack.
The logic involving a double-length loop and a stack can be less intuitive than the brute-force method.

Solutions

Solution

1class Solution {2public3  int[] nextGreaterElements(int[] nums) {4    int n = nums.length;5    int[] ans = new int[n];6    Arrays.fill(ans, -1);7    Deque<Integer> stk = new ArrayDeque<>();8    for (int i = 0; i < (n << 1); ++i) {9      while (!stk.isEmpty() && nums[stk.peek()] < nums[i % n]) {10        ans[stk.pop()] = nums[i % n];11      }12      stk.push(i % n);13    }14    return ans;15  }16}

1/** * @param {number[]} nums * @return {number[]} */ var nextGreaterElements =2  function (nums) {3    const n = nums.length;4    let stk = [];5    let ans = new Array(n).fill(-1);6    for (let i = 0; i < n << 1; i++) {7      const j = i % n;8      while (stk.length && nums[stk[stk.length - 1]] < nums[j]) {9        ans[stk.pop()] = nums[j];10      }11      stk.push(j);12    }13    return ans;14  };

1class Solution:2    def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) ans = [- 1] * n stk = [] for i in range(n << 1): while stk and nums[stk[- 1]] < nums[i % n]: ans[stk . pop()] = nums[i % n] stk . append(i % n) return ans

1class Solution {2public:3  vector<int> nextGreaterElements(vector<int> &nums) {4    int n = nums.size();5    vector<int> ans(n, -1);6    stack<int> stk;7    for (int i = 0; i < (n << 1); ++i) {8      while (!stk.empty() && nums[stk.top()] < nums[i % n]) {9        ans[stk.top()] = nums[i % n];10        stk.pop();11      }12      stk.push(i % n);13    }14    return ans;15  }16};

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.

← Previous

Previous problem

Next problem