Next Greater Element Using Stack in DSA Typescript

Mental Model

We find the next bigger number for each item by looking ahead using a stack to remember numbers waiting for their bigger match.

Analogy: Imagine people standing in a line waiting for someone taller to stand behind them. The stack keeps track of people waiting until a taller person arrives.

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

Dry Run Walkthrough

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

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

Step 1: Push 4 onto stack

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

Why: Start with first number, no next greater found yet

Step 2: 5 is greater than top of stack (4), pop 0 and set result for 4 as 5, then push 1

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

Why: Found next greater for 4, now wait for next greater for 5

Step 3: 2 is not greater than top of stack (5), push 2

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

Why: 2 waits for a bigger number

Step 4: 25 is greater than top of stack (2), pop 2 and set result for 2 as 25; 25 is also greater than next top (5), pop 1 and set result for 5 as 25; push 3

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

Why: Found next greater for 2 and 5, now wait for next greater for 25

Result:

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

Annotated Code

DSA Typescript

class NextGreaterElement {
  static findNextGreater(arr: number[]): number[] {
    const result = new Array(arr.length).fill(-1);
    const stack: number[] = [];

    for (let i = 0; i < arr.length; i++) {
      while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
        const index = stack.pop()!;
        result[index] = arr[i];
      }
      stack.push(i);
    }

    return result;
  }
}

// Driver code
const input = [4, 5, 2, 25];
const output = NextGreaterElement.findNextGreater(input);
console.log(output.join(' '));

while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {

Check if current element is greater than element at top index of stack to find next greater

const index = stack.pop()!;

Pop index from stack to update its next greater element

result[index] = arr[i];

Assign current element as next greater for popped index

stack.push(i);

Push current index to stack to find its next greater later

Output

5 25 25 -1

Complexity Analysis

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

Space: O(n) for the stack and result array to store next greater elements

vs Alternative: Naive approach is O(n^2) by checking each element's next greater by scanning ahead, which is slower for large arrays

Edge Cases

Empty array

Returns empty result array without error

DSA Typescript

for (let i = 0; i < arr.length; i++) {

All elements equal

No next greater elements found, all remain -1

DSA Typescript

while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {

Strictly decreasing array

No next greater elements found, all remain -1

DSA Typescript

while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {

When to Use This Pattern

When you need to find the next bigger item for each element in a list efficiently, use the stack pattern to remember waiting elements and find their next greater in one pass.

Common Mistakes

Mistake: Pushing values instead of indices onto the stack
Fix: Push indices to track positions and update result array correctly

Mistake: Not using a while loop to pop multiple smaller elements
Fix: Use while loop to pop all smaller elements before pushing current

Summary

Finds the next bigger number for each element in an array using a stack.

Use when you want to quickly find the next greater element for each item without checking all pairs.

Remember to use a stack to keep track of indices waiting for their next bigger number.

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