- Write a program to find next larger element of array
- Algorithm to find next greater element using stack data structure and in O(n) time complexity.

Given an integer array of size N. For every element E of input array, we have to **find the next greater element** of E. If array[j] is the next greater element of array[i] then (j > i) and array[j] must be the first larger element in right side of array[i]. If no **next greater element** exist for an element then set next greater element as -1.

Input Array : [7 4 10 8 1 14] OutputArray : [10 10 14 14 14 -1]

Let inputArray be an integer array of size N.

**By linearly searching next greater element for every array element : O(n**

^{2})- In this algorithm we will use two loops. outer loop will fix one array element(K).
- Inner loop will search for the first greater element by traversing in right side of K.

^{2})

## C program to find next greater element of array

#include<stdio.h> /* This program prints the next bigger element for every element of array */ void printNextBigElement(int *array, int size) { int nextBig, i, j; /* For every element of array search for first element bigget than current element */ for(i = 0; i < size; i++) { for (j = i+1, nextBig = -1; j < size; j++) { if (array[i] < array[j]) { /* Found Next Bigger Element */ nextBig = array[j]; break; } } printf("%d ", nextBig); } } int main() { int i, array[6]= {7, 4, 10, 8, 1, 14}; printf("Original Array\n"); for(i = 0; i < 6; i++){ printf("%d ", array[i]); } printf("\nNext Bigger Element Array\n"); printNextBigElement(array, 6); return 0; }Output

Original Array 7 4 10 8 1 14 Next Bigger Element Array 10 10 14 14 14 -1

**By using stack : O(n)**

**Algorithm to find next greater element using stack**

The core logic behind this algorithm is that, we first push elements in stack and then remove it from stack once we found a greater element.

- Traverse input array from left to right.
- Push first element of array in stack.
- For any element inputArray[i], compare it with top element of stack(top).
- If inputArray[i] <= top, then push inputArray[i] in stack.
- If inputArray[i] > top, then inputArray[i] is next greater element of top. Keep on removing top elements of stack until inputArray[i] > top.

- After complete traversal of inputArray, stack is non-empty then no next greater element exists for those elements inside stack.

## C program to find next larger element of array using stack

#include <stdio.h> #include <string.h> #define MAXSIZE 100 #define TRUE 1 #define FALSE 0 // Structure defining Stack data structure struct Stack { int top; int array[MAXSIZE]; } st; /* Initializes the top index to -1 */ void initialize() { st.top = -1; } /* Checks if Stack is Full or not */ int isFull() { if(st.top >= MAXSIZE-1) return TRUE; else return FALSE; } /* Checks if Stack is Empty or not */ int isEmpty() { if(st.top == -1) return TRUE; else return FALSE; } /* Adds an element to stack and then increment top index */ void push(int num) { if (isFull()) printf("Stack is Full...\n"); else { st.array[st.top + 1] = num; st.top++; } } /* Removes top element from stack and decrement top index */ int pop() { if (isEmpty()) printf("Stack is Empty...\n"); else { st.top = st.top - 1; return st.array[st.top+1]; } } /* This program prints the next bigger element for every element of array */ void printNextBigElement(int *array, int size) { initialize(); int top, current, i; /* Initialize stack with first element of array */ push(array[0]); /* Traverse whole array from left to right */ for(i = 1; i < size; i++){ current = array[i]; if (!isEmpty()) { /* Pop Top element of Stack */ top = pop(); /* If top element is smaller than current, then current is NBE of top. COntinue poping elements till top is smaller than current */ while(top < current) { printf("%d %d\n", top, current); if(isEmpty()) break; top = pop(); } /* If top is greater than current than push top again */ if (top >= current) push(top); } /* push curret to stack */ push(current); } /* Afer complete traversal, the left over elements on stack don't have any Next Bigger Element */ while (!isEmpty()){ top = pop(); printf("%d %d\n", top, -1); } } int main() { int i, array[6]= {7, 4, 10, 8, 1, 14}; printf("Original Array\n"); for(i = 0; i < 6; i++){ printf("%d ", array[i]); } printf("\nNext Bigger Element Mapping\n"); printNextBigElement(array, 6); return 0; }Output

Original Array 7 4 10 8 1 14 Next Bigger Element Mapping 4 10 7 10 1 14 8 14 10 14 14 -1