How to Find Previous Smaller Element Using Stack and Queue Efficiently

Finding the Previous Smaller Element (PSE) for each element in an array is a fundamental problem in data structures and algorithms. It has applications in monotonic stacks, histogram problems, and stock span problems.

In this guide, we will explore how to find the Previous Smaller Element using Stack and Queue efficiently, discuss different approaches, and analyze their time complexities. By the end, you will have a clear understanding of how to implement these solutions in various programming languages.

Understanding the Previous Smaller Element Problem

The Previous Smaller Element (PSE) for an element in an array is the closest element on the left that is smaller than the current element.

Example

Consider the array:
arr = [4, 10, 5, 8, 20, 15, 3, 12]

The Previous Smaller Element array will be:
[-1, 4, 4, 5, 8, 8, -1, 3]

Explanation:

• The first element 4 has no previous smaller element, so we store -1.
• 10 → previous smaller is 4.
• 5 → previous smaller is 4.
• 8 → previous smaller is 5, and so on.

Also Read: What is the Difference Between Deep Copy and Shallow Copy in Python?

Why Use Stack and Queue?

Both Stack and Queue help optimize this problem:

• Stack (Monotonic Stack Approach) reduces the time complexity to O(n).
• Queue (Sliding Window Approach) can be used for related problems.

Brute Force Approach: O(n²) Time Complexity

A simple approach is to use nested loops:

Algorithm

1. Iterate through the array.
2. For each element, check previous elements one by one.
3. Store the first smaller element found.

Implementation (Python)

def previous_smaller_element(arr):
    result = []
    for i in range(len(arr)):
        found = -1
        for j in range(i - 1, -1, -1):
            if arr[j] < arr[i]:
                found = arr[j]
                break
        result.append(found)
    return result

arr = [4, 10, 5, 8, 20, 15, 3, 12]
print(previous_smaller_element(arr))  

Output: [-1, 4, 4, 5, 8, 8, -1, 3]

Drawback: This method takes O(n²) time, making it inefficient for large inputs.

Also Read: How Do You Handle Exceptions in Python?

Optimized Approach Using Stack: O(n) Time Complexity

A monotonic decreasing stack allows us to find the Previous Smaller Element in O(n) time.

Algorithm

1. Initialize an empty stack.
2. Traverse the array from left to right.
3. Pop elements from the stack if they are greater than or equal to the current element.
4. The top of the stack is the previous smaller element.
5. Push the current element onto the stack.

Implementation (Python – Stack Approach)

def previous_smaller_element_stack(arr):
    stack = []
    result = []

    for num in arr:
        while stack and stack[-1] >= num:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(num)
    
    return result

arr = [4, 10, 5, 8, 20, 15, 3, 12]
print(previous_smaller_element_stack(arr))

Output: [-1, 4, 4, 5, 8, 8, -1, 3]

Time Complexity Analysis

• Each element is pushed onto the stack once and popped at most once.
• Overall complexity = O(n).
• Space complexity = O(n) (in the worst case).

Also Read: Python List Comprehensions: How to Use Them for Efficient Coding

Using Queue for Related Problems

Although Queue is not the most efficient for this problem, it can be useful for sliding window problems where previous elements need to be tracked.

Implementation (Python – Queue Approach)

from collections import deque

def previous_smaller_element_queue(arr):
    queue = deque()
    result = []

    for num in arr:
        while queue and queue[-1] >= num:
            queue.pop()
        result.append(queue[-1] if queue else -1)
        queue.append(num)

    return result

arr = [4, 10, 5, 8, 20, 15, 3, 12]
print(previous_smaller_element_queue(arr))

Time Complexity: Still O(n), but Stack is preferred due to simpler operations.

Comparing Approaches

Approach	Time Complexity	Space Complexity	Efficiency
Brute Force	O(n²)	O(1)	Inefficient
Stack	O(n)	O(n)	Best Approach
Queue	O(n)	O(n)	Alternative

---

Applications of Previous Smaller Element

• Stock Span Problem – Finding stock prices that are lower before a given day.
• Next Smaller Element Problem – A variation where we look forward instead of backward.
• Histogram Largest Rectangle – Used in solving area problems in histograms.
• Spans and Ranges in Arrays – Finding temperature drops, financial trends, etc.

Frequently Asked Questions

What is the Previous Smaller Element problem?
It involves finding the closest smaller element to the left of each element in an array.

Why is Stack preferred for this problem?
A monotonic decreasing stack allows for an O(n) solution by efficiently tracking smaller elements.

Can Queue solve this problem?
Yes, but Queue operations are less efficient for this specific problem compared to Stack.

What is the best time complexity for solving the Previous Smaller Element problem?
The best achievable time complexity is O(n) using a stack.

What are some real-world applications of this problem?
It is used in stock price analysis, temperature trends, and histogram area calculations.

Can this approach be used for Next Smaller Element?
Yes! The logic remains similar, but we traverse the array from right to left.

Conclusion

Finding the Previous Smaller Element efficiently is crucial in array and stack-based problems. The brute force approach is slow, while the stack-based solution optimizes it to O(n). Queue provides an alternative, but Stack is the preferred method.

By understanding and implementing these techniques, you can solve complex coding problems efficiently. Happy coding! 🚀