Next Greater Element Using Stack in DSA Javascript

Mental Model

We want to find the next bigger number for each number in a list by looking ahead efficiently using a stack.

Analogy: Imagine standing in a line of people with different heights. For each person, you want to find the next taller person standing to their right without checking everyone again and again.

Array: [4] [5] [2] [25] [7] [8]
Stack: empty
Result: [ ] [ ] [ ] [ ] [ ] [ ]

Dry Run Walkthrough

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

Goal: Find the next greater element for each number in the array using a stack.

Step 1: Push 4 onto the stack

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

Why: Start with the first element; no previous elements to compare yet.

Step 2: 5 is greater than top of stack (4), pop 0 and set result[0] = 5; push 1

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

Why: 5 is the next greater element for 4, so update result and push 5 for next comparisons.

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

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

Why: 2 is smaller, so it waits for a bigger number to its right.

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

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

Why: 25 is the next greater element for both 2 and 5, so update results and push 25.

Step 5: 7 is not greater than top of stack (25), push 4

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

Why: 7 waits for a bigger number to its right.

Step 6: 8 is greater than top of stack (7), pop 4 and set result[4] = 8; push 5

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

Why: 8 is the next greater element for 7, update result and push 8.

Step 7: End of array reached; pop remaining stack elements (25 and 8) and set their results to -1

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

Why: No greater elements to the right for 25 and 8, so result stays -1.

Result:

Final Result: [5, 25, 25, -1, 8, -1]

Annotated Code

DSA Javascript

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

    for (let i = 0; i < arr.length; i++) {
      // While current element is greater than stack top, update result
      while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
        const index = stack.pop();
        result[index] = arr[i];
      }
      // Push current index for future comparison
      stack.push(i);
    }

    // Remaining elements have no next greater, result already -1
    return result;
  }
}

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

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

Compare current element with top of stack to find next greater.

const index = stack.pop();

Pop index from stack whose next greater is found.

result[index] = arr[i];

Update result for popped index with current element.

stack.push(i);

Push current index to stack for future comparisons.

Output

5, 25, 25, -1, 8, -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 indices and answers.

vs Alternative: Naive approach is O(n^2) by checking each element's next greater by scanning ahead; stack reduces this to O(n).

Edge Cases

Empty array

Returns empty result array without error.

DSA Javascript

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

All elements in descending order

All results remain -1 because no next greater element exists.

DSA Javascript

result = new Array(arr.length).fill(-1);

All elements equal

All results remain -1 because no strictly greater element exists.

DSA Javascript

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

When to Use This Pattern

When you need to find the next bigger number for each element in a list efficiently, use the stack pattern to track candidates and update results in one pass.

Common Mistakes

Mistake: Comparing values directly without storing indices causes incorrect result placement.
Fix: Store indices in the stack to update the correct position in the result array.

Mistake: Not popping all smaller elements from the stack before pushing current element.
Fix: Use a while loop to pop all smaller elements to correctly assign their next greater.

Summary

Finds the next greater element for each item in an array using a stack.

Use when you want to efficiently find the next bigger number to the right for each element.

The key insight is to use a stack to remember indices of elements waiting for their next greater number.

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