Next Greater Element Using Stack in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Greater Element for a given array

What is the output of the Next Greater Element array for the input array [4, 5, 2, 25] using a stack-based approach?

DSA C

int arr[] = {4, 5, 2, 25};
int n = 4;
// Next Greater Element logic using stack
// Output format: [NGE for each element in order]

A [5, 2, 25, -1]

B [5, 25, 25, -1]

C [25, 25, -1, -1]

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

💡 Hint

Remember, the next greater element for each element is the first element to the right that is greater than it.

For 4, the next greater element is 5; for 5, it is 25; for 2, it is 25; for 25, there is no greater element to the right, so -1.

❓ Predict Output

intermediate

Next Greater Element output for a descending array

What is the output of the Next Greater Element array for the input array [9, 7, 5, 3, 1] using a stack?

DSA C

int arr[] = {9, 7, 5, 3, 1};
int n = 5;
// Next Greater Element logic using stack
// Output format: [NGE for each element in order]

A [-1, -1, -1, -1, -1]

B [1, 3, 5, 7, 9]

C [9, 7, 5, 3, 1]

D [7, 5, 3, 1, -1]

💡 Hint

In a strictly descending array, no element has a greater element to its right.

Since the array is strictly descending, no element has a next greater element, so all are -1.

🔧 Debug

advanced

Identify the error in Next Greater Element implementation

What error will this code produce when finding the Next Greater Element using a stack?

DSA C

int arr[] = {2, 7, 3, 5, 4, 6, 8};
int n = 7;
int stack[7];
int top = -1;
int result[7];
for (int i = 0; i < n; i++) result[i] = -1;
for (int i = 0; i < n; i++) {
  while (top >= 0 && arr[i] > arr[stack[top]]) {
    result[stack[top]] = arr[i];
    top--;
  }
  stack[++top] = i;
}
// print result array

A No error, outputs correct Next Greater Element array

B Runtime error due to stack overflow

C Logical error: result array remains all -1

D Compilation error due to missing semicolon

💡 Hint

Check if the stack is used correctly and indices are managed properly.

The code correctly uses a stack to track indices and updates the result array with the next greater elements. No errors occur.

🧠 Conceptual

advanced

Time complexity of Next Greater Element using stack

What is the time complexity of finding the Next Greater Element for an array of size n using a stack?

A O(log n)

B O(n log n)

C O(n^2)

D O(n)

💡 Hint

Each element is pushed and popped at most once from the stack.

Each element is pushed onto the stack once and popped once, so total operations are proportional to n, making it O(n).

🚀 Application

expert

Next Greater Element for circular array

Given a circular array [1, 2, 1], what is the Next Greater Element array using a stack approach that considers the array circular (elements after the last wrap to the start)?

DSA C

int arr[] = {1, 2, 1};
int n = 3;
// Circular Next Greater Element logic using stack
// Output format: [NGE for each element in order]

A [1, 2, 1]

B [-1, -1, -1]

C [2, -1, 2]

D [2, 1, -1]

💡 Hint

For circular arrays, consider iterating twice the length and use modulo for indices.

For element 1 at index 0, next greater is 2; for 2 at index 1, no greater element; for 1 at index 2, next greater is 2 (from index 1).

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