Next Greater Element Using Stack in DSA C - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Iterate over array from right to left

↓

While stack not empty and top <= current element

↓

Pop stack

↓

If stack empty -> No greater element, assign -1

↓

Else top of stack is next greater element

↓

Push current element onto stack

↓

Move to next element left

↓

Repeat until all elements processed

↓

Result array filled with next greater elements

We scan the array from right to left, using a stack to keep track of candidates for the next greater element. For each element, we pop smaller or equal elements from the stack until we find a greater one or the stack is empty.

Execution Sample

DSA C

int arr[] = {4, 5, 2, 25};
int n = 4;
int result[4];
// Compute next greater elements

This code finds the next greater element for each item in the array using a stack.

Execution Table

Step	Operation	Current Element	Stack Before	Stack After	Next Greater Element Assigned	Result Array State
1	Start	-	[]	[]	-	[-, -, -, -]
2	Process element 25 (rightmost)	25	[]	[25]	-1	[-, -, -, -1]
3	Process element 2	2	[25]	[25, 2]	25	[-, -, 25, -1]
4	Process element 5	5	[25, 2]	[25, 5]	25	[-, 25, 25, -1]
5	Process element 4	4	[25, 5]	[25, 5, 4]	5	[5, 25, 25, -1]
6	End	-	[25, 5, 4]	[25, 5, 4]	-	[5, 25, 25, -1]

💡 All elements processed, result array contains next greater elements or -1 if none.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
Stack	[]	[25]	[25, 2]	[25, 5]	[25, 5, 4]	[25, 5, 4]
Current Element	-	25	2	5	4	-
Result Array	[-, -, -, -]	[-, -, -, -1]	[-, -, 25, -1]	[-, 25, 25, -1]	[5, 25, 25, -1]	[5, 25, 25, -1]

Key Moments - 3 Insights

Why do we pop elements from the stack when they are smaller or equal to the current element?

Because those smaller or equal elements cannot be the next greater element for the current or any earlier elements. This is shown in step 4 where 2 is popped before pushing 5.

Why do we start scanning the array from right to left?

Because the next greater element for the rightmost element is always -1 (no elements to the right). Scanning from right to left allows us to use the stack to find the next greater element efficiently, as seen in step 2.

What does it mean when the stack is empty while processing an element?

It means there is no greater element to the right of the current element, so we assign -1 as the next greater element, as in step 2 for element 25.

Visual Quiz - 3 Questions

Look at the execution table, what is the next greater element assigned for element 4 at step 5?

A 5

B 25

C -1

D 4

💡 Hint

Check the 'Next Greater Element Assigned' column at step 5 in the execution table.

At which step does the stack first contain the element 5?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Stack After' column in the execution table to see when 5 appears.

If the input array was [4, 3, 2, 1], what would be the next greater element for 1?

A -1

B 2

C 3

D 4

💡 Hint

Consider the stack behavior when all elements are in decreasing order from left to right.

Concept Snapshot

Next Greater Element Using Stack:
- Scan array from right to left
- Use stack to track candidates
- Pop smaller/equal elements
- If stack empty, assign -1
- Else top is next greater element
- Push current element onto stack
- Repeat for all elements

Full Transcript

This visualization shows how to find the next greater element for each item in an array using a stack. We start from the rightmost element and move left. For each element, we remove smaller or equal elements from the stack because they cannot be the next greater element. If the stack is empty, it means no greater element exists to the right, so we assign -1. Otherwise, the top of the stack is the next greater element. We then push the current element onto the stack and continue. The execution table tracks the stack and result array after each step, showing how the next greater elements are assigned.