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.
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:
After performing these steps, the next greater elements for the array will be found.
Input: [4, 5, 2, 25]
Output: [5, 25, 25, -1]
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
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.