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 top

↓

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 on left

↓

Repeat until all elements processed

↓

Result array ready

We scan the array from right to left, using a stack to keep track of candidates for the next greater 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;
stack<int> s;
int res[4];
for (int i = n-1; i >= 0; i--) {
  while (!s.empty() && s.top() <= arr[i]) s.pop();
  res[i] = s.empty() ? -1 : s.top();
  s.push(arr[i]);
}

Find next greater element for each item in the array {4,5,2,25} using a stack scanning from right to left.

Execution Table

Step	Operation	Current Element	Stack Before	Stack After	Next Greater Element Assigned	Result Array State
1	Start	-	[]	[]	-	[-, -, -, -]
2	Process element at index 3	25	[]	[25]	-1 assigned (stack empty)	[-, -, -, -1]
3	Process element at index 2	2	[25]	[25, 2]	25 assigned (top of stack)	[-, -, 25, -1]
4	Process element at index 1	5	[25, 2]	[25, 5]	25 assigned (top of stack)	[-, 25, 25, -1]
5	Process element at index 0	4	[25, 5]	[25, 5, 4]	5 assigned (top of stack)	[5, 25, 25, -1]
6	End	-	[25, 5, 4]	-	-	[5, 25, 25, -1]

💡 All elements processed from right to left; stack used to find next greater elements.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	n-1=3	3	2	1	0	-1 (loop ends)
Stack	[]	[25]	[25, 2]	[25, 5]	[25, 5, 4]	[25, 5, 4]
res	[-, -, -, -]	[-, -, -, -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 while they are less than or equal to the current element?

Because those elements cannot be the next greater element for the current or any earlier elements, so we remove them to find a valid greater element on top (see steps 3 and 4 in execution_table).

Why do we scan the array from right to left instead of left to right?

Scanning from right to left allows us to use the stack to keep track of next greater elements efficiently, as we always know the next greater element to the right is on top of the stack (see concept_flow).

What happens if the stack is empty when assigning the next greater element?

It means there is no greater element to the right, so we assign -1 (see step 2 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the stack after processing element 5?

A [25, 5]

B [25, 2]

C [5]

D [25]

💡 Hint

Check the 'Stack After' column in row with Step 4 in execution_table.

At which step does the next greater element for the element 4 get assigned?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Next Greater Element Assigned' column and find when 5 is assigned.

If the input array was {4, 5, 2, 1}, what would be the next greater element for 1?

A 2

B -1

C 5

D 4

💡 Hint

Refer to the logic in concept_flow and how stack emptiness leads to -1 assignment.

Concept Snapshot

Next Greater Element Using Stack:
- Scan array from right to left.
- Use stack to track candidates for next greater.
- Pop stack while top <= current element.
- If stack empty, assign -1 else assign stack top.
- Push current element onto stack.
- Result array stores next greater 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 right end of the array and move left. For each element, we pop smaller or equal elements from the stack until we find a greater one or the stack is empty. If empty, we assign -1 as no greater element exists. Otherwise, the top of the stack is the next greater element. Then we push the current element onto the stack and continue. The execution table tracks each step, showing the stack state and the result array updates. Key moments clarify why we pop elements and why scanning is from right to left. The quiz tests understanding of stack states and assignments.

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 last element in the array

Solution

1. Step 1: Understand the problem goal

   The Next Greater Element problem aims to find, for each element, the first element to its right that is larger 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 bigger right element [OK]

Hint: Look right for the first bigger number using a stack [OK]

Common Mistakes:

• Confusing next greater with next smaller element
• Thinking it finds elements to the left
• Assuming it sums elements instead of finding one

2. Which of the following C++ code snippets correctly declares a stack to be used for Next Greater Element?

easy

A. stack<int> s = new stack<int>();

B. stack<int> s();

C. std::stack s<int>;

D. std::stack<int> s;

Solution

1. Step 1: Recall correct stack declaration syntax in C++

   The standard way to declare a stack of integers is std::stack<int> s; which creates an empty stack named s.

2. Step 2: Identify incorrect syntax in other options

   stack<int> s = new stack<int>(); uses 'new' which is not needed and incorrect here. std::stack s<int>; has wrong template syntax. stack<int> s(); declares a function, not a stack variable.

3. Final Answer:

   std::stack<int> s; -> Option D

4. Quick Check:

   std::stack<int> s; is correct stack declaration [OK]

Hint: Use std::stack<int> s; to declare stack of integers [OK]

Common Mistakes:

• Using 'new' keyword incorrectly
• Wrong template syntax like s<int>
• Declaring stack as a function

3. What is the output of the following C++ code for Next Greater Element?

std::vector<int> arr = {4, 5, 2, 25};
std::vector<int> nge(arr.size(), -1);
std::stack<int> s;
for (int i = 0; i < arr.size(); i++) {
  while (!s.empty() && arr[i] > arr[s.top()]) {
    nge[s.top()] = arr[i];
    s.pop();
  }
  s.push(i);
}
for (int x : nge) std::cout << x << " ";

medium

A. -1 -1 -1 -1

B. 25 25 -1 -1

C. 5 25 25 -1

D. 5 2 25 -1

Solution

1. Step 1: Trace the loop and stack operations

   Start with empty stack and nge = [-1, -1, -1, -1]. - i=0: push 0 (value 4) - i=1: 5 > 4, so nge[0]=5, pop 0, push 1 - i=2: 2 < 5, push 2 - i=3: 25 > 2, nge[2]=25, pop 2; 25 > 5, nge[1]=25, pop 1; push 3

2. Step 2: Final nge array after loop

   nge = [5, 25, 25, -1]. Print outputs with spaces: "5 25 25 -1 "

3. Final Answer:

   5 25 25 -1 -> Option C

4. Quick Check:

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

Hint: Push indices, update nge when current > top element [OK]

Common Mistakes:

• Printing values instead of indices
• Not popping stack after updating nge
• Confusing greater with smaller elements

4. Identify the bug in this Next Greater Element code snippet:

std::vector<int> arr = {2, 7, 3, 5, 4, 6, 8};
std::vector<int> nge(arr.size(), -1);
std::stack<int> s;
for (int i = arr.size() - 1; i >= 0; i--) {
  while (!s.empty() && arr[i] > s.top()) {
    s.pop();
  }
  if (!s.empty()) nge[i] = s.top();
  s.push(arr[i]);
}

medium

A. Stack should store indices, not values

B. Loop direction should be from 0 to arr.size() - 1

C. nge vector should be initialized with zeros

D. Comparing arr[i] with s.top() instead of arr[s.top()]

Solution

1. Step 1: Analyze stack usage in code

   The stack stores values (arr[i]) but comparisons and nge assignments expect indices to access arr elements correctly.

2. Step 2: Explain why storing indices is needed

   Storing indices allows referencing original array elements for comparison and updating nge. Storing values breaks logic when multiple same values exist.

3. Final Answer:

   Stack should store indices, not values -> Option A

4. Quick Check:

   Stack stores indices for correct comparisons [OK]

Hint: Stack must hold indices to access original array [OK]

Common Mistakes:

• Storing values instead of indices in stack
• Looping in wrong direction without adjusting logic
• Initializing nge with wrong default values

5. Given an array {13, 7, 6, 12}, how would you modify the Next Greater Element algorithm using a stack to find the Next Greater Element to the LEFT instead of the right?

hard

A. Traverse array from right to left, use stack to track elements, pop smaller elements, assign top as NGE to left.

B. Traverse array from left to right, use stack to track elements, pop smaller elements, assign top as NGE to left.

C. Traverse array from left to right, use stack to track elements, pop greater elements, assign top as NGE to left.

D. Traverse array from right to left, use stack to track elements, pop greater elements, assign top as NGE to left.

Solution

1. Step 1: Understand direction change for Next Greater to LEFT

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

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

   While scanning, pop elements smaller than current from stack. The top of stack after popping is the next greater element to the left.

3. Final Answer:

   Traverse array from left to right, use stack to track elements, pop smaller elements, assign top as NGE to left. -> Option B

4. Quick Check:

   Left NGE needs left-to-right scan and pop smaller elements [OK]

Hint: Scan left to right, pop smaller, top is left NGE [OK]

Common Mistakes:

• Scanning right to left for left NGE
• Popping greater elements instead of smaller
• Confusing next greater with next smaller element