Next Greater Element Using Stack in DSA Typescript - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Iterate over array from right to left

↓

While stack not empty and top <= current element

↓

Pop stack top

↓

If stack empty -> No greater element, assign -1

↓

Else top of stack is next greater element

↓

Push current element onto stack

↓

Move to next element left

↓

Repeat until all elements processed

We scan the array from right to left, using a stack to keep track of candidates for the next greater element. We pop smaller or equal elements until we find a greater one or the stack is empty.

Execution Sample

DSA Typescript

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

Finds the next greater element for each array item using a stack scanning from right to left.

Execution Table

Step	Operation	Current Index (i)	Current Element	Stack Before	Stack After	Result Array State	Explanation
1	Start	-	-	[]	[]	[-1, -1, -1, -1, -1]	Initialize empty stack and result array with -1
2	Process element	4	2	[]	[2]	[-1, -1, -1, -1, -1]	Stack empty, no greater element, push 2
3	Process element	3	5	[2]	[5]	[-1, -1, -1, -1, -1]	Pop 2 (<=5), stack empty, push 5
4	Process element	2	3	[5]	[5, 3]	[-1, -1, 5, -1, -1]	Top 5 > 3, result[2]=5, push 3
5	Process element	1	7	[5, 3]	[7]	[-1, 7, 5, -1, -1]	Pop 3 and 5 (<=7), stack empty, push 7, result[1]=7
6	Process element	0	1	[7]	[7, 1]	[7, 7, 5, -1, -1]	Top 7 > 1, result[0]=7, push 1
7	End	-	-	[7, 1]	[7, 1]	[7, 7, 5, -1, -1]	All elements processed, final result ready

💡 All elements processed from right to left, stack used to find next greater elements.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
stack	[]	[2]	[5]	[5,3]	[7]	[7,1]	[7,1]
result	[-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1]	[-1,-1,5,-1,-1]	[-1,7,5,-1,-1]	[7,7,5,-1,-1]	[7,7,5,-1,-1]
i	-	4	3	2	1	0	-

Key Moments - 3 Insights

Why do we pop elements from the stack while they are less than or equal to the current element?

Because those elements cannot be the next greater element for the current or any earlier elements. This is shown in steps 3 and 5 where smaller or equal elements are popped before pushing the current element.

Why do we scan the array from right to left instead of left to right?

Scanning from right to left allows us to find the next greater element to the right efficiently using the stack. The stack always holds candidates for next greater elements for elements to the left, as seen in the execution table steps.

What does it mean when the stack is empty during processing?

It means there is no greater element to the right of the current element, so the result remains -1 for that position, as shown in steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution table at Step 4. What is the next greater element for the element at index 2?

A 3

B 5

C 7

D -1

💡 Hint

Check the 'Result Array State' column at Step 4 for index 2.

At which step does the stack become empty after popping elements?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Stack Before' and 'Stack After' columns to see when all elements are popped.

If the input array was [4, 3, 2, 1], what would be the next greater element for index 0?

A -1

B 3

C 4

D No next greater element

💡 Hint

Refer to the logic in the execution table where no greater element to the right results in -1.

Concept Snapshot

Next Greater Element Using Stack:
- Scan array from right to left
- Use stack to track next greater candidates
- Pop smaller or equal elements from stack
- If stack empty, next greater is -1
- Else top of stack is next greater
- Push current element onto stack
- Result array stores next greater elements

Full Transcript

This visualization shows how to find the next greater element for each item in an array using a stack. We start from the right end of the array and move left. For each element, we pop elements from the stack that are smaller or equal because they can't be next greater for the current or earlier elements. If the stack is empty after popping, it means no greater element exists to the right, so we keep -1. Otherwise, the top of the stack is the next greater element. Then we push the current element onto the stack as a candidate for elements to the left. This process continues until all elements are processed. The execution table tracks the stack and result array states step-by-step, helping understand how the algorithm works internally.

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