Next Greater Element Problem using Stack

Next Greater Element Problem using Stack

The Next Greater Element problem involves finding the next greater element for each element in an array. The next greater element for an element x is the first greater element to the right of x in the array. This can be efficiently solved using a stack.

---

Step-by-Step Process

Consider an array:

[4, 5, 2, 25]

To find the next greater element for each element in the array using a stack, follow these steps:

1. Initialize an Empty Stack: Use a stack to keep track of elements for which the next greater element has not been found yet.
2. Traverse the Array: Iterate through each element in the array.
3. Compare with Stack's Top: For each element, compare it with the element at the top of the stack. If the current element is greater, the next greater element for the top element is found. Pop the stack and repeat the comparison until the stack is empty or the current element is not greater.
4. Push Current Element: Push the current element onto the stack.
5. Handle Remaining Elements: After processing all elements, the elements remaining in the stack do not have a next greater element. Set their next greater element to -1 or any other appropriate value.

After performing these steps, the next greater elements for the array will be found.

Input: [4, 5, 2, 25]
Output: [5, 25, 25, -1]

---

Pseudo Code

Function next_greater_element(arr):
    # Initialize an empty stack
    stack = []
    # Initialize a list to store the results
    result = [-1] * len(arr)
    # Traverse the array
    For i in range(len(arr)):
        # Compare with the stack's top element
        While stack and arr[i] > arr[stack[-1]]:
            index = stack.pop()
            result[index] = arr[i]
        # Push the current element's index onto the stack
        stack.append(i)
    # Return the result
    Return result

---

Python Program to Solve the Next Greater Element Problem using Stack

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        return len(self.stack) == 0

    def traverse(self):
        for item in reversed(self.stack):
            print(item, end=" -> ")
        print("None")

# Function to find the next greater element for each element in the array
def next_greater_element(arr):
    stack = Stack()
    result = [-1] * len(arr)
    for i in range(len(arr)):
        while not stack.is_empty() and arr[i] > arr[stack.peek()]:
            index = stack.pop()
            result[index] = arr[i]
        stack.push(i)
    return result

# Example usage:
input_array = [4, 5, 2, 25]
print(f"Input array: {input_array}")  # Output: Input array: [4, 5, 2, 25]
output_array = next_greater_element(input_array)
print(f"Next greater elements: {output_array}")  # Output: Next greater elements: [5, 25, 25, -1]

This Python program defines a stack with methods for pushing, popping, peeking, checking if the stack is empty, and traversing the stack. The next_greater_element function uses the stack to find the next greater element for each element in the input array by processing each element, comparing it with the stack's top element, and updating the result list accordingly.