Program to Find Next Greater Element for Every Array Element

  • 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(n2)
  • 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.
Time Complexity : O(n2)

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
Posted by
Labels: ,