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 array. Elements for which no greater element exist, consider next greater element as -1.
Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element NGE 4 --> 5 5 --> 25 2 --> 25 25 --> -1
d) For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.
Element NGE 13 --> -1 7 --> 12 6 --> 12 12 --> -1
Method 1 (Simple)
Use 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 outer loop. If a greater element is found then that element is printed as next, otherwise -1 is printed.
Thanks to Sachin for providing following code.
#include<stdio.h>
/* prints element and NGE pair for all elements of
arr[] of size n */
void printNGE(int arr[], int n)
{
int next = -1;
int i = 0;
int j = 0;
for (i=0; i<n; i++)
{
next = -1;
for (j = i+1; j<n; j++)
{
if (arr[i] < arr[j])
{
next = arr[j];
break;
}
}
printf("%d –> %d\n", arr[i], next);
}
}
int main()
{
int arr[]= {11, 13, 21, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printNGE(arr, n);
getchar();
return 0;
}
Output:
11 --> 13 13 --> 21 21 --> -1 3 --> -1
Time Complexity: O(n^2). The worst case occurs when all elements are sorted in decreasing order.
Method 2 (Using Stack)
1. Take stack A.
2. Initially the stack is empty. Traverse the array from left to right. Do for every element
a. if the stack is empty push the element in the stack
b. if the stack is non empty keep on popping elements from the stack till element popped < current element. The next greater element for every popped element would be the current element. If element popped > current element. Push popped element and then current element on the stack.
3. When the traversal is complete, if the stack is nonempty pop elements from the stack and set the values of next greater element for these popped element as -1.
eg. for array [2, 25, 20, 11, 21, 3]
stack A -> emtpy
1. push element 2 on stack A->2
2. pop 2 from the stack. Compare it with 25 since 2 < 25 set next greater element of 2 as 25.
A->25
3. pop 25 from the stack. 25 > 20 . Push 25 on the stack. Push 20 on the stack.
A->25->20
4. pop 20 from the stack. 20>11. Push 20 on the stack. Push 11 on the stack.
A->25->20->11
5. pop 11 from the stack. 11 < 21. Set next greater element of 11 as 21. Pop 20 from the stack. 20 < 21. Set next greater element of 20 as 21. Pop 25 from the stack. 25 > 21. Push 25 on stack. Push 21 on stack.
A->25->21
6. pop 21 from the stack. 21 > 3. Push 21 on stack. Push 3 on stack.
A->25->21->3
Set the value of next greater elements for all the elements present in the stack as -1.
#include<stdio.h>
#include<stdlib.h>
#define STACKSIZE 100
// stack structure
struct stack
{
int top;
int items[STACKSIZE];
};
// Stack Functions to be used by printNGE()
void push(struct stack *ps, int x)
{
if (ps->top == STACKSIZE-1)
{
printf("Error: stack overflow\n");
getchar();
exit(0);
}
else
{
ps->top += 1;
int top = ps->top;
ps->items [top] = x;
}
}
bool isEmpty(struct stack *ps)
{
return (ps->top == -1)? true : false;
}
int pop(struct stack *ps)
{
int temp;
if (ps->top == -1)
{
printf("Error: stack underflow \n");
getchar();
exit(0);
}
else
{
int top = ps->top;
temp = ps->items [top];
ps->top -= 1;
return temp;
}
}
/* prints element and NGE pair for all elements of
arr[] of size n */
void printNGE(int arr[], int n)
{
int i = 0;
struct stack s;
s.top = -1;
int element, next;
/* push the first element to stack */
push(&s, arr[0]);
// iterate for rest of the elements
for (i=1; i<n; i++)
{
next = arr[i];
if (isEmpty(&s) == false)
{
// if stack is not empty, then pop an element from stack
element = pop(&s);
/* If the popped element is smaller than next, then
a) print the pair
b) keep popping while elements are smaller and
stack is not empty */
while (element < next)
{
printf("\n %d --> %d", element, next);
if(isEmpty(&s) == true)
break;
element = pop(&s);
}
/* If element is greater than next, then push
the element back */
if (element > next)
push(&s, element);
}
/* push next to stack so that we can find
next greater for it */
push(&s, next);
}
/* After iterating over the loop, the remaining
elements in stack do not have the next greater
element, so print -1 for them */
while(isEmpty(&s) == false)
{
element = pop(&s);
next = -1;
printf("\n %d --> %d", element, next);
}
}
/* Driver program to test above functions */
int main()
{
int arr[]= {11, 13, 21, 3};
int n = sizeof(arr)/sizeof(arr[0]);
printNGE(arr, n);
getchar();
return 0;
}
Output:
11 --> 13 13 --> 21 3 --> -1 21 --> -1
Time Complexity: O(n). The worst case occurs when all elements are sorted in decreasing order. If elements are sorted in decreasing order, then every element is processed at most 4 times.
a) Initialy pushed to the stack.
b) Popped from the stack when next element is being processed.
c) Pushed back to the stack because next element is smaller.
d) Popped from the stack in step 3 of algo.