Next Smaller Element Problem using Stack

Next Smaller Element Problem using Stack

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.

---

Step-by-Step Process

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:

1. Initialize an Empty Stack: Use a stack to keep track of elements for which the next smaller 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 smaller, the next smaller 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 smaller.
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 smaller element. Set their next smaller element to -1 or any other appropriate value.

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]

---

Pseudo Code

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

---

Python Program to Solve the Next Smaller 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 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.