Next Greater Element Using Stack in DSA Javascript - Execution Trace

Concept Flow - Next Greater Element Using Stack

Start with empty stack

↓

Iterate over array from left to right

↓

While stack not empty and current element > top of stack element

↓

Pop from stack and assign current element as next greater

↓

Push current element index onto stack

↓

Repeat until end of array

↓

For remaining indices in stack, assign -1 as no next greater

↓

Done

We scan the array left to right, using a stack to keep indexes of elements waiting for their next greater element. When a bigger element appears, we pop smaller ones and assign their next greater.

Execution Sample

DSA Javascript

const arr = [4, 5, 2, 25];
const result = [];
const stack = [];
for (let i = 0; i < arr.length; i++) {
  while (stack.length && arr[i] > arr[stack[stack.length - 1]]) {
    result[stack.pop()] = arr[i];
  }
  stack.push(i);
}
while (stack.length) {
  result[stack.pop()] = -1;
}
console.log(result);

Finds next greater element for each array item using a stack to track indexes of elements waiting for a bigger number.

Execution Table

Step	Operation	Current Index (i)	Stack (indexes)	Action	Result Array	Visual State
1	Start iteration	0	[]	Push index 0	[]	[4] stack=[0], result=[]
2	Next iteration	1	[0]	arr[1]=5 > arr[0]=4, pop 0, result[0]=5; push 1	[5]	[4,5] stack=[1], result=[5]
3	Next iteration	2	[1]	arr[2]=2 <= arr[1]=5, push 2	[5]	[4,5,2] stack=[1,2], result=[5,-]
4	Next iteration	3	[1,2]	arr[3]=25 > arr[2]=2, pop 2, result[2]=25; arr[3]=25 > arr[1]=5, pop 1, result[1]=25; push 3	[5,25,25]	[4,5,2,25] stack=[3], result=[5,25,25]
5	End iteration	-	[3]	Pop remaining index 3, result[3]=-1	[5,25,25,-1]	[4,5,2,25] stack=[], result=[5,25,25,-1]
6	Done	-	[]	All processed	[5,25,25,-1]	[4,5,2,25] stack=[], result=[5,25,25,-1]

💡 All elements processed; stack emptied by assigning -1 to remaining indexes

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	undefined	0	1	2	3	-	-
stack	[]	[0]	[1]	[1,2]	[3]	[]	[]
result	[]	[]	[5]	[5,-]	[5,25,25]	[5,25,25,-1]	[5,25,25,-1]
arr	[4,5,2,25]	[4,5,2,25]	[4,5,2,25]	[4,5,2,25]	[4,5,2,25]	[4,5,2,25]	[4,5,2,25]

Key Moments - 3 Insights

Why do we pop from the stack only when the current element is greater than the element at the top of the stack?

Because the stack holds indexes of elements waiting for their next greater element. When the current element is bigger, it is the next greater for those smaller elements on top of the stack. This is shown in execution_table rows 2 and 4 where popping happens only if arr[i] > arr[stack top].

Why do we push the current index onto the stack even if no popping happens?

We push the current index to wait for its next greater element in the future. This is shown in execution_table row 3 where arr[2]=2 is not greater than arr[1]=5, so we push index 2 to stack.

Why do we assign -1 to remaining indexes in the stack after iteration?

Because those elements have no next greater element to their right. This is shown in execution_table row 5 where index 3 remains and gets -1 assigned.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4. What happens to the stack after processing current index 3?

A Stack contains indexes [1, 2, 3]

B Stack contains only index [3]

C Stack is empty

D Stack contains indexes [0, 3]

💡 Hint

Refer to the 'Stack (indexes)' column at Step 4 in execution_table

At which step does the result array first get a value assigned for index 0?

A Step 1

B Step 2

C Step 3

D Step 5

💡 Hint

Check the 'Result Array' column for index 0 assignment in execution_table

If the input array was strictly decreasing, what would the final result array look like?

A All elements replaced by -1

B Same as input array

C All elements replaced by the first element

D Alternating -1 and input values

💡 Hint

Consider the exit_note and how remaining stack indexes get -1 assigned

Concept Snapshot

Next Greater Element Using Stack:
- Iterate array left to right
- Use stack to store indexes waiting for next greater
- While current > stack top element, pop and assign current as next greater
- Push current index to stack
- After iteration, assign -1 to remaining indexes
- Result array holds next greater or -1 if none

Full Transcript

This concept finds the next greater element for each item in an array using a stack. We scan the array from left to right. The stack stores indexes of elements that have not yet found a bigger element to their right. When we find a bigger element, we pop smaller elements from the stack and assign the bigger element as their next greater. We push the current index onto the stack to wait for its next greater. After processing all elements, any indexes left in the stack have no next greater element, so we assign -1 to them. The execution table shows each step's stack, current index, actions, and result array updates. The variable tracker shows how variables change after each step. Key moments clarify why we pop only when current element is bigger, why we push indexes, and why we assign -1 at the end. The visual quiz tests understanding of stack changes, result assignments, and behavior on decreasing arrays.

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