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:

1. 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.

2. Iterate Through the Array:

   • For each element in the array (let's call it temp):
   1. 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.
   2. 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.

3. 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.

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!