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.

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