Next Greater Element Using Stack in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Next Greater Element for a simple array

What is the output of the following TypeScript code that finds the next greater element for each item in the array?

DSA Typescript

function nextGreaterElement(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 - 1]] < arr[i]) {
      const idx = stack.pop()!;
      result[idx] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElement([4, 5, 2, 25]));

A [5, 25, 25, -1]

B [5, 2, 25, -1]

C [25, 25, -1, -1]

D [4, 5, 2, 25]

💡 Hint

Think about how the stack helps track indices waiting for a bigger number.

The code uses a stack to keep indices of elements for which we haven't found a greater element yet. When a bigger element is found, it updates the result for all smaller elements on the stack.

❓ Predict Output

intermediate

Next Greater Element output with repeated elements

What is the output of this TypeScript code for the array with repeated elements?

DSA Typescript

function nextGreaterElement(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 - 1]] < arr[i]) {
      const idx = stack.pop()!;
      result[idx] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElement([2, 2, 1, 3]));

A [3, -1, 3, -1]

B [2, 3, 3, -1]

C [3, 3, 3, -1]

D [2, 2, 3, -1]

💡 Hint

Remember that equal elements do not count as greater.

The next greater element for both 2's and 1 is 3. The last element 3 has no greater element, so -1.

🔧 Debug

advanced

Identify the error in Next Greater Element implementation

What error will this TypeScript code produce when run?

DSA Typescript

function nextGreaterElement(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 - 1]] < arr[i]) {
      const idx = stack.pop()!;
      result[idx] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElement([1, 3, 2]));

A RangeError: Maximum call stack size exceeded

B TypeError: Cannot read property 'length' of undefined

C ReferenceError: i is not defined

D TypeError: Cannot read property 'undefined' of number

💡 Hint

Check the loop boundary and array access.

The loop runs with i <= arr.length, so when i equals arr.length, arr[i] is undefined. Accessing arr[i] causes a TypeError.

🧠 Conceptual

advanced

Time complexity of Next Greater Element using stack

What is the time complexity of the Next Greater Element algorithm using a stack for an array of size n?

A O(1) constant time regardless of input size

B O(n log n) due to sorting inside the algorithm

C O(n^2) because of nested loops

D O(n) because each element is pushed and popped at most once

💡 Hint

Think about how many times each element is processed.

Each element is pushed onto the stack once and popped once, so total operations are proportional to n, making it O(n).

🚀 Application

expert

Next Greater Element for circular array

Given a circular array, where the next element after the last is the first element, what is the output of this TypeScript code?

DSA Typescript

function nextGreaterElementCircular(arr: number[]): number[] {
  const n = arr.length;
  const stack: number[] = [];
  const result: number[] = new Array(n).fill(-1);
  for (let i = 0; i < 2 * n; i++) {
    const current = arr[i % n];
    while (stack.length && arr[stack[stack.length - 1]] < current) {
      const idx = stack.pop()!;
      result[idx] = current;
    }
    if (i < n) stack.push(i);
  }
  return result;
}

console.log(nextGreaterElementCircular([5, 3, 8, -2, 7]));

A [8, 8, 7, 7, 8]

B [8, 8, -1, 7, 8]

C [3, 8, -1, 7, -1]

D [8, 8, 8, 7, -1]

💡 Hint

Remember the array is circular, so elements after the end wrap to the start.

The code checks twice the length to simulate circular behavior. For each element, it finds the next greater element considering wrap-around.

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