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 innums
.The previous smaller number of an element
x
is the first number (highest index) to the left ofx
that is smaller thanx
. 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!
- 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?
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
- Initialize an empty stack. We will push element indices onto this.
- 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).
- If the stack becomes empty, there is no element on the left smaller than X.
- 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[].
- 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.
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.