Next Greater Element Using Stack in DSA C

Mental Model

We want to find the next bigger number for each number in a list by looking ahead efficiently using a stack.

Analogy: Imagine standing in a line of people with different heights. For each person, you want to find the next taller person standing to their right without checking everyone again and again.

Array: [4] [5] [2] [25] [7] [8]
Stack: empty
Goal: For each element, find next greater element to the right

Dry Run Walkthrough

Input: array: [4, 5, 2, 25, 7, 8]

Goal: Find the next greater element for each number in the array

Step 1: Push 4 onto stack

Stack: [4]
Next Greater Elements: [-, -, -, -, -, -]

Why: Start with first element, no next greater found yet

Step 2: 5 is greater than top of stack (4), pop 4 and set its next greater to 5; push 5

Stack: [5]
Next Greater Elements: [5, -, -, -, -, -]

Why: 5 is next greater for 4, update and continue

Step 3: 2 is not greater than top of stack (5), push 2

Stack: [5, 2]
Next Greater Elements: [5, -, -, -, -, -]

Why: 2 might find next greater later, keep it on stack

Step 4: 25 is greater than top of stack (2), pop 2 and set next greater to 25; also greater than 5, pop 5 and set next greater to 25; push 25

Stack: [25]
Next Greater Elements: [5, 25, 25, -, -, -]

Why: 25 is next greater for 2 and 5, update both

Step 5: 7 is not greater than top of stack (25), push 7

Stack: [25, 7]
Next Greater Elements: [5, 25, 25, -, -, -]

Why: 7 might find next greater later

Step 6: 8 is greater than top of stack (7), pop 7 and set next greater to 8; push 8

Stack: [25, 8]
Next Greater Elements: [5, 25, 25, -, 8, -]

Why: 8 is next greater for 7

Step 7: No more elements; pop remaining stack elements (25, 8) and set their next greater to -1

Stack: empty
Next Greater Elements: [5, 25, 25, -1, 8, -1]

Why: No next greater element for 25 and 8

Result:

Next Greater Elements: [5, 25, 25, -1, 8, -1]

Annotated Code

DSA C

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

// Stack structure
typedef struct Stack {
    int *arr;
    int top;
    int capacity;
} Stack;

// Create stack
Stack* createStack(int capacity) {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->arr = (int*)malloc(capacity * sizeof(int));
    return stack;
}

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

// Push element
void push(Stack *stack, int value) {
    stack->arr[++stack->top] = value;
}

// Pop element
int pop(Stack *stack) {
    return stack->arr[stack->top--];
}

// Peek top element
int peek(Stack *stack) {
    return stack->arr[stack->top];
}

// Function to find next greater elements
void nextGreaterElement(int arr[], int n) {
    Stack *stack = createStack(n);
    int *result = (int*)malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        // While current element is greater than element at index on top of stack
        while (!isEmpty(stack) && arr[i] > arr[peek(stack)]) {
            int index = pop(stack); // pop smaller element index
            result[index] = arr[i]; // set next greater
        }
        push(stack, i); // push current index
    }

    // For remaining elements no next greater found
    while (!isEmpty(stack)) {
        int index = pop(stack);
        result[index] = -1;
    }

    // Print result
    for (int i = 0; i < n; i++) {
        printf("%d -> %d\n", arr[i], result[i]);
    }

    free(stack->arr);
    free(stack);
    free(result);
}

int main() {
    int arr[] = {4, 5, 2, 25, 7, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    nextGreaterElement(arr, n);
    return 0;
}

while (!isEmpty(stack) && arr[i] > arr[peek(stack)]) {

Check if current element is greater than element at index on top of stack to find next greater

int index = pop(stack);

Pop index of smaller element to update its next greater

result[index] = arr[i];

Assign current element as next greater for popped index

push(stack, i);

Push current index to stack to find its next greater later

while (!isEmpty(stack)) {

Assign -1 for elements with no next greater

Output

4 -> 5

5 -> 25

2 -> 25

25 -> -1

7 -> 8

8 -> -1

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once

Space: O(n) for the stack and result array to store next greater elements

vs Alternative: Naive approach is O(n^2) by checking all elements to the right for each element, stack method is much faster

Edge Cases

Empty array

No output, function handles gracefully

DSA C

for (int i = 0; i < n; i++) {

All elements equal

All next greater elements are -1

DSA C

while (!isEmpty(stack)) {

Strictly decreasing array

All next greater elements are -1

DSA C

while (!isEmpty(stack)) {

When to Use This Pattern

When asked to find the next bigger number to the right for each element efficiently, use the stack pattern to track candidates and update results in one pass.

Common Mistakes

Mistake: Pushing values instead of indices onto the stack
Fix: Push indices to access and update the result array correctly

Mistake: Not popping all smaller elements before pushing current
Fix: Use a while loop to pop all smaller elements to find their next greater

Summary

Finds the next greater element for each item in an array using a stack.

Use when you need to find the next bigger number to the right efficiently.

The key is to use a stack to remember indices of elements waiting for their next greater.