Next Greater Element Using Stack in DSA C++

Mental Model

We find the next bigger number for each element by looking ahead using a stack to remember candidates.

Analogy: Imagine standing in a line of people with different heights. For each person, you look forward to find the first taller person. The stack helps you keep track of people waiting to find their taller neighbor.

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

Dry Run Walkthrough

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

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

Step 1: Push 4 onto stack

Array: [4, 5, 2, 25, 7, 8]
Stack: [4]
Result: [-1, -1, -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[0] = 5; then push 5

Array: [4, 5, 2, 25, 7, 8]
Stack: [5]
Result: [5, -1, -1, -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

Array: [4, 5, 2, 25, 7, 8]
Stack: [5, 2]
Result: [5, -1, -1, -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[2] = 25; also greater than 5, pop 5 and set result[1] = 25; push 25

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

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

Step 5: 7 is not greater than top of stack (25), push 7

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

Why: 7 waits for a bigger number ahead

Step 6: 8 is greater than top of stack (7), pop 7 and set result[4] = 8; push 8

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

Why: 8 is next greater for 7, update result and keep 8 for next checks

Step 7: End of array reached; pop remaining stack elements (25 and 8) and set their results to -1

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

Why: No next greater elements for 25 and 8, so result remains -1

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreaterElement(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1); // Initialize all with -1
    stack<int> s; // stack to hold indices

    for (int i = 0; i < n; i++) {
        // While current element is greater than element at stack top index
        while (!s.empty() && arr[i] > arr[s.top()]) {
            int idx = s.top();
            s.pop();
            result[idx] = arr[i]; // Update result for popped index
        }
        s.push(i); // Push current index
    }
    // Remaining indices in stack have no next greater element, remain -1
    return result;
}

int main() {
    vector<int> arr = {4, 5, 2, 25, 7, 8};
    vector<int> res = nextGreaterElement(arr);
    for (int val : res) {
        cout << val << " ";
    }
    cout << endl;
    return 0;
}

while (!s.empty() && arr[i] > arr[s.top()]) {

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

int idx = s.top(); s.pop(); result[idx] = arr[i];

Pop index from stack and update its next greater element

s.push(i);

Push current index to stack to find its next greater later

Output

5 25 25 -1 8 -1 

Complexity Analysis

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

Space: O(n) for the stack and result array

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

Edge Cases

Empty array

Returns empty result array immediately

DSA C++

int n = arr.size();

All elements in descending order

All results remain -1 because no next greater element exists

DSA C++

while (!s.empty() && arr[i] > arr[s.top()]) {

All elements equal

All results remain -1 because no strictly greater element exists

DSA C++

while (!s.empty() && arr[i] > arr[s.top()]) {

When to Use This Pattern

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

Common Mistakes

Mistake: Pushing values instead of indices onto the stack, making it hard to update the correct result position
Fix: Push indices onto the stack so you can update the result array at the correct position

Mistake: Not popping all smaller elements from the stack before pushing the current element
Fix: Use a while loop to pop all smaller elements to correctly assign their next greater element

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