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

Next Greater Element Using Stack

📖 Scenario: You have a list of daily temperatures recorded in an array. For each day, you want to find the next day when the temperature will be higher. If there is no future day with a higher temperature, you mark it as -1.This helps you plan your activities by knowing when warmer days are coming.

🎯 Goal: Build a program that finds the next greater temperature for each day using a stack.You will create the temperature list, set up a stack, write the logic to find the next greater element, and print the result.

📋 What You'll Learn

Create an array called temperatures with the exact values: [73, 74, 75, 71, 69, 72, 76, 73]

Create an empty array called stack to hold indices

Create an array called nextGreater of the same length as temperatures, filled with -1

Use a for loop with variable i to iterate over temperatures

Inside the loop, use a while loop to compare current temperature with the temperature at the index on top of the stack

Update nextGreater at the popped index with the current temperature

Push the current index i onto the stack

Print the nextGreater 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 fields where future trends matter.

💼 Career

Understanding stack-based algorithms is important for technical interviews and solving real-world problems efficiently.

1

Create the temperature array

Create an array called temperatures with these exact values: [73, 74, 75, 71, 69, 72, 76, 73]

DSA Typescript

# Your code here

Hint

Use const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];

2

Set up the stack and result array

Create an empty array called stack and an array called nextGreater of the same length as temperatures, filled with -1

DSA Typescript

const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];
# Your code here

Hint

Use const stack: number[] = []; and const nextGreater: number[] = new Array(temperatures.length).fill(-1);

3

Find the next greater element using a stack

Use a for loop with variable i to iterate over temperatures. Inside the loop, use a while loop to compare temperatures[i] with temperatures[stack[stack.length - 1]]. While current temperature is greater, pop from stack and update nextGreater at that index with temperatures[i]. Then push i onto stack.

DSA Typescript

const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];
const stack: number[] = [];
const nextGreater: number[] = new Array(temperatures.length).fill(-1);
# Your code here

Hint

Use a for loop and inside it a while loop to compare and update nextGreater. Push current index i onto stack.

4

Print the next greater temperatures array

Print the nextGreater array using console.log(nextGreater)

DSA Typescript

const temperatures = [73, 74, 75, 71, 69, 72, 76, 73];
const stack: number[] = [];
const nextGreater: number[] = new Array(temperatures.length).fill(-1);

for (let i = 0; i  0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
        const index = stack.pop()!;
        nextGreater[index] = temperatures[i];
    }
    stack.push(i);
}
# Your code here

Hint

Use console.log(nextGreater) to print the result.

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