Next Greater Element Using Stack in DSA C - Build from Scratch

Next Greater Element Using Stack

📖 Scenario: Imagine you have a list of daily temperatures, and you want to find for each day the next day when the temperature will be higher. This helps you plan your activities better.

🎯 Goal: You will build a program that finds the next greater element for each number in an array using a stack. The next greater element is the first number to the right that is bigger than the current number.

📋 What You'll Learn

Create an integer array called arr with the exact values: 4, 5, 2, 25

Create an integer variable called n and set it to the size of arr

Create an integer array called result of size n to store next greater elements

Use a stack implemented as an integer array called stack with a variable top to track the top index

Write a loop to find the next greater element for each item in arr using the stack

Print the result array in the format: 4 -> 5, 5 -> 25, 2 -> 25, 25 -> -1

💡 Why This Matters

🌍 Real World

Finding the next greater element is useful in stock price analysis, weather forecasting, and many other areas where you want to know the next time a value increases.

💼 Career

Understanding stacks and next greater element problems is common in coding interviews and helps build problem-solving skills for software development roles.

1

Create the array and size variable

Create an integer array called arr with these exact values: 4, 5, 2, 25. Then create an integer variable called n and set it to the size of arr.

DSA C

// Create the array arr and variable n
// Your code here

Hint

Use int arr[] = {4, 5, 2, 25}; to create the array. Use sizeof(arr) / sizeof(arr[0]) to get the number of elements.

2

Create the stack and result array

Create an integer array called result of size n to store next greater elements. Also create an integer array called stack of size n and an integer variable top initialized to -1 to use as a stack.

DSA C

#include 

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

    // Create result array and stack array with top
    // Your code here

    return 0;
}

Hint

Use int result[n]; and int stack[n];. Initialize top to -1 to indicate the stack is empty.

3

Find next greater elements using the stack

Write a for loop with variable i from 0 to n-1. Inside, use a while loop to pop from stack while top is not -1 and arr[i] is greater than arr[stack[top]]. For each popped index, set result at that index to arr[i]. Then push i onto stack. After the loop, pop remaining indices from stack and set their result to -1.

DSA C

#include 

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

    int result[n];
    int stack[n];
    int top = -1;

    // Find next greater elements using stack
    // Your code here

    return 0;
}

Hint

Use a for loop to go through arr. Use a while loop to pop from stack when current element is bigger. Assign next greater element in result. Push current index to stack. After the loop, assign -1 to remaining indices in result.

4

Print the next greater elements

Use a for loop with variable i from 0 to n-1 to print each element of arr and its next greater element from result in the format: 4 -> 5, 5 -> 25, 2 -> 25, 25 -> -1. Use printf and print a comma and space after each pair except the last.

DSA C

#include 

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

    int result[n];
    int stack[n];
    int top = -1;

    for (int i = 0; i  arr[stack[top]]) {
            result[stack[top]] = arr[i];
            top--;
        }
        top++;
        stack[top] = i;
    }

    while (top != -1) {
        result[stack[top]] = -1;
        top--;
    }

    // Print the next greater elements in the format "4 -> 5, 5 -> 25, 2 -> 25, 25 -> -1"
    // Your code here

    return 0;
}

Hint

Use a for loop to print each pair. Use printf("%d -> %d", arr[i], result[i]). Print a comma and space except after the last pair.