Next Greater Element Using Stack in DSA Typescript - 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 larger than the element itself. 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 next greater element 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 elements from the stack while the current element is greater than the top of the stack. For each popped element, the current element is its Next Greater Element.

beginner

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 will be the output Next Greater Element array for input [4, 5, 2, 25]?

The output array 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 its right.

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

A Indices or values of elements waiting for their next greater element

B Only the next greater elements found so far

C All elements in sorted order

D Only the smallest elements

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 Ignore the current element

D Replace the top element with the current element

If the current element is smaller, we push it onto the stack to find its next greater element later.

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

A The first element in the array

B The smallest element in the array

C The element itself

D -1 (no greater element to the right)

The last element has no elements to its right, so its NGE is -1.

What is the main advantage of using a stack for the Next Greater Element problem?

A It uses less memory than arrays

B It sorts the array automatically

C It reduces time complexity from O(n²) to O(n)

D It finds the smallest element quickly

Using a stack allows us to find the next greater elements in linear time, O(n), instead of quadratic time.

What happens to elements left in the stack after processing the entire array?

A They are the largest elements in the array

B They have no next greater element, so their NGE is -1

C They are removed from the array

D They become the next greater elements for others

Elements left in the stack have no greater element to their right, so their NGE is set to -1.

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

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

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

Consider how many times each element interacts with the stack.

Practice

1. What does the Next Greater Element problem using a stack find for each element in an array?

easy

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

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

C. The last element in the array

D. The sum of all elements greater than the current element

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 efficiently track elements for which we haven't found a greater element yet, allowing us to find the next greater element in one pass.

3. Final Answer:

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

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
• Searching to the left instead of right
• Thinking it sums elements instead of finding one

2. Which of the following TypeScript code snippets correctly initializes an empty stack to use for Next Greater Element?

easy

A. var stack = null;

B. let stack = {};

C. const stack: number[] = [];

D. const stack = new Map();

Solution

1. Step 1: Identify correct stack data structure

   For Next Greater Element, a stack is an array used with push/pop. So, an empty array of numbers is correct.

2. Step 2: Check TypeScript syntax

   const stack: number[] = []; correctly declares an empty number array stack.

3. Final Answer:

   const stack: number[] = []; -> Option C

4. Quick Check:

   Stack = number array [] [OK]

Hint: Use number array [] for stack in TypeScript [OK]

Common Mistakes:

• Using object {} instead of array for stack
• Initializing stack as null
• Using Map which is not a stack

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

medium

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

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

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

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

Solution

1. Step 1: Process each element to find next greater

   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: Form the output array

   Output array is [5, 25, 25, -1].

3. Final Answer:

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

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 -1 too early
• Mixing up order of elements
• Confusing next greater with next smaller

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

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

medium

A. Stack should store values, not indices

B. Result array initialized with zeros instead of -1

C. Loop should run backwards from end to start

D. Incorrect stack top access: should be stack[stack.length - 1]

Solution

1. Step 1: Check stack top element access

   stack[stack.length] is undefined because array indices go from 0 to length-1. Correct is stack[stack.length - 1].

2. Step 2: Confirm other parts are correct

   Result array initialization and loop direction are correct. Stack stores indices as expected.

3. Final Answer:

   Incorrect stack top access: should be stack[stack.length - 1] -> Option D

4. Quick Check:

   Stack top index = stack[stack.length - 1] [OK]

Hint: Stack top index is length-1, not length [OK]

Common Mistakes:

• Using stack[stack.length] which is undefined
• Initializing result with wrong default
• Reversing loop unnecessarily

5. Given the array [13, 7, 6, 12], what is the Next Greater Element array using a stack approach?

hard

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

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

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

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

Solution

1. Step 1: Find next greater for each element

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

2. Step 2: Write the output array

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Check right side elements for first bigger number [OK]

Common Mistakes:

• Assigning wrong next greater for 13
• Mixing up indices and values
• Confusing next greater with previous greater