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.

Practice

1. What does the Next Greater Element (NGE) problem using a stack find for each element in an array?

easy

A. The first greater element to the right of each element

B. The first smaller element to the left of each element

C. The last element in the array

D. The sum of all elements greater than the current element

Solution

1. Step 1: Understand the problem definition

   The Next Greater Element problem asks for the first element to the right of each element that is greater than it.

2. Step 2: Identify the role of the stack

   The stack helps efficiently find this next greater element by storing candidates and popping smaller elements.

3. Final Answer:

   The first greater element to the right of each element -> Option A

4. Quick Check:

   Next Greater Element = first greater right element [OK]

Hint: Look right for the first bigger number using a stack [OK]

Common Mistakes:

• Confusing next greater with next smaller element
• Looking to the left instead of right
• Thinking it sums elements instead of finding one

2. Which of the following C code snippets correctly initializes an empty stack for Next Greater Element problem?

easy

A. int stack[100]; int top = -1;

B. int stack[] = {0}; int top = 0;

C. int *stack; int top = NULL;

D. stack = new int[100]; top = -1;

Solution

1. Step 1: Check valid C array and top initialization

   int stack[100]; int top = -1; declares a fixed size array and sets top to -1 indicating empty stack.

2. Step 2: Identify invalid syntax or semantics in other options

   int stack[] = {0}; int top = 0; initializes top to 0 which means stack is not empty; int *stack; int top = NULL; uses NULL for int top which is invalid; stack = new int[100]; top = -1; uses 'new' which is C++ syntax, not C.

3. Final Answer:

   int stack[100]; int top = -1; -> Option A

4. Quick Check:

   Stack array + top = -1 means empty [OK]

Hint: Use array and top = -1 for empty stack in C [OK]

Common Mistakes:

• Using C++ 'new' keyword in C code
• Initializing top to 0 instead of -1
• Using pointer without allocation

3. What is the output of the Next Greater Element array for input [4, 5, 2, 25] using the stack method?

medium

A. [25, 25, -1, -1]

B. [5, 2, 25, -1]

C. [5, 25, 25, -1]

D. [-1, -1, -1, -1]

Solution

1. Step 1: Process each element to find next greater

   For 4, next greater is 5; for 5, next greater is 25; for 2, next greater is 25; for 25, no greater element, so -1.

2. Step 2: Confirm output array

   The output array is [5, 25, 25, -1].

3. Final Answer:

   [5, 25, 25, -1] -> Option C

4. Quick Check:

   Next greater elements match output [OK]

Hint: Check each element's right side for first bigger number [OK]

Common Mistakes:

• Assigning smaller or wrong next greater values
• Using -1 for elements that do have greater elements
• Confusing order of output

4. Identify the bug in this C code snippet for Next Greater Element using stack:

for (int i = 0; i < n; i++) {
  while (top != -1 && arr[stack[top]] < arr[i]) {
    result[stack[top]] = arr[i];
    top--;
  }
  stack[++top] = i;
}
while (top != -1) {
  result[stack[top]] = 0;
  top--;
}

medium

A. Using post-increment instead of pre-increment on stack index

B. Assigning 0 instead of -1 for elements with no greater element

C. Incorrect loop condition causing infinite loop

D. Not initializing top before loop

Solution

1. Step 1: Check final assignment for elements with no next greater

   The code assigns 0 instead of -1, which is incorrect as per problem definition.

2. Step 2: Verify other parts of code

   Stack index increment and loop conditions are correct; top is assumed initialized before.

3. Final Answer:

   Assigning 0 instead of -1 for elements with no greater element -> Option B

4. Quick Check:

   No greater element should be -1, not 0 [OK]

Hint: Use -1 for no next greater element, not 0 [OK]

Common Mistakes:

• Using 0 instead of -1 for no next greater
• Forgetting to initialize top
• Wrong increment operator on stack

5. Given the array [13, 7, 6, 12], what is the Next Greater Element array using the stack approach? Also, explain why the last element's next greater is -1.

hard

A. [ 7, 12, 13, -1 ]

B. [ -1, 13, 12, -1 ]

C. [ -1, 12, -1, -1 ]

D. [ -1, 12, 12, -1 ]

Solution

1. Step 1: Find next greater for each element

   For 13, no greater element to right, so -1; for 7, next greater is 12; for 6, next greater is 12; for 12, no greater element, so -1.

2. Step 2: Explain last element's next greater

   The last element 12 has no elements to its right, so no next greater element exists, hence -1.

3. Final Answer:

   [ -1, 12, 12, -1 ] -> Option D

4. Quick Check:

   Last element no right neighbor = -1 [OK]

Hint: Last element always has -1 as no elements to right [OK]

Common Mistakes:

• Assigning next greater to last element
• Mixing up next greater for middle elements
• Confusing output order