Next Greater Element Using Stack in DSA C# - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Read next element from array

↓

While stack not empty and top < current element?

↓

Pop from stack and assign current as next greater

↓

Push current element index to stack

↓

Repeat until all elements processed

↓

For remaining stack elements, assign -1 as no greater element

↓

End

We scan the array left to right, using a stack to keep indexes of elements waiting for their next greater element. When a bigger element appears, we pop smaller ones and assign their next greater.

Execution Sample

DSA C#

int[] arr = {4, 5, 2, 25};
int[] result = new int[arr.Length];
Stack<int> stack = new Stack<int>();
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()] = -1;
}

Finds next greater element for each array item using a stack to track indexes of elements waiting for a bigger number.

Execution Table

Step	Operation	Current Index i	Stack Content (indexes)	Action	Result Array State	Visual State
1	Start loop	0	[]	Push 0	[-, -, -, -]	[4]
2	Next element	1	[0]	arr[0]=4 < arr[1]=5, pop 0, result[0]=5, push 1	[5, -, -, -]	[5]
3	Next element	2	[1]	arr[1]=5 > arr[2]=2, push 2	[5, -, -, -]	[5, 2]
4	Next element	3	[1,2]	arr[2]=2 < arr[3]=25, pop 2, result[2]=25; arr[1]=5 < 25, pop 1, result[1]=25; push 3	[5, 25, 25, -]	[25]
5	End loop	-	[3]	Pop remaining 3, result[3]=-1	[5, 25, 25, -1]	[]
6	Finish	-	[]	All done	[5, 25, 25, -1]	[]

💡 All elements processed; stack emptied by assigning -1 to remaining indexes.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	N/A	0	1	2	3	-	-
stack	[]	[0]	[1]	[1,2]	[3]	[]	[]
result	[-,-,-,-]	[-,-,-,-]	[5,-,-,-]	[5,-,-,-]	[5,25,25,-]	[5,25,25,-1]	[5,25,25,-1]

Key Moments - 3 Insights

Why do we pop elements from the stack when the current element is greater?

Because the current element is the next greater element for those smaller elements on the stack. See execution_table rows 2 and 4 where popping happens and result array updates.

Why do we push the current index onto the stack after popping?

We push the current index because it might have a next greater element later. The stack keeps indexes waiting for their next greater. See execution_table rows 1, 3, and 4.

Why do remaining elements in the stack get -1 assigned at the end?

Because no greater element exists to their right. The stack holds indexes with no next greater found. See execution_table row 5.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what elements are popped from the stack?

A Indexes 3 and 2

B Indexes 0 and 1

C Indexes 2 and 1

D Only index 3

💡 Hint

Check the 'Action' and 'Stack Content' columns at Step 4 in execution_table.

At which step does the result array get the value 25 assigned for index 1?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Result Array State' column in execution_table for when result[1] changes.

If the input array was strictly decreasing, what would the final result array contain?

A Same as input array

B All elements replaced by -1

C Next greater elements to the right

D Zeros

💡 Hint

Refer to variable_tracker and key_moments about what happens when no next greater element exists.

Concept Snapshot

Next Greater Element Using Stack:
- Use a stack to store indexes of elements waiting for next greater.
- Iterate array left to right.
- While stack top element < current element, pop and assign current as next greater.
- Push current index to stack.
- After iteration, assign -1 to remaining stack indexes.
- Result array holds next greater elements or -1 if none.

Full Transcript

This concept finds the next greater element for each item in an array using a stack. We scan the array from left to right. The stack stores indexes of elements that have not yet found a bigger element to their right. When we find a bigger element, we pop smaller elements from the stack and assign the current bigger element as their next greater. We then push the current element's index onto the stack to wait for its next greater. After processing all elements, any indexes left in the stack have no next greater element, so we assign -1 to them. This method efficiently finds next greater elements in one pass.

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