C Program To Find 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 the array. Elements for which no greater element exist, consider the next greater element as -1.
Examples:
- For an array, the rightmost element always has the next greater element as -1.
- For an array that is sorted in decreasing order, all elements have the next greater element as -1.
- 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 the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.
Below is the implementation of the above approach:
C
// 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; } |
11 -- 13 13 -- 21 21 -- -1 3 -- -1
Time Complexity: O(N2)
Auxiliary Space: O(1)
Method 2 (Using Stack)
- Push the first element to stack.
- Pick rest of the elements one by one and follow the following steps in loop.
- Mark the current element as next.
- If stack is not empty, compare top element of stack with next.
- If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
- Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
- Finally, push the next in the stack.
- After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.
Below image is a dry run of the above approach:
Below is the implementation of the above approach:
C
// A Stack based C program to find next // greater element for all array elements. #include <stdbool.h> #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 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 code */ int main() { int arr[] = { 11, 13, 21, 3 }; int n = sizeof (arr) / sizeof (arr[0]); printNGE(arr, n); getchar (); return 0; } |
11 --> 13 13 --> 21 3 --> -1 21 --> -1
Time Complexity: O(N)
Auxiliary Space: 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.
- Initially pushed to the stack.
- Popped from the stack when next element is being processed.
- Pushed back to the stack because the next element is smaller.
- Popped from the stack in step 3 of the algorithm.
Please see for an optimized solution for printing in same order.
Please refer complete article on Next Greater Element for more details!