Next Greater Element
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.
Method 1 (Simple)
// Simple C program to print next greater elements
// in a given array
#include<stdio.h>
/* prints element and NGE pair for all elements of
arr[] of size n */
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;
}
}
printf("%d -- %dn", arr[i], next);
}
}
int main()
{
int arr[]=
{11, 13, 21, 3};
int n =
sizeof(arr)/sizeof(arr[0]);
printNGE(arr,
n);
return 0;
}
Output:
11 -- 13
13 -- 21
21 -- -1
3 -- -1
Method 2 (Using Stack)
// A Stack based C program to find next greater element
// for all array elements.
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.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 overflown");
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
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
Next Greater Element
Reviewed by Unknown
on
August 26, 2018
Rating:
Reviewed by Unknown
on
August 26, 2018
Rating:
No comments:
If you have any doubt or query ,comment below: