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 following C# code that finds the next greater element for each item in the array?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {4, 5, 2, 25};
        int[] result = NextGreaterElement(arr);
        foreach (int val in result) {
            Console.Write(val + " ");
        }
    }

    static int[] NextGreaterElement(int[] nums) {
        int n = nums.Length;
        int[] res = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && stack.Peek() <= nums[i]) {
                stack.Pop();
            }
            res[i] = stack.Count == 0 ? -1 : stack.Peek();
            stack.Push(nums[i]);
        }
        return res;
    }
}

A 5 25 25 -1

B 25 25 25 -1

C 25 -1 25 -1

D 5 25 -1 -1

💡 Hint

Trace the stack operations from right to left and note the next greater element for each position.

The algorithm processes the array from right to left. For each element, it pops smaller or equal elements from the stack until it finds a greater element or the stack is empty. The next greater element is the top of the stack or -1 if none exists.

For the array [4, 5, 2, 25]:

• 25 has no greater element to the right → -1
• 2's next greater is 25
• 5's next greater is 25
• 4's next greater is 5

🧠 Conceptual

intermediate

Understanding the role of stack in Next Greater Element

Why do we use a stack to solve the Next Greater Element problem efficiently?

A Because stack stores all elements so we can access them randomly anytime.

B Because stack helps keep track of elements in decreasing order to find the next greater element quickly.

C Because stack sorts the array automatically to find greater elements.

D Because stack reverses the array to process elements from left to right.

💡 Hint

Think about how the stack helps us remember candidates for the next greater element while scanning from right to left.

The stack stores elements in decreasing order from top to bottom. When processing from right to left, smaller elements are popped out, so the top always holds the next greater element candidate. This avoids scanning all elements repeatedly.

🔧 Debug

advanced

Identify the error in Next Greater Element implementation

What error will the following code produce when trying to find the next greater element?

DSA C#

int[] NextGreaterElement(int[] nums) {
    int n = nums.Length;
    int[] res = new int[n];
    Stack<int> stack = new Stack<int>();

    for (int i = 0; i < n; i++) {
        while (stack.Count > 0 && stack.Peek() <= nums[i]) {
            stack.Pop();
        }
        res[i] = stack.Count == 0 ? -1 : stack.Peek();
        stack.Push(nums[i]);
    }
    return res;
}

A The output will be incorrect because the loop processes from left to right instead of right to left.

B The code will cause an infinite loop due to missing increment in the for loop.

C The code will throw a NullReferenceException at stack.Peek().

D The code will compile but return an array of all -1 values.

💡 Hint

Consider the direction of traversal needed for the stack approach to work correctly.

The standard Next Greater Element algorithm using a stack requires processing the array from right to left. Processing from left to right as in this code will not correctly find the next greater elements, leading to wrong results.

❓ Predict Output

advanced

Next Greater Element output for circular array

What is the output of the following code that finds the next greater element in a circular array?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {1, 2, 1};
        int[] result = NextGreaterElementCircular(arr);
        foreach (int val in result) {
            Console.Write(val + " ");
        }
    }

    static int[] NextGreaterElementCircular(int[] nums) {
        int n = nums.Length;
        int[] res = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = 2 * n - 1; i >= 0; i--) {
            while (stack.Count > 0 && stack.Peek() <= nums[i % n]) {
                stack.Pop();
            }
            res[i % n] = stack.Count == 0 ? -1 : stack.Peek();
            stack.Push(nums[i % n]);
        }
        return res;
    }
}

A 2 -1 -1

B 2 2 -1

C -1 2 -1

D 2 -1 2

💡 Hint

Remember the array is circular, so after the last element, it wraps around to the first.

For the circular array [1, 2, 1]:

• Next greater for 1 (index 0) is 2
• Next greater for 2 (index 1) does not exist → -1
• Next greater for 1 (index 2) is 2 (from index 1)

🚀 Application

expert

Number of elements with no next greater element

Given the array [13, 7, 6, 12], how many elements have no next greater element to their right?

A 3

B 1

C 2

D 0

💡 Hint

Find the next greater element for each item and count how many are -1.

Next greater elements:

• 13 → no greater element → -1
• 7 → next greater is 12
• 6 → next greater is 12
• 12 → no greater element → -1

Elements with no next greater element: 13 and 12 → 2 elements.

Practice

1. What does the Next Greater Element 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 sum of all elements greater than the current element

D. The index of the maximum element in the array

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Identify the role of the stack

   A stack helps track elements for which we haven't found a greater element yet, allowing efficient lookup of the next greater element.

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: Next Greater Element means first bigger number on right [OK]

Common Mistakes:

• Confusing next greater with next smaller element
• Thinking it finds the maximum element overall
• Assuming it finds elements to the left instead of right

2. Which of the following C# code snippets correctly initializes a stack to solve the Next Greater Element problem?

easy

A. int[] stack = new int[10];

B. Stack stack = new Stack();

C. List<int> stack = new List<int>();

D. Stack<int> stack = new Stack<int>();

Solution

1. Step 1: Identify correct stack initialization syntax in C#

   Using generic Stack<int> with new Stack<int>() is the modern and type-safe way to create a stack of integers.

2. Step 2: Compare other options

   Stack stack = new Stack(); uses non-generic Stack (older style), C uses List which is not a stack, D uses array which is fixed size and not a stack.

3. Final Answer:

   Stack<int> stack = new Stack<int>(); -> Option D

4. Quick Check:

   Generic Stack<int> initialization is correct [OK]

Hint: Use generic Stack<int> for integer stacks in C# [OK]

Common Mistakes:

• Using non-generic Stack without type safety
• Using List instead of Stack for LIFO behavior
• Using fixed-size arrays instead of dynamic stack

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

medium

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

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

C. [25, 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: Form the output array

   Output array is [5, 25, 25, -1].

3. Final Answer:

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

4. Quick Check:

   Next Greater Elements = [5, 25, 25, -1] [OK]

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

Common Mistakes:

• Assigning -1 too early for elements with greater elements later
• Confusing next greater with next smaller
• Misreading the input array order

4. Identify the error in the following C# code snippet for Next Greater Element:

int[] arr = {2, 7, 3, 5, 4, 6, 8};
Stack<int> stack = new Stack<int>();
int[] result = new int[arr.Length];
for (int i = 0; i < arr.Length; i++) {
  while (stack.Count > 0 && arr[stack.Peek()] < arr[i]) {
    result[stack.Pop()] = arr[i];
  }
  stack.Push(i);
}
while (stack.Count > 0) {
  result[stack.Pop()] = 0;
}

medium

A. Using arr[i] instead of arr[stack.Peek()] in while condition

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

C. Pushing values instead of indices onto the stack

D. Not initializing the result array

Solution

1. Step 1: Check how no greater elements are marked

   The code assigns 0 to elements with no next greater element, but conventionally -1 is used to indicate none.

2. Step 2: Verify other parts of the code

   Indices are pushed, arr[stack.Peek()] is correctly used, and result array is initialized, so no errors there.

3. Final Answer:

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

4. Quick Check:

   No greater element marked as -1, not 0 [OK]

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

Common Mistakes:

• Using 0 instead of -1 for no greater element
• Pushing values instead of indices on stack
• Incorrect while loop condition

5. Given the array [13, 7, 6, 12], how would you modify the Next Greater Element algorithm to find the next greater element to the left instead of the right?

hard

A. Traverse the array from right to left and use a stack to track elements, popping greater ones.

B. Traverse the array from right to left and use a stack to track elements, popping smaller ones.

C. Traverse the array from left to right and use a stack to track elements, popping smaller ones.

D. Traverse the array from left to right and use a queue instead of a stack.

Solution

1. Step 1: Understand direction change for next greater to left

   To find next greater element on the left, we must scan from left to right, checking elements before current.

2. Step 2: Use stack to track candidates and pop smaller elements

   We push elements and pop smaller ones to find the nearest greater on the left efficiently.

3. Final Answer:

   Traverse the array from left to right and use a stack to track elements, popping smaller ones. -> Option C

4. Quick Check:

   Next greater left = left to right traversal with stack [OK]

Hint: For next greater left, scan left to right popping smaller elements [OK]

Common Mistakes:

• Scanning right to left for next greater left
• Using queue instead of stack
• Popping greater elements instead of smaller