### Optimized Solution to "Next Greater Element"

In competitive programming, the "Next Greater Element" problem is a common one that requires efficient solutions, especially when time complexity becomes critical in larger inputs. The problem asks us to find the next greater element for every element in an array.

Although this problem has been solved in various ways online, I wanted to share my version that utilizes a `deque`

(double-ended queue) to efficiently track the next greater elements while making use of vectors and indexes for clarity. This makes it easy to follow and understand, especially for beginners.

### Problem Statement

Given an array of `n`

integers, for each element, find the next greater element. The next greater element of an element `x`

in the array is the first greater element to the right of `x`

. If there is no greater element, return `-1`

.

### Approach

To efficiently find the next greater element for each element in the array, we will use a **monotonic deque**. This approach helps maintain the order of elements while allowing quick access to the next greater element. Here’s a step-by-step breakdown:

**Initialization**:- Read the input size
`n`

and initialize a vector`ans`

of size`n`

filled with`-1`

to store the results. This`-1`

will signify that no greater element exists for that index initially. - Create a deque
`dq`

to store pairs of elements and their indices as we process the array.

- Read the input size
**Iterate Through the Array**:- For each element in the array (let's call it
`temp`

):

**Check and Update the Deque**:- While the deque is not empty and the element at the back of the deque (i.e.,
`dq.back().first`

) is less than`temp`

, it means`temp`

is the next greater element for the indices stored in the deque. - Pop elements from the back of the deque, and for each popped element, update the
`ans`

vector with`temp`

at the index of the popped element. This effectively tells us that`temp`

is the next greater element for those indices.

- While the deque is not empty and the element at the back of the deque (i.e.,
**Add the Current Element**:- After updating the deque, push the current element along with its index into the deque. This maintains the order and ensures that we can continue to check for next greater elements as we move forward.

- For each element in the array (let's call it
**Output the Results**:- After processing all elements, print the contents of the
`ans`

vector, which now contains the next greater elements for each index in the original array.

- After processing all elements, print the contents of the

### Code Implementation

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> ans(n, -1); // Initialize answer vector with -1
deque<pair<int, int>> dq; // Deque to store pairs of (element, index)
for (int i = 0; i < n; i++){
int temp;
cin >> temp;
// Remove elements from deque that are smaller than the current element
while (!dq.empty() && dq.back().first < temp){
ans[dq.back().second] = temp; // Set the next greater element
dq.pop_back();
}
dq.push_back({temp, i}); // Add the current element with its index
}
// Output the results
for (auto i : ans)
cout << i << " ";
}
```

### Explanation of Key Points

**Deque (Double-ended Queue):**

A deque allows us to efficiently add and remove elements from both ends. In this case, we use it to keep track of the elements and their indices, while ensuring the elements in the deque are in decreasing order (from front to back).**Vector**`ans`

:

This stores the result for each element in the array. If no next greater element is found, the value remains`-1`

.**Time Complexity**: The overall time complexity is**O(n)**since each element is pushed and popped from the deque at most once.**Space Complexity**: The space complexity is**O(n)**for storing the results and the deque.

### Why This Version?

Though this algorithm has been seen in various forms across the internet, I've chosen to use a `vector`

and maintain index clarity for those who are just getting started. By directly associating indices with elements in the deque, we ensure that the solution is easy to debug and follow.

### Conclusion

I hope this version of the "Next Greater Element" problem using a deque and vectors helps you understand this pattern better. Feel free to use and adapt this solution in your future competitive programming challenges!

Let me know if you have any suggestions or improvements!