Next Greater Element

Table Of Contents

show

Problem Statement
Brute Force Approach

C++ Code
Java Code
Python Code

Efficient Approach: Using Stack

C++ Code For Stack Method
Java Code For Stack Method
Python Code For Stack Method

Practice Question
FAQs

Problem Statement

Given an array A[], find the next greater elementG[i] for every element A[i] in the array.
The Next greater Element for an element A[i] is the first greater element on the right side of A[i] in the array. Elements for which no greater element exists, consider the next greater element as -1.

More formally,

G[i] for an element A[i] = an element A[j] such that j is minimum
possible AND j > i AND A[j] > A[i]

Confused about your next job?

In 4 simple steps you can find your personalised career roadmap in Software development for FREE

Expand in New Tab

Examples:

Input: A[] = [8, 5, 2, 3, 9]
Output: [9, 9, 3, 9, -1]
Explanation:

The least greater element of 8 on its right is 9
The least greater element of 5 on its right is 9.
The least greater element of 2 on its right is 3.
The least greater element of 3 on its right is 9.
No element is greater than 9 on its right, hence -1.

Input: A[] = [18, 25, 2, 13, 29]
Output: [25, 29, 13, 29, -1]

Brute Force Approach

A simple approach to solving the problem is to run two nested loops and for each element A[i] find the first element to its right strictly greater than it.

Algorithm

Iterate loop i from 1 till N.
Initialise a variable next_greater = -1.
Iterate a loop j from i + 1 till N and perform the following:
- If A[j] > A[i]:
  - next_greater = A[j] and break.
- Else, continue
Print the value next_greater obtained.

C++ Code

void printNGE(int arr[], int n) {
  int next, i, j;
  for (i = 0; i < n; i++) {
    next = -1;
    for (j = i + 1; j < n; j++) {
      if (arr[i] < arr[j]) {
        next = arr[j];
        break;
      }
    }
    cout << arr[i] << " -- " <<
      next << endl;
  }
}

Java Code

 static void printNGE(int arr[], int n) {
  int next, i, j;
  for (i = 0; i < n; i++) {
    next = -1;
    for (j = i + 1; j < n; j++) {
      if (arr[i] < arr[j]) {
        next = arr[j];
        break;
      }
    }
    System.out.println(arr[i] + " -- " + next);
  }
}

Python Code

def printNGE(arr):
 
    for i in range(0, len(arr), 1):
 
        next = -1
        for j in range(i + 1, len(arr), 1):
            if arr[i] < arr[j]:
                next = arr[j]
                break
 
        print(str(arr[i]) + " -- " + str(next))

Efficient Approach: Using Stack

The idea is to use a stack to solve this problem. Push the first element of the array into the stack. Now iterate through all the elements from 1 to N – 1 and if the value of the current index is smaller than the value at the top of the stack, push it into the stack. Similarly, if the value of the current index is greater than the value at the top of the stack, pop all remaining elements, and the next greater element is the popped elements.

Dry Run of the above approach

Let the initial array be Arr[] = {11, 13, 21, 3, 4, 2}

Push the first element into the stack.

Traverse the array from i = 1 till i = N – 1. Since, 13 > 11, pop out 11 from the stack and set 13 as the next greater element of 11.

Similarly, repeat the above step again. Continue loop from 2 to N – 1. Since, 21 > 13, pop out 13 from the stack and set 21 as the next greater element of 13.

Continuing the loop from i = 3. Since, the element 3 < 21, push it into the stack.

Continuing the loop from i = 4. Since, the 4 > 3, pop 3 and set next greater element of 3 as 4.

Continuing the loop from i = 5. Since, the element 2 < 4, push it into the stack.

Now, since the whole array has been traversed, still we are left with elements in the stack. This means, for all these elements, there doesn’t exist any greater element to its right. Hence, we mark them as -1.

Algorithm

Initialise a stack st.
Push the first element of the array into the stack.
Iterate from i = 1 till i = N – 1 and for each i, check whether the current element:
- A[i] > st.top(), keep popping elements from the stack, until an element greater than A[i] appears in the stack. The current element A[i] is the next greater element for each of the popped elements.
- A[i] < st.top(), push it into the stack.
Continue traversing till the end of the array.
At last, pop out the remaining elements of the stack and print -1, since no next greater element exists for them.

C++ Code For Stack Method

void printNGE(int arr[], int n) {
  stack < int > s;
  s.push(arr[0]);
 
  for (int i = 1; i < n; i++) {
 
    if (s.empty()) {
      s.push(arr[i]);
      continue;
    }
    while (s.empty() == false &&
      s.top() < arr[i]) {
      cout << s.top() <<
        " --> " << arr[i] << endl;
      s.pop();
    }
    s.push(arr[i]);
  }
  while (s.empty() == false) {
    cout << s.top() << " --> " << -1 << endl;
    s.pop();
  }
}

Java Code For Stack Method

static class stack {
  int top;
  int items[] = new int[100];
  void push(int x) {
    if (top == 99) {
      System.out.println("Stack full");
    } else {
      items[++top] = x;
    }
  }
 
  int pop() {
    if (top == -1) {
      System.out.println("Underflow error");
      return -1;
    } else {
      int element = items[top];
      top--;
      return element;
    }
  }
 
  boolean isEmpty() {
    return (top == -1) ? true : false;
  }
}
static void printNGE(int arr[], int n) {
  int i = 0;
  stack s = new stack();
  s.top = -1;
  int element, next;
  s.push(arr[0]);
 
  for (i = 1; i < n; i++) {
    next = arr[i];
 
    if (s.isEmpty() == false) {
      element = s.pop();
 
      while (element < next) {
        System.out.println(element + " --> " +
          next);
        if (s.isEmpty() == true)
          break;
        element = s.pop();
      }
 
      if (element > next)
        s.push(element);
    }
 
    s.push(next);
  }
  while (s.isEmpty() == false) {
    element = s.pop();
    next = -1;
    System.out.println(element + " -- " + next);
  }
}

Python Code For Stack Method

<!-- wp:enlighter/codeblock {"language":"java"} -->
<pre class="EnlighterJSRAW" data-enlighter-language="java" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">static class stack {
  int top;
  int items[] = new int[100];
  void push(int x) {
    if (top == 99) {
      System.out.println("Stack full");
    } else {
      items[++top] = x;
    }
  }
 
  int pop() {
    if (top == -1) {
      System.out.println("Underflow error");
      return -1;
    } else {
      int element = items[top];
      top--;
      return element;
    }
  }
 
  boolean isEmpty() {
    return (top == -1) ? true : false;
  }
}
static void printNGE(int arr[], int n) {
  int i = 0;
  stack s = new stack();
  s.top = -1;
  int element, next;
  s.push(arr[0]);
 
  for (i = 1; i &lt; n; i++) {
    next = arr[i];
 
    if (s.isEmpty() == false) {
      element = s.pop();
 
      while (element &lt; next) {
        System.out.println(element + " --> " +
          next);
        if (s.isEmpty() == true)
          break;
        element = s.pop();
      }
 
      if (element > next)
        s.push(element);
    }
 
    s.push(next);
  }
  while (s.isEmpty() == false) {
    element = s.pop();
    next = -1;
    System.out.println(element + " -- " + next);
  }
}</pre>
<!-- /wp:enlighter/codeblock -->

Practice Question

Next Greater Problem

FAQs

What other data structure can be used other than stack?
A queue can also be used to find the Next Greater Element.

What is the worst case and best case scenario in the brute force approach?
The best case is when the array is sorted in increasing order. This leads to an O(N) approach.
The worst case is when the array is sorted in decreasing order.