The Next Smaller Element problem involves finding the next smaller element for each element in an array. The next smaller element for an element x is the first smaller element to the right of x in the array. This can be efficiently solved using a stack.
Consider an array:
[4, 8, 5, 2, 25]
To find the next smaller element for each element in the array using a stack, follow these steps:
After performing these steps, the next smaller elements for the array will be found.
Input: [4, 8, 5, 2, 25]
Output: [2, 5, 2, -1, -1]
Function next_smaller_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 smaller element for each element in the array
def next_smaller_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, 8, 5, 2, 25]
print(f"Input array: {input_array}") # Output: Input array: [4, 8, 5, 2, 25]
output_array = next_smaller_element(input_array)
print(f"Next smaller elements: {output_array}") # Output: Next smaller elements: [2, 5, 2, -1, -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_smaller_element function uses the stack to find the next smaller 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.