Previous Smaller Element

🎯

Previous Smaller Element

mediumSTACKAmazonGoogle

Imagine you are analyzing stock prices day by day and want to find for each day the last day before it when the stock price was lower, helping you understand recent dips.

💡 This problem asks for the closest smaller element to the left for each element in an array. Beginners often struggle because a naive approach requires nested loops, which is inefficient. Understanding how to use a stack to track candidates efficiently is key to mastering this pattern.

📋

Problem Statement

Given an array of integers, for each element, find the previous element that is smaller than the current element. If no such element exists, output -1 for that position. Return the array of previous smaller elements.

1 ≤ n ≤ 10^5-10^9 ≤ array elements ≤ 10^9

💡

Example

Input"[4, 5, 2, 10, 8]"

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

For 4, no smaller previous element → -1; for 5, previous smaller is 4; for 2, none smaller before it → -1; for 10, previous smaller is 2; for 8, previous smaller is 2.

• All elements equal → all outputs -1
• Strictly increasing array → previous smaller is always the immediate previous element
• Strictly decreasing array → all outputs -1
• Single element array → output -1

⚠️

Common Mistakes

Not popping elements greater or equal to current from stack

Incorrect previous smaller element found or stack grows incorrectly

✅ Ensure while loop pops all elements >= current before pushing current

Pushing values instead of indexes when indexes are needed

Cannot retrieve positions or indices of previous smaller elements

✅ Push indexes onto stack and compare values via arr[stack.top()]

Initializing output array incorrectly or forgetting to fill with -1

Output contains garbage or default zeros instead of -1 for no smaller element

✅ Initialize output array with -1 for all positions before processing

Using a stack that does not maintain strictly increasing order

Stack top may not be the closest smaller element, causing wrong results

✅ Always pop elements from stack while they are >= current element to maintain strict increase

Not handling empty stack case before accessing top element

Runtime error or exception due to accessing empty stack

✅ Check if stack is empty before accessing top element

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by directly checking each element's previous smaller element without any optimization.

Intuition

For each element, scan all previous elements to find the closest smaller one by checking backwards until found or start is reached.

Algorithm

1. Initialize an output array with -1 for all positions.
2. For each element from left to right, scan all previous elements backwards.
3. If a smaller element is found, record it in the output and stop scanning.
4. If none found, output remains -1.

💡 This approach is straightforward but inefficient because it checks many elements repeatedly, which is easy to understand but slow.

</>

Code

def previous_smaller_element(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

# Driver code
if __name__ == '__main__':
    arr = [4, 5, 2, 10, 8]
    print(previous_smaller_element(arr))

Line Notes

n = len(arr)Determine the size of the input array for iteration limits

result = [-1] * nInitialize output with -1 assuming no smaller previous element by default

for i in range(n)Iterate over each element to find its previous smaller element

for j in range(i - 1, -1, -1)Scan backwards from current element to find the closest smaller element

if arr[j] < arr[i]Check if the candidate element is smaller than current

result[i] = arr[j]Record the found smaller element in the result

breakStop scanning once the closest smaller element is found

import java.util.*;
public class PreviousSmallerElement {
    public static int[] previousSmaller(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;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10, 8};
        System.out.println(Arrays.toString(previousSmaller(arr)));
    }
}

Line Notes

int n = arr.length;Get the length of the input array for iteration

int[] result = new int[n];Create output array to store previous smaller elements

Arrays.fill(result, -1);Initialize all outputs to -1 assuming no smaller element found

for (int i = 0; i < n; i++)Iterate over each element to find previous smaller

for (int j = i - 1; j >= 0; j--)Scan backwards from current index to find smaller element

if (arr[j] < arr[i])Check if candidate element is smaller

result[i] = arr[j];Assign found smaller element to result

break;Stop scanning once closest smaller element is found

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

vector<int> previousSmallerElement(const 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;
}

int main() {
    vector<int> arr = {4, 5, 2, 10, 8};
    vector<int> res = previousSmallerElement(arr);
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Line Notes

int n = arr.size();Get the number of elements in input vector

vector<int> result(n, -1);Initialize result vector with -1 for no smaller element

for (int i = 0; i < n; i++)Loop over each element to find previous smaller

for (int j = i - 1; j >= 0; j--)Scan backwards to find closest smaller element

if (arr[j] < arr[i])Check if candidate element is smaller

result[i] = arr[j];Store found smaller element in result

break;Stop scanning once closest smaller element is found

function previousSmallerElement(arr) {
    const n = arr.length;
    const result = new Array(n).fill(-1);
    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;
}

// Test
console.log(previousSmallerElement([4, 5, 2, 10, 8]));

Line Notes

const n = arr.length;Determine array length for iteration

const result = new Array(n).fill(-1);Initialize output array with -1

for (let i = 0; i < n; i++)Iterate over each element to find previous smaller

for (let j = i - 1; j >= 0; j--)Scan backwards to find closest smaller element

if (arr[j] < arr[i])Check if candidate element is smaller

result[i] = arr[j];Assign found smaller element to result

break;Stop scanning once closest smaller element is found

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each element, we scan backwards up to all previous elements, leading to a quadratic number of comparisons.

💡 For n=20, this means up to 400 comparisons, which is manageable but grows quickly for larger n.

Interview Verdict: TLE for large inputs

This approach is too slow for large arrays, but it is important to understand the problem and correctness before optimizing.

🧠

Using Stack (Monotonic Increasing Stack)

💡 This approach introduces a stack to efficiently track candidates for previous smaller elements, reducing time complexity drastically.

Intuition

Use a stack to keep elements in increasing order. For each element, pop from the stack until the top is smaller, then that top is the previous smaller element.

Algorithm

1. Initialize an empty stack and an output array.
2. Iterate over each element in the array.
3. While stack is not empty and top of stack is greater or equal to current element, pop from stack.
4. If stack is empty, output -1; else output top of stack.
5. Push current element onto stack.

💡 The stack maintains a strictly increasing sequence of elements, so the top is always the closest smaller element to the left.

</>

Code

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

# Driver code
if __name__ == '__main__':
    arr = [4, 5, 2, 10, 8]
    print(previous_smaller_element(arr))

Line Notes

stack = []Initialize stack to keep track of candidates for previous smaller elements

result = []Initialize output list to store results

for num in arr:Process each element in input array

while stack and stack[-1] >= num:Pop elements from stack that are not smaller than current

stack.pop()Remove elements that can't be previous smaller for current

if stack:If stack not empty, top is previous smaller element

result.append(stack[-1])Append previous smaller element to result

else:If stack empty, no smaller previous element

result.append(-1)Append -1 to result when no smaller element found

stack.append(num)Push current element onto stack for future elements

import java.util.*;
public class PreviousSmallerElement {
    public static int[] previousSmaller(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10, 8};
        System.out.println(Arrays.toString(previousSmaller(arr)));
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Create stack to hold candidates for previous smaller elements

for (int i = 0; i < n; i++)Iterate over each element in array

while (!stack.isEmpty() && stack.peek() >= arr[i])Pop elements from stack that are not smaller than current

stack.pop();Remove elements that can't be previous smaller

result[i] = stack.isEmpty() ? -1 : stack.peek();Assign previous smaller element or -1 if none

stack.push(arr[i]);Push current element onto stack

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

vector<int> previousSmallerElement(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && st.top() >= arr[i]) {
            st.pop();
        }
        result[i] = st.empty() ? -1 : st.top();
        st.push(arr[i]);
    }
    return result;
}

int main() {
    vector<int> arr = {4, 5, 2, 10, 8};
    vector<int> res = previousSmallerElement(arr);
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Line Notes

stack<int> st;Stack to keep track of previous smaller candidates

for (int i = 0; i < n; i++)Iterate over each element

while (!st.empty() && st.top() >= arr[i])Pop elements not smaller than current

st.pop();Remove invalid candidates

result[i] = st.empty() ? -1 : st.top();Assign previous smaller or -1 if none

st.push(arr[i]);Push current element for future comparisons

function previousSmallerElement(arr) {
    const stack = [];
    const result = [];
    for (const num of arr) {
        while (stack.length && stack[stack.length - 1] >= num) {
            stack.pop();
        }
        result.push(stack.length ? stack[stack.length - 1] : -1);
        stack.push(num);
    }
    return result;
}

// Test
console.log(previousSmallerElement([4, 5, 2, 10, 8]));

Line Notes

const stack = [];Initialize stack to hold candidates

const result = [];Initialize result array

for (const num of arr)Iterate over each element

while (stack.length && stack[stack.length - 1] >= num)Pop elements not smaller than current

stack.pop();Remove invalid candidates

result.push(stack.length ? stack[stack.length - 1] : -1);Push previous smaller or -1

stack.push(num);Push current element onto stack

⏱

Complexity

TimeO(n)

SpaceO(n)

Each element is pushed and popped at most once, so total operations are linear in n.

💡 For n=100000, this means roughly 200000 operations, which is efficient for large inputs.

Interview Verdict: Accepted

This is the standard efficient approach for this problem and is expected in interviews.

🧠

Stack with Indexes to Retrieve Positions

💡 Sometimes you need the index of the previous smaller element instead of the value. This approach modifies the stack to store indexes, enabling retrieval of positions.

Intuition

Store indexes in the stack instead of values. Compare current element with element at top index. This allows outputting the index or value as needed.

Algorithm

1. Initialize an empty stack to store indexes and an output array.
2. Iterate over each element by index.
3. While stack not empty and element at top index is greater or equal to current element, pop from stack.
4. If stack empty, output -1; else output element at top index.
5. Push current index onto stack.

💡 Using indexes allows more flexibility and is a common variant in interview problems.

</>

Code

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

# Driver code
if __name__ == '__main__':
    arr = [4, 5, 2, 10, 8]
    print(previous_smaller_element_indexes(arr))

Line Notes

for i, num in enumerate(arr)Iterate with index and value for position tracking

while stack and arr[stack[-1]] >= numCompare current element with element at top index in stack

stack.pop()Remove indexes whose elements are not smaller

if stack:If stack not empty, top index points to previous smaller element

result.append(arr[stack[-1]])Append previous smaller element's value

else:No smaller previous element found

result.append(-1)Append -1 when none found

stack.append(i)Push current index for future comparisons

import java.util.*;
public class PreviousSmallerElement {
    public static int[] previousSmallerIndexes(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : arr[stack.peek()];
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10, 8};
        System.out.println(Arrays.toString(previousSmallerIndexes(arr)));
    }
}

Line Notes

Stack<Integer> stack = new Stack<>();Stack stores indexes to track positions

for (int i = 0; i < n; i++)Iterate over array with index

while (!stack.isEmpty() && arr[stack.peek()] >= arr[i])Pop indexes with elements not smaller than current

stack.pop();Remove invalid candidates

result[i] = stack.isEmpty() ? -1 : arr[stack.peek()];Assign previous smaller element value or -1

stack.push(i);Push current index onto stack

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

vector<int> previousSmallerElementIndexes(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[st.top()] >= arr[i]) {
            st.pop();
        }
        result[i] = st.empty() ? -1 : arr[st.top()];
        st.push(i);
    }
    return result;
}

int main() {
    vector<int> arr = {4, 5, 2, 10, 8};
    vector<int> res = previousSmallerElementIndexes(arr);
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Line Notes

stack<int> st;Stack holds indexes for position tracking

for (int i = 0; i < n; i++)Iterate over elements by index

while (!st.empty() && arr[st.top()] >= arr[i])Pop indexes with elements not smaller

st.pop();Remove invalid candidates

result[i] = st.empty() ? -1 : arr[st.top()];Assign previous smaller element or -1

st.push(i);Push current index onto stack

function previousSmallerElementIndexes(arr) {
    const stack = [];
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        while (stack.length && arr[stack[stack.length - 1]] >= arr[i]) {
            stack.pop();
        }
        result.push(stack.length ? arr[stack[stack.length - 1]] : -1);
        stack.push(i);
    }
    return result;
}

// Test
console.log(previousSmallerElementIndexes([4, 5, 2, 10, 8]));

Line Notes

for (let i = 0; i < arr.length; i++)Iterate over array with index

while (stack.length && arr[stack[stack.length - 1]] >= arr[i])Pop indexes with elements not smaller

stack.pop();Remove invalid candidates

result.push(stack.length ? arr[stack[stack.length - 1]] : -1);Push previous smaller element or -1

stack.push(i);Push current index onto stack

⏱

Complexity

TimeO(n)

SpaceO(n)

Each index is pushed and popped at most once, so total operations are linear.

💡 This approach is as efficient as the previous stack method but adds flexibility for index-based queries.

Interview Verdict: Accepted

This variant is useful when the problem requires indexes or further processing based on positions.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to code the stack-based approach (Approach 2 or 3) as it is efficient and standard. Brute force is useful only to explain the problem.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code for large inputs
2. Stack (Values)	O(n)	O(n)	No	N/A	Code this for value-based previous smaller element
3. Stack (Indexes)	O(n)	O(n)	No	Yes (indexes allow reconstruction)	Code this if indexes or positions are required

💼

Interview Strategy

💡 Use this guide to understand the problem from basics to optimized solutions. Practice explaining brute force first, then the stack approach, and be ready to discuss edge cases and complexity.

How to Present

Clarify the problem and ask about input size and output format.Explain the brute force approach to show understanding.Discuss its inefficiency and motivate the stack approach.Explain the stack-based solution step-by-step.Write clean code and test with sample inputs.Discuss edge cases and possible follow-ups.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 8min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to stack, coding accuracy, and handling of edge cases.

Common Follow-ups

• What if you need the index of the previous smaller element? → Use stack of indexes.
• How to find the next smaller element instead? → Iterate from right to left with similar stack logic.

💡 These follow-ups test your adaptability and understanding of the monotonic stack pattern beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Asked for previous or next smaller/greater element; 2) Need closest element on one side; 3) Input is array or list; 4) Constraints require better than O(n^2).

Signature Phrases

'previous smaller element''closest smaller element to the left''for each element find the last smaller element before it'

NOT This Pattern When

Problems asking for global min/max or unrelated sorting/searching are different patterns.

Similar Problems

Next Greater Element - similar logic but for greater elementsNext Smaller Element - same pattern but looking to the rightLargest Rectangle in Histogram - uses monotonic stack for area calculation

Practice

1. Consider the following Python code implementing a stack using one queue with a costly push operation:

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

stack = MyStack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop())
print(stack.top())

What is the output of the two print statements?

easy

A. 30
10

B. 10
20

C. 30
20

D. 20
10

Solution

1. Step 1: Trace push operations

   Push 10: queue=[10]
   Push 20: queue=[20,10] after rotation
   Push 30: queue=[30,20,10] after rotation

2. Step 2: Trace pop and top

   Pop removes front: 30
   Top returns front: 20

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Rotation puts last pushed element front -> pop returns 30, top returns 20 [OK]

Hint: Rotation after push puts newest element front [OK]

Common Mistakes:

• Not rotating queue correctly, so pop returns oldest element
• Confusing pop and top outputs
• Off-by-one in rotation loop

2. Identify the bug in the following MinStack implementation using a single stack with encoded minimums:

medium

A. Line 'if diff < 0:' in pop should be 'if diff <= 0:' to handle zero differences correctly.

B. Line 'self.stack.append(diff)' should append x instead of diff to store actual values.

C. Line with 'if diff <= 0:' should be 'if diff < 0:' to avoid incorrect min updates on duplicates.

D. Line 'self.minVal = self.minVal - diff' in pop should add diff instead of subtracting.

Solution

1. Step 1: Analyze push condition

   The condition 'if diff <= 0:' updates minVal even when diff == 0, i.e., when new element equals current min.

2. Step 2: Understand impact

   Updating minVal on equal values causes minVal to be overwritten incorrectly, breaking min tracking when duplicates are popped.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct condition is 'diff < 0' to update minVal only on strictly smaller values [OK]

Hint: Only update minVal when new value is strictly less than current min [OK]

Common Mistakes:

• Using <= instead of < causes minVal errors with duplicates
• Incorrect pop minVal update
• Appending wrong values to stack

3. What is the time complexity of the optimized monotonic stack solution for the Next Greater Element I problem, where m = length of nums1 and n = length of nums2?

medium

A. O(m * n) because for each element in nums1, we scan nums2 to find the next greater element.

B. O(n) because only nums2 is processed with a stack; nums1 lookup is constant time.

C. O(n + m) because each element in nums2 is pushed and popped at most once, and mapping results for nums1 is O(m).

D. O(n log n) due to sorting nums2 before processing.

Solution

1. Step 1: Analyze stack operations on nums2

   Each element in nums2 is pushed once and popped at most once, so stack operations are O(n).

2. Step 2: Analyze mapping and lookup for nums1

   Mapping next greater elements for nums1 uses a hashmap and set lookups, each O(1), done m times, total O(m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Combined complexity is O(n + m), not O(m*n) or O(n log n) [OK]

Hint: Stack operations are linear; hashmap lookups are constant [OK]

Common Mistakes:

• Assuming nested loops cause O(m*n) complexity
• Confusing sorting-based approaches with stack-based ones
• Ignoring the cost of hashmap lookups

4. What is the time complexity of the optimal monotonic stack solution that uses an explicit circular array copy (doubling the array) for the Next Greater Element II problem, and why?

medium

A. O(n) because each element is pushed and popped at most once despite doubling

B. O(n²) because the doubled array doubles the iterations

C. O(n log n) due to sorting implicit in stack operations

D. O(2n) which simplifies to O(n) but requires extra space

Solution

1. Step 1: Identify loop iterations

   The loop runs over doubled array of length 2n, so 2n iterations.

2. Step 2: Analyze stack operations

   Each element index is pushed once and popped once at most, so total stack operations are O(n). The doubling does not cause repeated pushes for the same index.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Doubling array length does not multiply complexity beyond linear [OK]

Hint: Each element pushed/popped once -> O(n) despite doubled array [OK]

Common Mistakes:

• Assuming doubling array doubles complexity to O(n²)
• Confusing stack operations with sorting complexity
• Ignoring that indices are pushed only once

5. Suppose you want to extend the circular queue to support a 'peekRear' operation that returns the last inserted element in O(1) time. Which modification to the optimal approach is correct?

hard

A. Return queue[tail] directly, since tail points to the last element inserted.

B. Return queue[(tail - 1 + capacity) % capacity], since tail points to the next insertion position.

C. Return queue[head], because head always points to the rear element.

D. Return queue[size - 1], since size tracks the number of elements.

Solution

1. Step 1: Understand tail pointer semantics

   Tail points to the next insertion index, not the last inserted element.

2. Step 2: Calculate rear element index

   The last inserted element is at (tail - 1 + capacity) modulo capacity to handle wrap-around.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Rear element index is tail - 1 modulo capacity [OK]

Hint: Rear element is at (tail - 1) mod capacity [OK]

Common Mistakes:

• Using tail index directly
• Confusing head with rear
• Using size as index