# Next Greater Element II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/next-greater-element-ii)
Canonical: https://scaleengineer.com/dsa/problems/next-greater-element-ii
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Zeta](https://scaleengineer.com/companies/zeta)
---
## Problem
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
## Brute Force Iteration
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.
**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).
**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.
### Explanation
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 `-1`s to handle this case automatically.
```java
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;
    }
}
```
### Algorithm
- 1. Initialize a result array `res` of the same size as `nums` and fill it with `-1`.
- 2. Iterate through the input array `nums` with an index `i` from `0` to `n-1`.
- 3. For each element `nums[i]`, start a second loop to search for its next greater element.
- 4. 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.
- 5. 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.
- 6. If the inner loop completes without finding a greater element, `res[i]` remains `-1`.
- 7. After iterating through all elements, return the `res` array.

## Optimal Approach using Monotonic Stack
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.
**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.
**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.
### Explanation
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).
```java
import java.util.Arrays;
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        
        // Stack stores indices of the numbers
        Deque<Integer> stack = new ArrayDeque<>(); 
        
        // Iterate twice through the array to handle circularity
        for (int i = 0; i < 2 * n; i++) {
            int num = nums[i % n];
            // While stack is not empty and the current number is greater than
            // the number at the index stored at the top of the stack
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                // The current number is the next greater element for the index at the top
                result[stack.pop()] = num;
            }
            // Push the current index onto the stack for the first pass
            if (i < n) {
                stack.push(i);
            }
        }
        
        return result;
    }
}
```
### Algorithm
- 1. Get the length of the array, `n`.
- 2. Create a result array `res` of size `n` and initialize all its elements to `-1`.
- 3. Initialize an empty stack (e.g., a `Deque`) to store indices.
- 4. Loop from `i = 0` to `2*n - 1`. This simulates iterating through the array twice.
- 5. In each iteration, get the current number `num = nums[i % n]`.
- 6. 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`.
- 7. If `i < n`, push the current index `i` onto the stack. This ensures each index is pushed only once.
- 8. After the loop finishes, the `res` array contains the next greater element for each index. Return `res`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[]} */ var nextGreaterElements =
  function (nums) {
    const n = nums.length;
    let stk = [];
    let ans = new Array(n).fill(-1);
    for (let i = 0; i < n << 1; i++) {
      const j = i % n;
      while (stk.length && nums[stk[stk.length - 1]] < nums[j]) {
        ans[stk.pop()] = nums[j];
      }
      stk.push(j);
    }
    return ans;
  };

```

### Python

```python
class Solution:
    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

```

### CPP

```cpp
class Solution {
public:
  vector<int> nextGreaterElements(vector<int> &nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    stack<int> stk;
    for (int i = 0; i < (n << 1); ++i) {
      while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
        ans[stk.top()] = nums[i % n];
        stk.pop();
      }
      stk.push(i % n);
    }
    return ans;
  }
};

```