Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Previous Smaller Element

EASYProblemSolveExternal Links

Description

You are given an integer array arr[]. For every element in the array, your task is to determine its Previous Smaller Element (PSE).

The Previous Smaller Element of an element x is the first element that appears to the left of x in the array and is strictly smaller than x.

If no such element exists (either because there are no elements to the left or none of them are smaller), assign -1 as the PSE for that position.

Return an array where the value at each index is the PSE for the corresponding element in the input array.

Examples

Example 1

Input: arr = [1, 6, 2]

Output: [-1, 1, 1]

Explanation:

  • For arr[0] = 1: There are no elements to the left, so PSE = -1.
  • For arr[1] = 6: The only element to the left is 1, and 1 < 6, so PSE = 1.
  • For arr[2] = 2: Elements to the left are [1, 6]. Scanning from right to left: 6 is not smaller than 2, but 1 is smaller than 2. So PSE = 1.

Example 2

Input: arr = [1, 5, 0, 3, 4, 5]

Output: [-1, 1, -1, 0, 3, 4]

Explanation:

  • For arr[0] = 1: No elements to the left. PSE = -1.
  • For arr[1] = 5: Element 1 is to the left and 1 < 5. PSE = 1.
  • For arr[2] = 0: Elements to the left are [1, 5]. Neither 5 nor 1 is smaller than 0. PSE = -1.
  • For arr[3] = 3: Elements to the left include 0, and 0 < 3. PSE = 0 (the nearest smaller one).
  • For arr[4] = 4: The nearest element to the left that is smaller is 3. PSE = 3.
  • For arr[5] = 5: The nearest element to the left that is smaller is 4. PSE = 4.

Example 3

Input: arr = [4, 5, 2, 10, 8]

Output: [-1, 4, -1, 2, 2]

Explanation:

  • For arr[0] = 4: No left elements. PSE = -1.
  • For arr[1] = 5: 4 < 5. PSE = 4.
  • For arr[2] = 2: Both 5 and 4 are not smaller than 2. PSE = -1.
  • For arr[3] = 10: Nearest smaller to the left is 2. PSE = 2.
  • For arr[4] = 8: Nearest smaller to the left is 2 (skipping 10 since 10 ≥ 8). PSE = 2.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^5

Editorial

Brute Force

Intuition

Imagine you are standing in a line of people of different heights, and each person wants to know who is the nearest shorter person standing behind them (to their left). The simplest strategy is for each person to turn around and scan backward, person by person, until they find someone shorter. If they reach the front of the line without finding anyone shorter, the answer is -1.

Similarly, for each element in the array, we look at all previous elements from right to left — starting from the element immediately to the left and moving further back. The first one we find that is strictly smaller is the Previous Smaller Element. If no element satisfies the condition, we record -1.

This brute force approach checks every possible candidate for every element, making it straightforward to understand but potentially slow for large arrays.

Step-by-Step Explanation

Let's trace through with arr = [1, 6, 2]:

Step 1: Process arr[0] = 1.

  • Index 0 has no elements to its left.
  • PSE = -1.
  • result = [-1, ?, ?]

Step 2: Process arr[1] = 6. Start scanning left from j = 0.

  • Check arr[0] = 1. Is 1 < 6? YES.
  • Found PSE = 1 immediately.
  • result = [-1, 1, ?]

Step 3: Process arr[2] = 2. Start scanning left from j = 1.

  • Check arr[1] = 6. Is 6 < 2? NO (6 ≥ 2). Continue scanning.
  • Check arr[0] = 1. Is 1 < 2? YES.
  • Found PSE = 1 after checking 2 elements.
  • result = [-1, 1, 1]

Result: [-1, 1, 1]

Notice that for arr[2] = 2, we had to skip over 6 because it was not smaller. In the worst case (a strictly decreasing array), every element would need to scan all previous elements.

Brute Force — Scanning Left for Each Element — Watch how each element scans backward through all previous elements to find the first one that is strictly smaller. The result array fills in as PSEs are found.

Algorithm

  1. Create a result array of size n, initialized with -1 for all positions.
  2. For each index i from 0 to n-1:
    • For each index j from i-1 down to 0:
      • If arr[j] < arr[i], set result[i] = arr[j] and break the inner loop.
  3. Return the result array.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> prevSmaller(vector<int>& arr) {
        int n = arr.size();
        vector<int> result(n, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i]) {
                    result[i] = arr[j];
                    break;
                }
            }
        }
        
        return result;
    }
};
class Solution:
    def prevSmaller(self, arr):
        n = len(arr)
        result = [-1] * n
        
        for i in range(n):
            for j in range(i - 1, -1, -1):
                if arr[j] < arr[i]:
                    result[i] = arr[j]
                    break
        
        return result
import java.util.Arrays;

class Solution {
    public int[] prevSmaller(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i]) {
                    result[i] = arr[j];
                    break;
                }
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n elements, the inner loop may scan up to i previous elements. In the worst case (a strictly decreasing array like [5, 4, 3, 2, 1]), every element scans all previous elements without finding a smaller one. Total comparisons: 0 + 1 + 2 + ... + (n-1) = n*(n-1)/2, which is O(n²).

Space Complexity: O(1)

We only use a few loop variables (i, j) beyond the output array. The result array is required for the output and does not count as extra auxiliary space. No additional data structures are used.

Why This Approach Is Not Efficient

The brute force approach uses nested loops, giving O(n²) time complexity. With n up to 10^5, this means up to approximately 5 × 10^9 comparisons in the worst case — far too slow for typical time limits of 1-2 seconds.

The fundamental problem is redundant re-examination. When scanning leftward for arr[2] = 2 in our example, we checked arr[1] = 6 and found it wasn't smaller, then checked arr[0] = 1. But consider: element 6 can never be the PSE for any future element that is ≤ 6, because any such element would skip 6 and look further left. We are wasting time re-checking elements that have already been made irrelevant by closer, smaller values.

Key insight: If we could maintain only the "useful" candidates — elements that might still serve as someone's PSE — we could skip over irrelevant ones instantly. A stack provides exactly this capability. By keeping elements in increasing order on the stack, the top always represents the nearest smaller candidate. When a new element arrives, we discard (pop) all candidates that are no longer useful (those ≥ the new element), reducing the total work across all elements to O(n).

Optimal Approach - Monotonic Stack

Intuition

The brute force re-examines elements that have already been determined useless. Consider this scenario: if we encounter element 0 after having seen elements 5 and 1, both 5 and 1 are now irrelevant for any future element. Why? Because 0 is smaller than both AND is closer to any future element. Any future element that needs a previous smaller element will either find 0 sufficient, or needs something even smaller than 0 — which would be even further to the left.

This insight leads to a monotonic stack approach. We maintain a stack of candidate elements in increasing order from bottom to top:

  1. Pop all elements from the stack that are ≥ the current element — they can never be anyone's PSE anymore because the current element is smaller and closer.
  2. If the stack is not empty, the top is the PSE — it is the nearest element to the left that is still smaller.
  3. If the stack is empty, no previous smaller element exists — PSE = -1.
  4. Push the current element onto the stack — it becomes a candidate for future elements.

The stack always maintains an increasing order from bottom to top. This is called a monotonically increasing stack. Because each element is pushed and popped at most once across the entire traversal, the total work is O(n) — a dramatic improvement from O(n²).

Step-by-Step Explanation

Let's trace through with arr = [1, 5, 0, 3, 4, 5] using a monotonic stack:

Step 1: Process arr[0] = 1.

  • Stack is empty → no previous smaller element exists.
  • PSE = -1.
  • Push 1 onto stack. Stack: [1]
  • result = [-1]

Step 2: Process arr[1] = 5.

  • Stack top = 1. Is 1 < 5? Yes → PSE = 1.
  • Push 5 onto stack. Stack: [1, 5]
  • result = [-1, 1]

Step 3: Process arr[2] = 0.

  • Stack top = 5. Is 5 ≥ 0? Yes → pop 5. (5 is no longer useful — 0 is smaller and closer.)
  • Stack top = 1. Is 1 ≥ 0? Yes → pop 1. (Same reasoning — 1 is also now irrelevant.)
  • Stack is empty → PSE = -1.
  • Push 0 onto stack. Stack: [0]
  • result = [-1, 1, -1]

Step 4: Process arr[3] = 3.

  • Stack top = 0. Is 0 < 3? Yes → PSE = 0.
  • Push 3 onto stack. Stack: [0, 3]
  • result = [-1, 1, -1, 0]

Step 5: Process arr[4] = 4.

  • Stack top = 3. Is 3 < 4? Yes → PSE = 3.
  • Push 4 onto stack. Stack: [0, 3, 4]
  • result = [-1, 1, -1, 0, 3]

Step 6: Process arr[5] = 5.

  • Stack top = 4. Is 4 < 5? Yes → PSE = 4.
  • Push 5 onto stack. Stack: [0, 3, 4, 5]
  • result = [-1, 1, -1, 0, 3, 4]

Result: [-1, 1, -1, 0, 3, 4]

Notice how at Step 3, elements 5 and 1 were popped because they could never be the PSE for any future element — 0 is smaller and closer. The stack always maintains increasing order, ensuring the top is always the nearest smaller candidate. Each element is pushed once and popped at most once, giving O(n) total operations.

Monotonic Stack — Finding Previous Smaller Elements in O(n) — Watch how the monotonic stack maintains only useful candidates in increasing order. Elements that can never be a PSE for future elements are popped immediately, avoiding redundant comparisons.

Algorithm

  1. Create an empty stack and a result array of size n.
  2. For each index i from 0 to n-1:
    • While the stack is not empty AND the top of the stack is ≥ arr[i]:
      • Pop from the stack (this element can no longer be a PSE for anyone).
    • If the stack is not empty: result[i] = stack top (the nearest smaller element).
    • If the stack is empty: result[i] = -1 (no previous smaller element exists).
    • Push arr[i] onto the stack.
  3. Return the result array.

Code

#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> prevSmaller(vector<int>& arr) {
        int n = arr.size();
        vector<int> result(n);
        stack<int> st;
        
        for (int i = 0; i < n; i++) {
            // Pop elements that are >= current element
            while (!st.empty() && st.top() >= arr[i]) {
                st.pop();
            }
            
            // If stack is not empty, top is the PSE
            result[i] = st.empty() ? -1 : st.top();
            
            // Push current element as a candidate for future elements
            st.push(arr[i]);
        }
        
        return result;
    }
};
class Solution:
    def prevSmaller(self, arr):
        n = len(arr)
        result = [0] * n
        stack = []
        
        for i in range(n):
            # Pop elements that are >= current element
            while stack and stack[-1] >= arr[i]:
                stack.pop()
            
            # If stack is not empty, top is the PSE
            result[i] = stack[-1] if stack else -1
            
            # Push current element as a candidate
            stack.append(arr[i])
        
        return result
import java.util.Stack;

class Solution {
    public int[] prevSmaller(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            // Pop elements that are >= current element
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            
            // If stack is not empty, top is the PSE
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            
            // Push current element as a candidate
            stack.push(arr[i]);
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there is a while loop inside the for loop, the total number of push and pop operations across the entire traversal is bounded by 2n. Each of the n elements is pushed onto the stack exactly once and popped at most once. Therefore, the amortized cost per element is O(1), and the total time is O(n).

Space Complexity: O(n)

In the worst case (a strictly increasing array like [1, 2, 3, 4, 5]), no elements are ever popped, and all n elements remain on the stack simultaneously. The stack therefore uses O(n) extra space.