Previous Smaller Element

Last Updated : 12 Sep, 2025

Given an array arr[], find the Previous Smaller Element (PSE) for every element in the array.

  • The Previous Smaller Element of an element x is defined as the first element to its left in the array that is smaller than x.
  • If no such element exists for a particular position, the PSE should be considered as -1.

 Examples: 

Input: arr[] = [1, 6, 2]
Output: [-1, 1, 1]
Explanation: For the first element 1, there is no element to its left, so the result is -1. For 6, the previous smaller element is 1. For 2, the previous smaller element is also 1, since it is the closest smaller number when looking left.

Input: arr[] = [1, 5, 0, 3, 4, 5]
Output: [-1, 1, -1, 0, 3, 4]
Explanation:
For 1, no element on the left → -1
For 5, the previous smaller element is 1
For 0, no smaller element on the left → -1
For 3, the previous smaller element is 0
For 4, the previous smaller element is 3
For the last 5, the previous smaller element is 4

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Using Nested Loops - O(n2) Time and O(1) Space

The idea is to use two loops: for each element, check the elements on its left to find the previous smaller one. If none exists, store -1.

C++ 
#include <iostream>
#include <vector>
using namespace std;

vector<int> prevSmaller(vector<int>& arr){
    int n = arr.size();
    vector<int> result(n, -1);

    // for each element, check all elements 
    // on the left
    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;
}

int main() {
    vector<int> arr = {1, 5, 0, 3, 4, 5};
    vector<int> ans = prevSmaller(arr);

    for (int x : ans) cout << x << " ";
    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>

int* prevSmaller(int arr[], int n) {
    
    // allocate memory for result array
    int* result = (int*)malloc(n * sizeof(int));

    // initialize all PSEs as -1
    for (int i = 0; i < n; i++) result[i] = -1;

    for (int i = 0; i < n; i++) {
       
        // check all elements on the left
        for (int j = i - 1; j >= 0; j--) {
            if (arr[j] < arr[i]) {
                
                // first smaller element on the left
                result[i] = arr[j];
                break;
            }
        }
    }
    return result;
}

int main() {
    int arr[] = {1, 5, 0, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int* result = prevSmaller(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}
Java 
import java.util.ArrayList;

class GfG {
    static ArrayList<Integer> prevSmaller(int arr[]) {
        int n = arr.length;
        ArrayList<Integer> result = new ArrayList<>();

        // initialize all as -1
        for (int i = 0; i < n; i++) result.add(-1);

        // for each element, check all elements 
        // on the left
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i]) {
                    result.set(i, arr[j]);
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int arr[] = {1, 5, 0, 3, 4, 5};
        ArrayList<Integer> ans = prevSmaller(arr);

        for (int x : ans) System.out.print(x + " ");
    }
}
Python 
def prevSmaller(arr):
    n = len(arr)
    result = [-1] * n

    # for each element, check all elements 
    # on the left
    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
    
if __name__ == "__main__":
    arr = [1, 5, 0, 3, 4, 5]
    ans = prevSmaller(arr)

    for x in ans:
        print(x, end=" ")
C# 
using System;
using System.Collections.Generic;

class GfG {
    static List<int> prevSmaller(int[] arr) {
        int n = arr.Length;
        List<int> result = new List<int>(new int[n]);

        // initialize all as -1
        for (int i = 0; i < n; i++) result[i] = -1;

        // for each element, check all elements 
        // on the left
        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;
    }

    public static void Main() {
        int[] arr = {1, 5, 0, 3, 4, 5};
        List<int> ans = prevSmaller(arr);

        foreach (int x in ans) Console.Write(x + " ");
    }
}
JavaScript 
function prevSmaller(arr) {
    let n = arr.length;
    let result = new Array(n).fill(-1);

    // for each element, check all elements 
    // on the left
    for (let i = 0; i < n; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (arr[j] < arr[i]) {
                result[i] = arr[j];
                break;
            }
        }
    }
    return result;
}

// Driver Code
let arr = [1, 5, 0, 3, 4, 5];
let ans = prevSmaller(arr);
console.log(ans.join(" "));

Output
-1 1 -1 0 3 4

[Expected Approach] Using Monotonic stack - O(n) Time and O(n) Space

The idea is to use a monotonic increasing stack. We traverse the array from left to right. For each element, we pop elements from the stack that are greater than or equal to it, since they cannot be the previous smaller element. If the stack is not empty, the top of the stack is the previous smaller element. Finally, we push the current element onto the stack.

C++ 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> prevSmaller(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);

    stack<int> st;

    for (int i = 0; i < n; i++) {
     
        // pop elements from stack until a smaller 
        // element is found or stack becomes empty
        while (!st.empty() && st.top() >= arr[i]) {
            st.pop();
        }

        // if stack is not empty, top is nearest smaller
        if (!st.empty()) {
            result[i] = st.top();
        }

        // push current element to stack
        st.push(arr[i]);
    }
    return result;
}

int main() {
    vector<int> arr = {1, 5, 0, 3, 4, 5};
    vector<int> ans = prevSmaller(arr);

    for (int x : ans) cout << x << " ";
    return 0;
}
C 
#include <stdio.h>
#include <stdlib.h>

int* prevSmaller(int arr[], int n) {
   
    int* result = (int*)malloc(n * sizeof(int));

    // stack to keep track of elements
    int* st = (int*)malloc(n * sizeof(int));
    int top = -1;

    // initialize all PSEs as -1
    for (int i = 0; i < n; i++) {
        result[i] = -1;
    }

    for (int i = 0; i < n; i++) {
        
        // pop elements from stack which are >= current element
        while (top >= 0 && st[top] >= arr[i]) {
            top--;
        }

        // if stack is not empty, top element is PSE
        if (top >= 0) {
            result[i] = st[top];
        }

        // push current element onto stack
        st[++top] = arr[i];
    }

    return result;
}

int main() {
    int arr[] = {1, 5, 0, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int* result = prevSmaller(arr, n);

    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    return 0;
}
Java 
import java.util.ArrayList;
import java.util.Stack;

class GfG {
    static ArrayList<Integer> prevSmaller(int arr[]) {
        int n = arr.length;
        ArrayList<Integer> result = new ArrayList<>();

        // initialize all as -1
        for (int i = 0; i < n; i++) result.add(-1);

        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < n; i++) {
        
            // pop elements from stack until a smaller 
            // element is found or stack becomes empty
            while (!st.isEmpty() && st.peek() >= arr[i]) {
                st.pop();
            }

            // if stack is not empty, top is nearest smaller
            if (!st.isEmpty()) {
                result.set(i, st.peek());
            }

            // push current element to stack
            st.push(arr[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int arr[] = {1, 5, 0, 3, 4, 5};
        ArrayList<Integer> ans = prevSmaller(arr);

        for (int x : ans) System.out.print(x + " ");
    }
}
Python 
def prevSmaller(arr):
    n = len(arr)
    result = [-1] * n

    # stack to keep track of elements
    st = []

    for i in range(n):
      
        # pop elements from stack until a smaller 
        # element is found or stack becomes empty
        while st and st[-1] >= arr[i]:
            st.pop()

        # if stack is not empty, top is nearest smaller
        if st:
            result[i] = st[-1]

        # push current element to stack
        st.append(arr[i])

    return result

if __name__ == "__main__":
    arr = [1, 5, 0, 3, 4, 5]
    ans = prevSmaller(arr)

    for x in ans:
        print(x, end=" ")
C# 
using System;
using System.Collections.Generic;

class GfG {
    static List<int> prevSmaller(int[] arr) {
        int n = arr.Length;
        List<int> result = new List<int>(new int[n]);

        // initialize all as -1
        for (int i = 0; i < n; i++) result[i] = -1;

        Stack<int> st = new Stack<int>();

        for (int i = 0; i < n; i++) {
            
            // pop elements from stack until a smaller 
            // element is found or stack becomes empty
            while (st.Count > 0 && st.Peek() >= arr[i]) {
                st.Pop();
            }

            // if stack is not empty, top is nearest smaller
            if (st.Count > 0) {
                result[i] = st.Peek();
            }

            // push current element to stack
            st.Push(arr[i]);
        }
        return result;
    }

    public static void Main() {
        int[] arr = {1, 5, 0, 3, 4, 5};
        List<int> ans = prevSmaller(arr);

        foreach (int x in ans) Console.Write(x + " ");
    }
}
JavaScript 
function prevSmaller(arr) {
    let n = arr.length;
    let result = new Array(n).fill(-1);

    // stack to keep track of elements
    let st = [];

    for (let i = 0; i < n; i++) {
        
        // pop elements from stack until a smaller 
        // element is found or stack becomes empty
        while (st.length > 0 && st[st.length - 1] >= arr[i]) {
            st.pop();
        }

        // if stack is not empty, top is nearest smaller
        if (st.length > 0) {
            result[i] = st[st.length - 1];
        }

        // push current element to stack
        st.push(arr[i]);
    }
    return result;
}

// Driver Code
let arr = [1, 5, 0, 3, 4, 5];
let ans = prevSmaller(arr);
console.log(ans.join(" "));

Output
-1 1 -1 0 3 4
Comment
Article Tags:
Stack
Searching
DSA
Arrays
+1 More

Explore