Next Greater Element Using Stack in DSA Javascript - 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 the right of it in the array that is greater than it. If no such element exists, the NGE is -1.

intermediate

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

A stack helps keep track of elements for which we haven't found the NGE yet. It allows us to process elements in a way that avoids checking all pairs, reducing time from O(n²) to O(n).

intermediate

In the Next Greater Element algorithm using a stack, what do we do 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, because the current element is the first greater element to the right.

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.

beginner

What is the output of the Next Greater Element algorithm for the array [4, 5, 2, 25]?

The output is [5, 25, 25, -1]. Explanation: 4's NGE is 5, 5's NGE is 25, 2's NGE is 25, and 25 has no greater element to the right.

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

A Indices or values of elements waiting for their NGE

B Only the greatest elements found so far

C All elements in sorted order

D Elements that have found their NGE

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

If the current element is smaller than the top of the stack, what should we do?

A Push the current element onto the stack

B Pop the top element from the stack

C Replace the top element with the current element

D Ignore the current element

If the current element is smaller, we push it onto the stack because it might have a greater element later.

What value do we assign if no Next Greater Element exists for an element?

A 0

B -1

C The element itself

D Infinity

We assign -1 to indicate no greater element exists to the right.

What is the main advantage of using a stack for NGE over a brute force approach?

A Simpler code

B Less memory usage

C Faster time complexity (O(n) vs O(n²))

D Works only for sorted arrays

Using a stack reduces the time complexity from O(n²) to O(n).

For the array [13, 7, 6, 12], what is the Next Greater Element for 7?

A 13

B 6

C -1

D 12

The first greater element to the right of 7 is 12.

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

Think about how the stack helps track elements waiting for their next greater.

Describe the difference in time complexity between the brute force method and the stack method for Next Greater Element.

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 sum of all elements greater than the current element

B. The first smaller element to the left of each element

C. The last element in the array

D. The first greater element to the right of each element

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: Recognize the role of the stack

   A stack helps track elements waiting for their next greater element to appear on the right.

3. Final Answer:

   The first greater element to the right of each element -> Option D

4. Quick Check:

   Next Greater Element = first bigger right element [OK]

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

Common Mistakes:

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

2. Which of the following is the correct way to initialize an empty stack in JavaScript for solving Next Greater Element?

easy

A. const stack = null;

B. const stack = {};

C. const stack = [];

D. const stack = 0;

Solution

1. Step 1: Identify stack data structure in JavaScript

   Stacks are commonly implemented using arrays in JavaScript, so initializing with [] is correct.

2. Step 2: Check other options

   { } is an object, null is no value, 0 is a number, none suitable for stack operations.

3. Final Answer:

   const stack = []; -> Option C

4. Quick Check:

   Stack = array [] for push/pop [OK]

Hint: Use array [] for stack in JavaScript [OK]

Common Mistakes:

• Using object {} instead of array
• Assigning null or number instead of array
• Not initializing stack before use

3. What is the output of the Next Greater Element array for input [4, 5, 2, 25]?

medium

A. [-1, -1, -1, -1]

B. [5, 25, 25, -1]

C. [25, 25, -1, -1]

D. [5, 2, 25, -1]

Solution

1. Step 1: Find next greater for each element

   4's next greater is 5, 5's next greater is 25, 2's next greater is 25, 25 has none so -1.

2. Step 2: Write output array

   The output array is [5, 25, 25, -1].

3. Final Answer:

   [5, 25, 25, -1] -> Option B

4. Quick Check:

   Next Greater Element for [4,5,2,25] = [5,25,25,-1] [OK]

Hint: Check each element's right side for first bigger number [OK]

Common Mistakes:

• Assigning smaller or equal numbers as next greater
• Using -1 for elements that do have greater elements
• Mixing order of output array

4. Given the code snippet below, what is the bug that prevents correct Next Greater Element output?

function nextGreater(arr) {
  const stack = [];
  const result = new Array(arr.length).fill(-1);
  for (let i = 0; i <= arr.length; i++) {
    while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
      const idx = stack.pop();
      result[idx] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

medium

A. Loop condition should be i < arr.length, not i <= arr.length

B. Stack should be initialized with arr values, not empty

C. Result array should be filled with zeros, not -1

D. Push should add arr[i], not index i

Solution

1. Step 1: Check loop boundary

   The loop runs from i = 0 to i <= arr.length, which causes arr[i] to be undefined at i = arr.length, causing errors.

2. Step 2: Correct loop condition

   Change to i < arr.length to avoid out-of-bound access and fix logic.

3. Final Answer:

   Loop condition should be i < arr.length, not i <= arr.length -> Option A

4. Quick Check:

   Loop index must be within array length [OK]

Hint: Use i < arr.length to avoid undefined access [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Pushing values instead of indices to stack
• Filling result with wrong default values

5. You have an array [13, 7, 6, 12]. Using the Next Greater Element approach with a stack, what is the final output array?

hard

A. [ -1, 12, 12, -1 ]

B. [ -1, 13, 12, -1 ]

C. [ -1, -1, 12, -1 ]

D. [ 7, 6, 12, -1 ]

Solution

1. Step 1: Find next greater for each element

   13 has no greater element to the right, so -1. 7's next greater is 12. 6's next greater is 12. 12 has none, so -1.

2. Step 2: Check if any element has a greater element before it

   13 is greater than 7 and 6, so their next greater is 12, but 7's next greater is 12, not 13. 13 itself has no greater element.

3. Step 3: Confirm output array

   The output is [-1, 12, 12, -1].

4. Final Answer:

   [-1, 12, 12, -1] -> Option A

5. Quick Check:

   Next Greater Element for [13,7,6,12] = [-1,12,12,-1] [OK]

Hint: Check right side for first bigger number, use stack to track indices [OK]

Common Mistakes:

• Assigning previous greater 13 instead of next greater 12 for 7
• Confusing next greater with previous greater
• Mixing output order