Easy and simple solution with analogy || understand the concept
Problem DescriptionGiven a circular array nums (the next element after the last one is the first element), find the next greater element for each element. The n
## Problem Description
Given a circular array `nums` (the next element after the last one is the first element), find the next greater element for each element. The next greater element for a number `x` is the first number to its right in the circular array that is greater than `x`. If no such element exists, return -1. Return an array of these results.

---

## Intuition
We use a stack to find the next greater element for each number in a circular array by simulating two passes over the array and tracking larger elements.

---

## Analogy
Imagine `nums` as a circular row of streetlights of different heights around a park. For each streetlight, we want to find the next taller one as we walk around the circle (even wrapping around to the start). The stack acts like a spotlight, keeping only the taller lights in view and discarding shorter ones as we go.

---

## Approach
1. **Simulate Circular Behavior:**
   - Since the array is circular, process it twice (2 * n elements) using modulo (`i % n`) to wrap around.
   - Iterate from right to left (2n-1 to 0) to mimic the circular nature.

2. **Use a Stack:**
   - For each element:
     - Pop all smaller or equal elements from the stack (they can’t be the "next greater").
     - If the stack has an element left and we’re in the first pass (i < n), it’s the next greater element.
     - Push the current element onto the stack.

3. **Build Result:**
   - Initialize a result vector with -1 (default if no greater element exists).
   - Update the result only during the first pass (i < n) with the stack’s top element.

---

## Code
```cpp []
class Solution {
public:
  vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    
    stack<int> st;
    vector<int> result(n, -1);

    for(int i=2*n-1; i>=0; i--){
      while(!st.empty() && 
      st.top() <= nums[i%n]) st.pop();
      if(i < n && !st.empty()) result[i] = st.top();
      st.push(nums[i%n]);
    }

    return result;
  }
};
```

## Dry Run
Let’s take `nums = [1, 2, 1]`.

| Index (i) | Current Element (nums[i % n]) | Stack (Top to Bottom) | Result Updates       | Action                                      |
|-----------|-------------------------------|-----------------------|----------------------|---------------------------------------------|
| 5         | 1                            | [1]                  | -                    | Stack empty → push 1                       |
| 4         | 2                            | [2]                  | -                    | Pop 1 (1 ≤ 2), push 2                     |
| 3         | 1                            | [2, 1]              | -                    | 2 > 1, no pop, push 1                     |
| 2         | 1                            | [2, 1]              | [?, ?, 2]           | Pop 1 (1 ≤ 1), result[2] = 2, push 1      |
| 1         | 2                            | [2]                  | [?, 2, 2]           | Pop 1 (1 ≤ 2), result[1] = 2, push 2      |
| 0         | 1                            | [2, 1]              | [-1, 2, 2]          | 2 > 1, no pop, result[0] = -1, push 1     |

**Final Result:** `[-1, 2, 2]`

---

## Time and Space Complexity Analysis
- **Time Complexity: O(n)**
  - We process 2n elements, but each element is pushed and popped from the stack at most once → O(n).
- **Space Complexity: O(n)**
  - Stack: At most stores n elements → O(n).
  - Result vector: O(n) for output.

---

![leetcode.jpeg](https://assets.leetcode.com/users/images/985e65fc-4a53-4dba-8410-d407911a4b51_1742048433.3010871.jpeg)

['Array', 'Stack', 'Monotonic Stack', 'C++']