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]
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
- If A[j] > A[i]:
- 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 < 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);
}
}</pre>
<!-- /wp:enlighter/codeblock -->
Practice Question
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.
