Next Greater Element

Next Greater Element

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:

  1. The least greater element of 8 on its right is 9
  2. The least greater element of 5 on its right is 9.
  3. The least greater element of 2 on its right is 3.
  4. The least greater element of 3 on its right is 9.
  5. 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}
initial array
  • Push the first element into the stack.
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.
Traverse the array
  • 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.
Continue loop from 2 to N - 1
  • Continuing the loop from i = 3. Since, the element 3 < 21, push it into the stack.
Continuing the loop from i = 3
  • 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 = 4
  • Continuing the loop from i = 5. Since, the element 2 < 4, push it into the stack.
Continuing the loop from i = 5
  • 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.
whole array has been traversed

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.

Previous Post
LRU Cache

LRU Cache

Next Post
Dining Philosophers Problem

Dining Philosophers Problem

Total
0
Share