Next Greater Element Using Stack in DSA Javascript - Time & Space Complexity

Time Complexity: Next Greater Element Using Stack

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the next greater element grows as the input list gets bigger.

How does the number of steps change when we use a stack to solve this problem?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function nextGreaterElement(arr) {
  const stack = [];
  const result = new Array(arr.length).fill(-1);
  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[i] > arr[stack[stack.length - 1]]) {
      const index = stack.pop();
      result[index] = arr[i];
    }
    stack.push(i);
  }
  return result;
}
    

This code finds the next greater number for each element in the array using a stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that goes through each element once.
• Secondary operation: The while-loop inside that pops elements from the stack when the current element is greater.
• How many times: Each element is pushed and popped at most once, so the total number of stack operations is at most 2n.

How Execution Grows With Input

As the input size grows, each element is handled a limited number of times.

Input Size (n)	Approx. Operations
10	About 20 stack operations
100	About 200 stack operations
1000	About 2000 stack operations

Pattern observation: The operations grow roughly in a straight line with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Because there is a nested while loop inside the for loop, the time complexity must be O(n²)."

[OK] Correct: Each element is pushed and popped only once, so the total work inside the while loop across all iterations is limited to O(n), not repeated for every element.

Interview Connect

Understanding this pattern helps you solve many problems efficiently using stacks, a skill often valued in interviews.

Self-Check

What if we changed the input to a circular array? How would the time complexity change?

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