This program finds the next greater element for each element in a given array. The Next Greater Element (NGE) for an element x is the first greater element to the right of x in the array. If there is no greater element, the result is -1 for that element.

Program Explanation

The problem is solved using a stack to efficiently compute the next greater element for each element in an array. The algorithm processes elements from right to left, using the stack to keep track of elements for which we haven’t found the next greater element yet.

The process is as follows:

1. Start from the last element and move leftwards.
2. For each element, pop elements from the stack until you find an element greater than the current element.
3. If such an element is found, it is the next greater element. Otherwise, the next greater element is -1.
4. Push the current element onto the stack and continue.

C Program Code

#include <stdio.h>
#include <stdlib.h>

#define MAX 100  // Define the maximum size of the array

// Stack structure
struct Stack {
    int arr[MAX];
    int top;
};

// Initialize the stack
void initStack(struct Stack *s) {
    s->top = -1;
}

// Check if stack is empty
int isEmpty(struct Stack *s) {
    return s->top == -1;
}

// Push an element onto the stack
void push(struct Stack *s, int value) {
    if (s->top == MAX - 1) {
        printf("Stack overflow\n");
        return;
    }
    s->arr[++(s->top)] = value;
}

// Pop an element from the stack
int pop(struct Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->arr[(s->top)--];
}

// Peek the top element of the stack
int peek(struct Stack *s) {
    if (isEmpty(s)) {
        return -1;
    }
    return s->arr[s->top];
}

// Function to find the next greater element for each element in the array
void findNextGreaterElements(int arr[], int n) {
    struct Stack s;
    initStack(&s);
    int nge[MAX];  // Array to store the next greater elements

    // Process elements from right to left
    for (int i = n - 1; i >= 0; i--) {
        // Pop elements from the stack that are smaller than or equal to the current element
        while (!isEmpty(&s) && peek(&s) <= arr[i]) {
            pop(&s);
        }

        // If stack is not empty, then the top element is the next greater element
        if (!isEmpty(&s)) {
            nge[i] = peek(&s);
        } else {
            // If no greater element is found, store -1
            nge[i] = -1;
        }

        // Push the current element onto the stack
        push(&s, arr[i]);
    }

    // Display the results
    printf("Element  Next Greater Element\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t\t%d\n", arr[i], nge[i]);
    }
}

// Main driver function
int main() {
    int arr[] = {11, 13, 21, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    findNextGreaterElements(arr, n);

    return 0;
}
    

Code Explanation

1. Stack Structure: The stack is implemented using a simple array with a fixed size of MAX. It has operations to push(), pop(), and peek() elements, which are used to maintain elements for which we need to find the next greater element.

2. Processing the Array: The function findNextGreaterElements() processes the array from right to left:

• For each element, smaller elements in the stack are popped, as they cannot be the next greater element.
• If the stack is non-empty after popping, the element at the top is the next greater element.
• If the stack is empty, it means there is no greater element to the right, so we store -1 for that element.

Sample Output

Array: 11 13 21 3 
Element  Next Greater Element
11       13
13       21
21       -1
3        -1
    

Conclusion

This C program demonstrates how to efficiently find the next greater element for each element in an array using a stack. By iterating from right to left and using the stack to store potential candidates for the next greater element, the program achieves an O(n) time complexity, making it highly efficient for large arrays.