Previous Smaller Element

📋

Problem

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.

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

Edge cases: All elements equal → all outputs -1Strictly increasing array → previous smaller is always the immediate previous elementStrictly decreasing array → all outputs -1

</>

IDE

def previous_smaller_element(arr: list[int]) -> list[int]:public int[] previousSmallerElement(int[] arr)vector<int> previousSmallerElement(vector<int> &arr)function previousSmallerElement(arr)

def previous_smaller_element(arr):
    # Write your solution here
    pass

class Solution {
    public int[] previousSmallerElement(int[] arr) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> previousSmallerElement(vector<int> &arr) {
    // Write your solution here
    return {};
}

function previousSmallerElement(arr) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [-1, -1, -1, -1, -1]Not popping elements from stack when they are greater or equal to current element, causing stack top to be incorrect.✅ Pop elements from stack while stack top >= current element before assigning previous smaller.

Wrong: [4, 4, 4, 2, 2]Using immediate previous element without checking if it is smaller, leading to incorrect previous smaller values.✅ Use stack to find the closest previous smaller element, not just immediate previous.

Wrong: [0]For single element input, returning the element itself instead of -1.✅ Return -1 for the first element as no previous smaller exists.

Wrong: TLE or timeoutUsing nested loops (O(n^2)) for large input sizes.✅ Implement monotonic stack approach with O(n) time complexity.

✓

Test Cases

Try to think about how your code handles very small or empty inputs.

Consider tricky input patterns that might break naive stack usage.

Optimize your solution to run in linear time using a monotonic stack.

t1_01basic

Input{"arr":[4,5,2,10,8]}

Expected[-1,4,-1,2,2]

⏱ Performance - must finish in 2000ms

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.

💡 Use a stack to keep track of previous smaller elements.

💡 Pop from the stack while top is greater or equal to current element.

💡 The top of the stack after popping is the previous smaller element or -1 if stack is empty.

Why it failed: Output incorrect because the stack logic is not implemented or incorrect. Fix by popping elements >= current before checking top.

✓ Correctly identifies previous smaller elements using a monotonic increasing stack.

t1_02basic

Input{"arr":[1,3,0,2,5]}

Expected[-1,1,-1,0,2]

⏱ Performance - must finish in 2000ms

For 1 no smaller previous → -1; for 3 previous smaller is 1; for 0 none smaller → -1; for 2 previous smaller is 0; for 5 previous smaller is 2.

💡 Track previous smaller elements by maintaining a stack of candidates.

💡 Remove elements from stack that are not smaller than current element.

💡 Top of stack after removals is the previous smaller element or -1 if none.

Why it failed: Fails to pop elements >= current, causing wrong previous smaller values. Fix by popping until top < current.

✓ Stack correctly maintains previous smaller elements for all positions.

t2_01edge

Input{"arr":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array returns empty output.

💡 Check how your code handles empty input arrays.

💡 Ensure no indexing or stack operations occur on empty input.

💡 Return empty list immediately if input is empty.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding a check for empty input and returning empty list.

✓ Handles empty input gracefully by returning empty output.

t2_02edge

Input{"arr":[7]}

Expected[-1]

⏱ Performance - must finish in 2000ms

Single element has no previous smaller element, so output is -1.

💡 For single element arrays, previous smaller is always -1.

💡 Ensure your code does not access invalid indices for single element.

💡 Return [-1] for single element input.

Why it failed: Fails by accessing invalid indices or returning wrong value for single element. Fix by handling single element case correctly.

✓ Correctly returns -1 for single element input.

t2_03edge

Input{"arr":[2,2,2,2]}

Expected[-1,-1,-1,-1]

⏱ Performance - must finish in 2000ms

All elements equal, so no previous smaller element exists for any position.

💡 Equal elements are not smaller, so they should be popped from stack.

💡 Stack should be emptied for each element equal to current.

💡 Result is -1 for all positions when all elements equal.

Why it failed: Fails by treating equal elements as smaller or not popping them. Fix by popping elements >= current, not just >.

✓ Correctly returns -1 for all elements when all are equal.

t3_01corner

Input{"arr":[1,2,3,4,5]}

Expected[-1,1,2,3,4]

⏱ Performance - must finish in 2000ms

Strictly increasing array: previous smaller is always immediate previous element.

💡 In strictly increasing arrays, previous smaller is the element just before current.

💡 Stack will always have the immediate previous element as top.

💡 Ensure stack is not popped unnecessarily for increasing sequences.

Why it failed: Fails by popping too aggressively causing previous smaller to be -1 incorrectly. Fix by popping only elements >= current, not > current.

✓ Correctly identifies immediate previous smaller elements in increasing sequences.

t3_02corner

Input{"arr":[5,4,3,2,1]}

Expected[-1,-1,-1,-1,-1]

⏱ Performance - must finish in 2000ms

Strictly decreasing array: no previous smaller element exists for any position.

💡 In decreasing arrays, stack will be emptied for each element.

💡 No element before current is smaller, so output is always -1.

💡 Check that your code does not mistakenly assign previous elements.

Why it failed: Fails by returning wrong previous smaller values due to incorrect stack logic. Fix by popping all elements >= current.

✓ Correctly returns -1 for all elements in decreasing sequences.

t3_03corner

Input{"arr":[2,1,2,1,2]}

Expected[-1,-1,1,-1,1]

⏱ Performance - must finish in 2000ms

Alternating pattern tests correct popping and stack maintenance for repeated smaller elements.

💡 Stack must pop elements >= current to find correct previous smaller.

💡 Repeated smaller elements reset the stack top correctly.

💡 Check that stack top after popping is used as previous smaller.

Why it failed: Fails by not popping equal or greater elements causing wrong previous smaller. Fix by popping all elements >= current before checking top.

✓ Correctly handles alternating pattern with repeated smaller elements.

t4_01performance

Input{"arr":[100000,99999,99998,99997,99996,99995,99994,99993,99992,99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,99981,99980,99979,99978,99977,99976,99975,99974,99973,99972,99971,99970,99969,99968,99967,99966,99965,99964,99963,99962,99961,99960,99959,99958,99957,99956,99955,99954,99953,99952,99951,99950,99949,99948,99947,99946,99945,99944,99943,99942,99941,99940,99939,99938,99937,99936,99935,99934,99933,99932,99931,99930,99929,99928,99927,99926,99925,99924,99923,99922,99921,99920,99919,99918,99917,99916,99915,99914,99913,99912,99911,99910,99909,99908,99907,99906,99905,99904,99903,99902,99901]}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100 with strictly decreasing values to test O(n) stack solution performance within 2 seconds.

💡 Brute force O(n^2) will time out for large n.

💡 Use a monotonic stack to achieve O(n) time complexity.

💡 Push and pop each element at most once for linear time.

Why it failed: TLE due to nested loops O(n^2) approach. Fix by implementing O(n) monotonic stack solution.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Consider the following code for a circular queue of capacity 3. After executing these operations in order: enQueue(1), enQueue(2), enQueue(3), deQueue(), enQueue(4), what is the value of the tail pointer?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace enQueue(1), enQueue(2), enQueue(3)

   Initially, head=0, tail=0, size=0. After enQueue(1): tail=1, size=1; enQueue(2): tail=2, size=2; enQueue(3): tail=0 (wrap-around), size=3.

2. Step 2: Trace deQueue() and enQueue(4)

   deQueue() moves head from 0 to 1, size=2. enQueue(4) inserts at tail=0, then tail=1, size=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Tail pointer wraps modulo capacity, final tail=1 after last enQueue [OK]

Hint: Tail pointer increments modulo capacity [OK]

Common Mistakes:

• Forgetting modulo wrap-around
• Off-by-one tail position
• Confusing head and tail pointers

2. Consider the following buggy code for asteroid collision. Which line contains the subtle bug that causes incorrect behavior on equal size asteroids?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

medium

A. Line with 'stack.pop()' inside 'if stack[-1] < -a:'

B. Line with 'while alive and stack and stack[-1] > 0 and a < 0:' condition

C. Line with 'alive = False' inside 'elif stack[-1] == -a:'

D. Line with 'stack.append(a)' after the while loop

Solution

1. Step 1: Identify behavior on equal size asteroids

   When sizes are equal, both asteroids should explode (pop from stack and not append current).

2. Step 2: Check code for equal size case

   In the buggy code, stack.pop() is missing when sizes are equal, so the top asteroid remains incorrectly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing stack.pop() causes incorrect survival of equal asteroid [OK]

Hint: Equal size asteroids both must be removed [OK]

Common Mistakes:

• Forgetting to pop stack on equal size
• Appending asteroid after it exploded
• Incorrect while loop condition

3. The following code attempts to implement the optimized next greater element algorithm. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line with 'while stack and num > stack[-1]:' condition

B. Line 'while stack:' loop assigning -1 to remaining elements

C. Line 'nums1_set.remove(smaller)' inside the if condition

D. Line missing 'next_greater_map[smaller] = num' inside the while loop

Solution

1. Step 1: Identify missing mapping assignment

   The code pops smaller elements but does not assign their next greater element in next_greater_map, causing missing or incorrect results.

2. Step 2: Confirm other lines are correct

   The while condition, set removal, and final assignment of -1 are all correct and necessary for correctness and efficiency.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without mapping assignment, queries for nums1 elements fail [OK]

Hint: Mapping next greater elements must happen immediately after popping [OK]

Common Mistakes:

• Forgetting to assign next greater element after popping from stack
• Incorrectly removing elements from nums1_set too early
• Misplacing the final assignment of -1 for leftover stack elements

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 the stock prices can be negative and you want to compute the span as before. Which modification to the monotonic stack approach correctly handles negative prices without breaking the algorithm?

hard

A. Store pairs of (price, span) in the stack and accumulate spans when popping

B. Change the while condition to pop only when top price is strictly less than current price

C. Use a balanced binary search tree instead of a stack to handle negative values

D. No change needed; the existing monotonic stack approach works for negative prices

Solution

1. Step 1: Understand impact of negative prices

   Negative prices do not affect the monotonic stack logic, but to handle spans correctly, storing spans with prices helps accumulate consecutive spans efficiently.

2. Step 2: Why storing (price, span) pairs works

   When popping smaller or equal prices, their spans can be added to the current span, allowing correct span calculation even with negative or mixed values.

3. Step 3: Why other options fail

   Changing while condition to strict less breaks equal price handling. Balanced BST is unnecessary overhead. No change ignores span accumulation needed for correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Storing spans with prices is a known robust solution [OK]

Hint: Store (price, span) pairs to accumulate spans correctly [OK]

Common Mistakes:

• Assuming no change needed
• Using strict less instead of less or equal