Next Greater Element Using Stack in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Next Greater Element (NGE) for an element in an array?

The Next Greater Element for an element is the first element to its right that is greater than it. If no such element exists, the NGE is -1.

intermediate

Why do we use a stack to solve the Next Greater Element problem efficiently?

A stack helps keep track of elements for which we haven't found the NGE yet. It allows us to find the NGE in a single pass by comparing current elements with the top of the stack.

intermediate

What is the time complexity of the Next Greater Element algorithm using a stack?

The time complexity is O(n) because each element is pushed and popped at most once from the stack.

intermediate

In the Next Greater Element algorithm, what happens when the current element is greater than the element at the top of the stack?

We pop the top element from the stack and assign the current element as its Next Greater Element. We repeat this until the stack is empty or the top element is greater than the current element.

beginner

What value do we assign to elements that do not have a Next Greater Element?

We assign -1 to elements that do not have any greater element to their right.

What data structure is most suitable for solving the Next Greater Element problem efficiently?

A Stack

B Queue

C Array

D Linked List

Stack allows us to keep track of elements waiting for their Next Greater Element in O(n) time.

What is the Next Greater Element for the last element in the array?

A The first element

B -1

C The element itself

D The previous element

The last element has no elements to its right, so its Next Greater Element is -1.

If the current element is smaller than the top of the stack, what do we do in the NGE algorithm?

A Ignore the current element

B Pop the stack

C Push the current element onto the stack

D Replace the top of the stack

We push the current element because we haven't found its NGE yet.

What is the worst-case time complexity of the Next Greater Element algorithm using a stack?

A O(n)

B O(n log n)

C O(n^2)

D O(log n)

Each element is pushed and popped at most once, so the algorithm runs in linear time.

What does the stack store during the Next Greater Element algorithm?

A Only the largest element

B All elements in the array

C The final NGE values

D Indices or values of elements waiting for their NGE

The stack stores elements (or their indices) for which we haven't found the Next Greater Element yet.

Explain how the stack is used step-by-step to find the Next Greater Element for each element in an array.

Think about how you handle each element and the stack's role.

Describe the time complexity of the Next Greater Element algorithm using a stack and why it is efficient.

Focus on how many times each element is processed.

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