Stack Patterns
Tags: algorithms, codenewbie, computerscience
Published: 2021-03-13 09:55:02


While approaching an algorithmic problem, we should give more attention to the similarities between problems. If we can find these similarities, then solving that kind of problems become very easy. Today we are going to discuss the patterns in the stack.

With this pattern, we can solve a lot of problems based on the stack. We can even solve the popular [Stock Span](https://www.geeksforgeeks.org/the-stock-span-problem/) and [Maximum Area of Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/) problem.

## **Approach**

Let’s go through the **Next Greater Element** problem. Here we have to find, the next greater element for each number in an array. We will use the stack to store the greater elements. We will traverse the array backwards.

Algorithm:

 1. Push the last element of the array to the stack

 2. For all the other elements repeat the following process

— Check if the stack is empty,if it is then put -1 at that index. ie. That number does not have any element greater than that to its right side.
 — If the peek of the stack is greater than the current element then the stack peek is the next greater element.

— If not, keep popping the top of the stack until you find an element greater than the current element

— If now the stack is empty, place -1 at that index(no greater elements)

— Else peek of the stack is the greater element

— push the current element in the stack

The algorithm can be understood here.

![A dry run of the algorithm for the next greater element](https://cdn-images-1.medium.com/max/2400/1*ZhULRGR14L1vd01OWSQtHg.gif)

Now you have understood how to solve this problem, you can visualize the other related problems on your own.

If we follow this approach and with little changes we can solve **Next Smaller Element**, **Previous Greater Element** and **Previous Smaller Element** problem easily.

All the four problems along with the java code are given below.

**Next Greater Element**
{% gist https://gist.github.com/sksaikia/539846969b0acfd4e57b5d2cdc1fe400.js %}
**Next Smaller Element**
{% gist https://gist.github.com/sksaikia/ddaefde8750ab6c45d10a472b8d65301.js %}
**Previous Greater Element**
{% gist https://gist.github.com/sksaikia/62bd915e6b746767ba9485f3cf77907d.js %}
**Previous Smaller Element**
{% gist https://gist.github.com/sksaikia/4b154711d0d6a299c2128efcc26a96bf.js %}
Try these problems by yourself.

 1. [Previous smallest element](https://www.interviewbit.com/problems/nearest-smaller-element/)

 2. [Previous greater element variation](https://leetcode.com/problems/132-pattern/)

 3. [Smallest on the left of an array](https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/)

4. [Next greater element](https://www.geeksforgeeks.org/next-greater-element/)

5. [Next smaller element](https://www.geeksforgeeks.org/next-smaller-element/)

6. [Previous greater element](https://www.geeksforgeeks.org/previous-greater-element/)

In our future tutorials, we will try to extend this problem and use this pattern to solve more problems. You can try the following problems by yourself.

 1. [Stock Span Problem](https://www.geeksforgeeks.org/the-stock-span-problem/)

 2. [Maximum Area Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)

 3. [Maximum Area of Histogram in 2D](https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/)

The code can be found here
{%github sksaikia/Leetcode %}