Previous Smaller Element | Stack and Queue

This chapter explores how to efficiently find the Previous Smaller Element (PSE)—also commonly referred to as the Nearest Smaller Element on the left—for every element in an array. Building directly on top of the "Next Greater Element" pattern, this lesson demonstrates how to leverage a monotonic stack to optimize a brute-force $O(N^2)$ algorithm down to an optimal linear $O(N)$ solution.

1. Problem Statement & Definition

Given an array of integers, our objective is to find the nearest smaller element on the left for each element in the array.

• If an element has no smaller element to its left, we record -1 for that position.
• We must return a new array or list containing these answers without modifying the original input array.

Example Walkthrough

Consider the input array: [4, 5, 2, 2, 8]

• For 4: Looking to the left, there are no elements. Answer = -1.
• For 5: Looking to the left, the closest smaller element is 4. Answer = 4.
• For 2: Looking to the left, no element is strictly smaller than 2. Answer = -1.
• For 2 (fourth element): Looking to the left, the closest smaller element is 2 (the third element). Answer = 2.
• For 8: Looking to the left, we scan 2, 2, 5, 4. The nearest smaller element is 2. Answer = 2.

Resulting NSE array: [-1, 4, -1, 2, 2]

2. The Naive Brute-Force Approach

The most intuitive way to solve this problem is to check every element by scanning backward toward the beginning of the array.

Naive Algorithm Logic

1. Create a result array (or list) of size N.
2. Iterate through each element at index i from 0 to N - 1.
3. Run a nested loop backward from i - 1 down to 0.
4. The first element encountered that is strictly smaller than arr[i] is recorded as the answer, and we immediately break the inner loop.
5. If the inner loop finishes without finding a smaller element, store -1.

Complexity Analysis

• Time Complexity: $O(N^2)$ in the worst-case scenario (e.g., a strictly increasing array where every element must scan all previous elements).
• Space Complexity: $O(N)$ auxiliary space dedicated exclusively to storing the output result array.

3. Recognizing the Need for Optimization

In an interview setting, an $O(N^2)$ solution is typically unacceptable for large constraints ($N \ge 10^5$). Because we need to look backward (to the left) for each element—similar to how we looked forward in Next Greater Element—we can adapt the Monotonic Stack pattern.

Instead of rescanning previous elements repeatedly, we maintain a stack that dynamically tracks potential candidates, discarding elements that are larger and therefore useless for future queries.

4. Core Mental Model: The Increasing Monotonic Stack

To find the previous smaller element on the left, we maintain an increasing monotonic stack.

Real-Life Analogy: The Line of Sight

Imagine standing in a crowd facing a stage, where people are standing in a line. You want to look left to find the first person shorter than you.

• If the person immediately to your left is taller than you, they block your view of anyone shorter standing further back.
• Therefore, you can completely ignore (pop) taller people because they can never be the "nearest smaller" element for you or anyone arriving after you.

Stack Invariant

• The stack stores elements in increasing order from bottom to top (smallest at the bottom, largest at the top).
• When processing an incoming element arr[i], we pop all elements from the stack that are greater than or equal to arr[i], because they are useless.

5. Step-by-Step Dry Run

Let's dry-run the optimized stack approach with the array: [5, 7, 9, 6, 7, 4]

1. Process 5:

   • Stack is empty.
   • Result for 5 is -1.
   • Push 5 onto stack.
   • Stack: [5]

2. Process 7:

   • Stack top is 5, which is smaller than 7. Valid!
   • Result for 7 is 5.
   • Push 7 onto stack.
   • Stack: [5, 7]

3. Process 9:

   • Stack top is 7, which is smaller than 9. Valid!
   • Result for 9 is 7.
   • Push 9 onto stack.
   • Stack: [5, 7, 9]

4. Process 6:

   • Stack top is 9, which is greater than 6. Pop 9.
   • Next stack top is 7, which is greater than 6. Pop 7.
   • Next stack top is 5, which is smaller than 6. Valid!
   • Result for 6 is 5.
   • Push 6 onto stack.
   • Stack: [5, 6]

5. Process 7:

   • Stack top is 6, which is smaller than 7. Valid!
   • Result for 7 is 6.
   • Push 7 onto stack.
   • Stack: [5, 6, 7]

6. Process 4:

   • Stack top 7 > 4 (Pop)
   • Stack top 6 > 4 (Pop)
   • Stack top 5 > 4 (Pop)
   • Stack is now empty.
   • Result for 4 is -1.
   • Push 4 onto stack.
   • Stack: [4]

6. Pseudocode & Implementation Logic

Here is the structured pseudocode implementing the linear-time Previous Smaller Element algorithm:

Function findPreviousSmallerElements(arr):
    n = length of arr
    initialize result list 'nse' of size n
    initialize empty stack 'st'
    
    for i from 0 to n - 1:
        // Pop elements greater than or equal to current element
        while st is not empty and st.top() >= arr[i]:
            st.pop()
        
        // If stack is empty, no smaller element exists on the left
        if st is empty:
            nse[i] = -1
        else:
            nse[i] = st.top()
        
        // Push current element onto stack for future comparisons
        st.push(arr[i])
        
    return nse

7. Complexity Analysis of the Optimized Solution

• Time Complexity: $O(N)$
  • Although there is a while loop inside the main for loop, each element is pushed onto the stack exactly once and popped from the stack at most once across the entire execution of the algorithm. Thus, the amortized time complexity per element is $O(1)$.
• Space Complexity: $O(N)$
  • $O(N)$ space is required for the output result array (nse).
  • $O(N)$ space is required in the worst case for the stack (e.g., when the input array is strictly increasing, every element gets pushed and remains in the stack).

8. Summary and Key Takeaways

• Problem Objective: Find the nearest smaller element located to the left of each index in an array.
• Brute Force Limitation: Comparing every element backwards results in an inefficient $O(N^2)$ time complexity.
• Monotonic Stack Pattern: By maintaining an increasing stack, we can instantly discard elements that are greater than or equal to our current target.
• Direction of Iteration: Because we are searching for previous elements on the left, we iterate through the input array in the forward direction (0 to N - 1).
• Stack Invariant Rule: Pop all elements from the stack that are >= arr[i] before recording the answer.
• Amortized Linear Time: Even with a nested while loop, each element enters and leaves the stack at most once, achieving an optimal $O(N)$ time complexity.
• Space Efficiency: Auxiliary space is bounded by $O(N)$ for both the answer array and the monotonic stack.