Next Greater Element Using Stack and Queue: Efficient Algorithm Explained

The Next Greater Element (NGE) problem is a fundamental data structures and algorithms problem that frequently appears in coding interviews, competitive programming, and real-world applications.

The problem statement is simple:

Given an array, find the Next Greater Element (NGE) for every element. The Next Greater Element for an element x is the first greater element to its right in the array. If there is no greater element, return -1.

To solve this problem efficiently, we use Stack and Queue, two essential data structures that help optimize time complexity.

What is the Next Greater Element?

Given an array arr[], the Next Greater Element (NGE) for each element is the first greater number appearing to its right.

Example of Next Greater Element

Input Array	Next Greater Element Array
[4, 5, 2, 10]	[5, 10, 10, -1]
[3, 8, 4, 1]	[8, -1, -1, -1]

Brute Force Approach (O(n²))

A naive approach would be to use two nested loops, iterating over the array and checking for the next greater element. However, this results in O(n²) time complexity, which is inefficient for large inputs.

To optimize the solution, we use Stack and Queue.

Also Read: How to Work with Virtual Environments in Python

Efficient Algorithm Using Stack

A stack is used to efficiently track elements and find the Next Greater Element in O(n) time complexity.

Algorithm Using Stack

1. Traverse the array from right to left.
2. Use a stack to keep track of the next greater elements.
3. If the stack is empty, there is no greater element, so store -1.
4. While elements in the stack are smaller than the current element, pop them.
5. The top of the stack after popping is the Next Greater Element.
6. Push the current element onto the stack.

Python Implementation Using Stack

def next_greater_element(arr):
    stack = []
    result = [-1] * len(arr)

    for i in range(len(arr) - 1, -1, -1):
        while stack and stack[-1] <= arr[i]:
            stack.pop()

        if stack:
            result[i] = stack[-1]

        stack.append(arr[i])

    return result

# Example Usage
arr = [4, 5, 2, 10]
print(next_greater_element(arr))  # Output: [5, 10, 10, -1]

🔹 Time Complexity: O(n) (Each element is pushed and popped once)
🔹 Space Complexity: O(n) (For the stack)

Also Read: What Are Python’s Built-in Data Types? A Comprehensive Guide

Efficient Algorithm Using Queue

While a stack provides the best solution, we can also use a monotonic queue to find the Next Greater Element in O(n) time.

Algorithm Using Queue

1. Traverse the array from left to right.
2. Use a deque (double-ended queue) to keep track of elements in decreasing order.
3. Remove elements from the queue smaller than the current element.
4. The front of the queue holds the Next Greater Element.
5. Add the current element to the queue.

Python Implementation Using Queue

from collections import deque

def next_greater_element_queue(arr):
    queue = deque()
    result = [-1] * len(arr)

    for i in range(len(arr)):
        while queue and queue[-1] <= arr[i]:
            queue.pop()

        if queue:
            result[i] = queue[-1]

        queue.append(arr[i])

    return result

# Example Usage
arr = [4, 5, 2, 10]
print(next_greater_element_queue(arr))  # Output: [5, 10, 10, -1]

🔹 Time Complexity: O(n)
🔹 Space Complexity: O(n)

Comparison: Stack vs Queue for Next Greater Element

Feature	Stack Approach	Queue Approach
Data Structure Used	Stack	Monotonic Queue
Time Complexity	O(n)	O(n)
Space Complexity	O(n)	O(n)
Best For	Sequential Processing	Real-time Data Processing

A stack-based approach is more efficient and widely used for this problem.

Also Read: How to optimize performance of Python code?

Real-World Applications of Next Greater Element

✅ Stock Price Prediction – Identify when a stock price will rise in the future.
✅ Temperature Analysis – Find the next warmer day in a dataset.
✅ Traffic Management – Predict the next peak in traffic flow.
✅ Competitive Programming – Frequently asked in coding interviews.
✅ AI and Data Science – Used in sequence analysis and forecasting.

Common Mistakes and How to Avoid Them

❌ Using nested loops (O(n²)) instead of a stack (O(n)) – Always optimize using data structures.
❌ Not handling the case where no greater element exists – Ensure -1 is stored properly.
❌ Forgetting to pop smaller elements from the stack – Always maintain a valid stack state.
❌ Using the wrong order of traversal – Right to Left is required for stacks.

FAQs

Conclusion

The Next Greater Element problem is a crucial data structures problem frequently asked in coding interviews. Using Stack and Queue, we can optimize the solution to run in O(n) time complexity.

🚀 Key Takeaways:
✅ Use Stack for the most efficient O(n) solution.
✅ Queue can be used for real-time applications.
✅ Mastering this concept helps in competitive programming.
✅ Real-world applications in stock analysis, AI, and forecasting.

Start practicing today and master Next Greater Element efficiently!