Next Greater Element Using Stack in DSA C#

Mental Model

We find the next bigger number for each item by looking ahead using a stack to remember numbers waiting for their bigger match.

Analogy: Imagine standing in a line and looking forward to find the first taller person ahead of you. The stack keeps track of people who haven't found a taller person yet.

Array: [4, 5, 2, 25]
Stack: empty
Result: [-1, -1, -1, -1]

Dry Run Walkthrough

Input: array: [4, 5, 2, 25]

Goal: Find the next greater element for each number in the array

Step 1: Push 4 onto stack

Array: [4, 5, 2, 25]
Stack: [0]
Result: [-1, -1, -1, -1]

Why: Start with first element, no next greater found yet

Step 2: 5 is greater than top of stack (4), so pop 4 and set result for 4 as 5; then push 5

Stack: [1]
Result: [5, -1, -1, -1]

Why: 5 is next greater for 4, update result and keep 5 for next checks

Step 3: 2 is not greater than top of stack (5), push 2

Stack: [1, 2]
Result: [5, -1, -1, -1]

Why: 2 waits for a bigger number ahead

Step 4: 25 is greater than top of stack (2), pop 2 and set result for 2 as 25; also greater than 5, pop 5 and set result for 5 as 25; push 25

Stack: [3]
Result: [5, 25, 25, -1]

Why: 25 is next greater for both 2 and 5, update results

Step 5: No more elements, pop remaining stack elements and set their result as -1

Stack: empty
Result: [5, 25, 25, -1]

Why: No next greater element for 25

Result:

Result array: [5, 25, 25, -1]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class NextGreaterElement {
    public static int[] FindNextGreater(int[] arr) {
        int n = arr.Length;
        int[] result = new int[n];
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < n; i++) {
            // While current element is greater than stack top, update result
            while (stack.Count > 0 && arr[i] > arr[stack.Peek()]) {
                int index = stack.Pop();
                result[index] = arr[i];
            }
            stack.Push(i); // Push current index
        }

        // For remaining elements, no next greater element
        while (stack.Count > 0) {
            int index = stack.Pop();
            result[index] = -1;
        }

        return result;
    }

    static void Main() {
        int[] arr = {4, 5, 2, 25};
        int[] res = FindNextGreater(arr);
        for (int i = 0; i < res.Length; i++) {
            Console.Write(res[i] + (i == res.Length - 1 ? "\n" : ", "));
        }
    }
}

while (stack.Count > 0 && arr[i] > arr[stack.Peek()]) {

Check if current element is next greater for elements indexed in stack

int index = stack.Pop();

Pop index waiting for next greater element

result[index] = arr[i];

Assign next greater element for popped index

stack.Push(i);

Push current index to stack to find its next greater later

while (stack.Count > 0) {

Assign -1 for elements with no next greater element

int index = stack.Pop();

Pop remaining indices

result[index] = -1;

Set -1 for no next greater element

Output

5, 25, 25, -1

Complexity Analysis

Time: O(n) because each element is pushed and popped at most once from the stack

Space: O(n) for the stack and result array to store next greater elements

vs Alternative: Naive approach is O(n^2) by checking each element's next greater by scanning ahead; stack method is more efficient

Edge Cases

Empty array

Returns empty result array without error

DSA C#

int n = arr.Length;

All elements in descending order

All elements have no next greater, result is all -1

DSA C#

while (stack.Count > 0) { int index = stack.Pop(); result[index] = -1; }

All elements equal

No next greater element for any, result is all -1

DSA C#

while (stack.Count > 0) { int index = stack.Pop(); result[index] = -1; }

When to Use This Pattern

When you need to find the next bigger item for each element in a list efficiently, use the stack pattern to remember waiting elements and update results in one pass.

Common Mistakes

Mistake: Pushing values instead of indices onto the stack, making it hard to update the result array correctly.
Fix: Push indices to track positions and update result array properly.

Mistake: Not popping all smaller elements before pushing the current element, missing some next greater updates.
Fix: Use a while loop to pop all smaller elements before pushing current index.

Summary

Finds the next greater element for each item in an array using a stack.

Use when you want to efficiently find the next bigger number for each element without nested loops.

The key insight is to use a stack to keep track of elements waiting for their next greater number and update them as soon as a bigger number appears.

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