Previous Smaller Element

Similar To Leetcode #503 (Medium)

Introduction

This blog post covers a variation of the Next Greater Element II problem on Leetcode. It is one of the problems which requires very clever use of a simple data structure. Moreover, this technique is used in several other Leetcode problems such as Largest Rectangle In Histogram and Maximal Rectangle as a sub-routine.

Problem Statement

Given an array nums, return the previous smaller number (PSE) for every element in nums.

The previous smaller number of an element x is the first number (highest index) to the left of x that is smaller than x. If there’s no such element, return -1 for this number.

Suppose nums[] = {9, 6, 10, 9, 5}.
The previous smaller elements (PSE) are as follows:
PSE of 9 is -1 (no element to the left of 9 that is smaller).
PSE of 6 is -1 (no element to the left of 9 that is smaller).
PSE of 10 is 6.
PSE of 9 is 6.
PSE of 5 is 6.

Thought Process

It’s easy to come up with a naive algorithm for the problem.
For an element at index i, we start scanning elements from index (i-1) to index 0 and select the first element which is smaller than nums[i].
Since there are n elements, and for each element, we are iterating over n elements to the left in the worst case, the overall runtime is O(n²).

However, Leetcode problems are seldom that simple.
n can be as large as 10⁴ which means that an O(n²) time algorithm will be too slow.
The challenge is to optimize the runtime.

To optimize, we should figure out what’s the redundant computation that the algorithm is doing and try to eliminate it.

Let’s dig in!

Suppose our array has 5 elements [1, 14, 12, 10, 4] and we know the index of the next smaller element to the left for 1, 14, 12, and 10.

Do we need to iterate over the entire array to figure out the previous smaller element for 4?
No!

Skipping over elements by making use of the previous smaller elements already known. The lines indicate following the PSE of earlier numbers to compute the PSE of the current number.

• We know that the element on the immediate left of 4 i.e. 10 > 4. Thus, 10 is not the previous smaller element for 4.
• We also know that the previous smaller element of 10 is 1. So, we don’t need to compare 4 with 12 and 14, because we already know that everything between 10 and 1 is greater than 10 and hence also greater than 4.

We were able to skip over 14 and 12 because there’s no point in looking at elements that are bigger than 10.

In essence, instead of iterating through each element, we can skip elements by jumping over to the previous smaller elements. This avoids redundant computation. (KEY POINT 1)

Great! We were able to identify and remove the redundant computation. But how should we implement this and does it actually improve the asymptotic runtime?

PSE for elements to the right of X will either be X, Y, or an element to the left of Y.

Say we’re moving from left to right in the array and computing the previous smaller element for each element.

Notice that, when we encounter an element say X, everything to the left of X that is greater than X is meaningless since they’ll never be the previous smaller element for elements to the right of X. (KEY POINT 2)

This hints towards using a stack. We want to push elements to the stack when we encounter them and pop elements that are of no use to us moving forwards.

Algorithm

1. Initialize an empty stack. We will push element indices onto this.
2. Traverse the array from left to right. When you encounter an element X, keep popping indices from the stack as long as the value at that index is bigger than X (because they’re of no use to use anymore — see Keypoint 2).
3. If the stack becomes empty, there is no element on the left smaller than X.
4. If the stack isn’t empty, the index on top of the stack corresponds to the previous smaller element of X. Note this information in an array PS[].
5. Push index of element X onto the stack.

Why does this work?
Suppose the previous smaller element of X is Y.
When we push X onto the stack, we are guaranteed that the index of Y is already present somewhere in the stack.

This is because:

• When we encountered Y, we must have pushed it onto the stack.
• Since there is no element between Y and X that is smaller than X and Y (remember Y is the previous smaller element of X), Y could not have been popped from the stack.

Moreover, since everything between Y and X is greater than X, our algorithm will pop all of them from the stack till we have Y left at the top. At this point, we’ll set Y to be the previous smaller element of X.
If the stack is empty, that means there is no element smaller than X to its left.

Dry-run of the algorithm on the array [1, 14, 12, 10, 4]. Note that the red boxes indicate the elements that are popped from the stack when the element to be inserted is smaller than the top stack element.

Runtime Analysis

When dealing with stacks, it’s good to think about runtime in terms of the number of push/pop operations.
In this case, no element is re-inserted into the stack. Hence, each element is pushed onto the stack once and popped at most once. Thus, we have O(n) push/pop operations.
Moreover, before every pop operation, we just do an O(1) comparison with the stack top. Thus, the overall runtime is O(n).

Follow-Ups

In this post, we have covered how to compute the previous smaller element. But if you understand the concept, it can be easily applied to variations such as the previous larger element and the next smaller/greater element.
Think about how to do this as an exercise!

Moreover, this can be applied to other Leetcode problems as well such as Largest Rectangle In Histogram and Maximal Rectangle. Here’s a blog post explaining the Largest Rectangle in Histogram problem.

Please endorse the article and let me know in the comments if this explanation helped you understand the problem better. Would love to hear any feedback/suggestions/edits as well.