Next Greater Element

Problem Statement: Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider the next greater element as -1.

Example:

arr = [1,2,3,4,3]

Output: [2,3,4,-1,-1]

This is one of the popular interview questions in many product-based companies. So our solution should be in the proper manner, starting with brute force and gradually moving to the optimal one. let's start with brute force

Approach 1: Brute force

This is the simulation process by using two loops: The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed. Time complexity is O(n²) so obivously interviewer will ask you to optimise it

Approach 2: Efficient: Using Stack

Stack is an ideal data structure for such problems. It stores the elements or its index for whom the next greater element is not yet found and pops them as soon as it meets the next greater element.

Stack can be used to store either element values or their indices. Since we need to return an array with the next greater element at corresponding indices, the order is important for us and hence we shall store indices.

Alogrithm:

1. Declare an array ans[] with size n and initialize it with a default value of -1.

2. Declare a stack S and push value '0' in it representing the index of the first element.

3. Start traversing the array from the second element and at each iteration

4. Initiate a while loop that keeps on popping elements as long as the top of the stack is smaller than the current element. The Next Greater Element for all these popped elements will be the current element.

5. At the end of while loop, push the index of the current element in the stack

All elements that remain in the stack, in the end, have the next greater element as -1. Since the default value in ans[] was -1, the corresponding indices of these elements are already filled with -1. Return ans[] array

#include<bits/stdc++.h>

using namespace std;
class Solution {
  public:
    vector < int > nextGreaterElements(vector < int > & nums) {
      int n = nums.size();
      vector < int > nge(n, -1);
      stack < int > st;
      for (int i = 2 * n - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= nums[i % n]) {
          st.pop();
        }

        if (i < n) {
          if (!st.empty()) nge[i] = st.top();
        }
        st.push(nums[i % n]);
      }
      return nge;
    }
};
int main() {
  Solution obj;
  vector < int > v {5,7,1,2,6,0};
  vector < int > res = obj.nextGreaterElements(v);
  cout << "The next greater elements are" << endl;
  for (int i = 0; i < res.size(); i++) {
    cout << res[i] << " ";
  }
}

def findNextGreaterElements(arr):
 
    # base case
    if not arr: return
 
    result = [-1] * len(arr)
 
    # create an empty stack
    s = []
 
    # do for each element
    for i in range(len(arr)):
 
        # loop till we have a greater element on top or stack becomes empty.
 
        # Keep popping elements from the stack smaller than the current
        # element, and set their next greater element to the current element
        while s and arr[s[-1]] < arr[i]:
            result[s[-1]] = arr[i]
            s.pop()
 
        # push current "index" into the stack
        s.append(i)
 
    return result
 
 
if __name__ == '__main__':
 
    input = [1,2,3,4,3]
    print(findNextGreaterElements(input))

Time Complexity: each element is visited at most twice, first while pushing them onto the stack and second while popping them from the stack. Initializing ans[] array with -1 + Traversal of the array and Stack. O(n) + O(2*n) = O(n)

Auxiliary Space: O(n), Since we are using stack for storing

💡 Follow up: Try to solve next smaller element for every element