Next Greater Element Using Stack in DSA Javascript - Build from Scratch

Next Greater Element Using Stack

📖 Scenario: Imagine you have a list of daily temperatures, and you want to find for each day the next day when the temperature will be higher. This helps you plan your activities better.

🎯 Goal: You will build a program that finds the next greater element for each number in a list using a stack. The next greater element is the first number to the right that is bigger than the current number.

📋 What You'll Learn

Create an array called numbers with the values [4, 5, 2, 25]

Create an empty array called stack to help find the next greater elements

Create an array called result of the same length as numbers filled with -1

Use a for loop with variable i to go through numbers

Inside the loop, use a while loop to compare current number with the top of stack

Update result with the next greater element when found

Print the result array at the end

💡 Why This Matters

🌍 Real World

Finding the next greater element is useful in stock price analysis, weather forecasting, and many other areas where you want to know the next time a value increases.

💼 Career

Understanding stack-based algorithms is important for software engineers, especially in roles involving data processing, algorithm design, and coding interviews.

1

Create the initial array

Create an array called numbers with these exact values: [4, 5, 2, 25]

DSA Javascript

// Create the array called numbers with values [4, 5, 2, 25]
// Your code here

Hint

Use const numbers = [4, 5, 2, 25]; to create the array.

2

Set up the stack and result array

Create an empty array called stack and an array called result with the same length as numbers filled with -1

DSA Javascript

const numbers = [4, 5, 2, 25];
// Create an empty array called stack
// Create an array called result with length numbers.length filled with -1
// Your code here

Hint

Use const stack = []; and const result = new Array(numbers.length).fill(-1);.

3

Find the next greater elements using a stack

Use a for loop with variable i from 0 to numbers.length. Inside the loop, use a while loop to check if stack is not empty and numbers[i] is greater than numbers[stack[stack.length - 1]]. If yes, update result[stack.pop()] with numbers[i]. After the while loop, push i into stack.

DSA Javascript

const numbers = [4, 5, 2, 25];
const stack = [];
const result = new Array(numbers.length).fill(-1);
// Use a for loop with i from 0 to numbers.length
// Inside, use a while loop to compare numbers[i] with numbers at index on top of stack
// Update result when next greater element is found
// Push i into stack
// Your code here

Hint

Use a for loop and inside it a while loop to compare and update result. Push the current index i into stack after processing.

4

Print the result array

Print the result array using console.log(result)

DSA Javascript

const numbers = [4, 5, 2, 25];
const stack = [];
const result = new Array(numbers.length).fill(-1);

for (let i = 0; i  0 && numbers[i] > numbers[stack[stack.length - 1]]) {
        const index = stack.pop();
        result[index] = numbers[i];
    }
    stack.push(i);
}
// Print the result array
// Your code here

Hint

Use console.log(result); to print the final array.

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