Find Next Greater Element using Stack using Visualization

The Next Greater Element problem is a classic problem that involves finding the next larger element for each element in an array. The problem can be defined as:

Problem Statement

Given an array of integers, for each element, find the next greater element to its right. If there isn’t a next greater element, use -1.

Example

Input: [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]

Explanation:

• For the first 2, the next greater element is 4.
• For 1, the next greater element is 2.
• For the second 2, the next greater element is 4.
• For 4, there is no greater element, so the output is -1.
• For 3, there is no greater element, so the output is -1.

Approach: Using a Stack

The most efficient way to solve this problem is by using a stack. This approach works in O(n) time complexity, where n is the size of the array.

Steps:

1. Initialize an empty stack and a result array of the same length as the input array, filled with -1.
2. Traverse the array from right to left.
3. For each element, check if the stack is not empty and the top element of the stack is less than or equal to the current element.
   • If so, pop the stack.
4. If the stack is not empty after the above step, the top element of the stack is the next greater element for the current element.
5. Push the current element onto the stack.
6. Continue until all elements are processed.

Code Implementation

Here is the code implementation of the approach in JavaScript:

function nextGreaterElement(nums) {
  const stack = [];
  const result = new Array(nums.length).fill(-1);

  for (let i = nums.length - 1; i >= 0; i--) {
    while (stack.length > 0 && stack[stack.length - 1] <= nums[i]) {
      stack.pop();
    }

    if (stack.length > 0) {
      result[i] = stack[stack.length - 1];
    }

    stack.push(nums[i]);
  }

  return result;
}

// Example usage:
const nums = [2, 1, 2, 4, 3];
console.log(nextGreaterElement(nums)); // Output: [4, 2, 4, -1, -1]

Visual Walkthrough

Let’s go through each step with a visualization table to better understand the stack operations:

Step	Current Element	Stack (Top -> Bottom)	Action	Result Array
1	3	[3]	Push 3 to the stack	[-1, -1, -1, -1, -1]
2	4	[4]	Pop 3 (since 3 <= 4), push 4 to the stack	[-1, -1, -1, -1, -1]
3	2	[4, 2]	Top is 4 (greater than 2), so set result[2] = 4	[-1, -1, 4, -1, -1]
4	1	[4, 2, 1]	Top is 2 (greater than 1), so set result[1] = 2	[-1, 2, 4, -1, -1]
5	2	[4, 2]	Pop 1 and 2 (since 1, 2 <= 2), top is 4 (greater than 2), set result[0] = 4	[4, 2, 4, -1, -1]

Conclusion

The stack-based solution for the “Next Greater Element” problem is efficient and easy to understand. By visualizing the steps with a diagram, the operations of pushing and popping elements become clearer, helping us understand how the algorithm works.