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 and Maximum Area of 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:
Push the last element of the array to the stack
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.
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
Next Smaller Element
Previous Greater Element
Previous Smaller Element
Try these problems by yourself.
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.
The code can be found here
LeetCode
I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.
Follow me on medium - https://sourav-saikia.medium.com
Follow me on dev.to - https://dev.to/sksaikia
Follow me on twitter - https://twitter.com/sourav__saikia
Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia
The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.
| Problem Name | Problem No | Article Links |
|---|---|---|
| Contains Duplicate | 217 | https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0 |
| Jewels and Stones | 771 | https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37 |
March LeetCoding Challenge
| Problem Name | Problem No | Article Links |
|---|---|---|
| Distribute Candies | 575 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9 |
| Set Mismatch | 645 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9 |
| Missing Number | 268 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb |
| Intersection of Two Linked Lists | 160 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563 |
| Average of Levels in Binary Tree | 637 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8 |
| Short Encoding of Words | 820 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557 |
| Remove Palindromic Subsequences | 1332 |
Top comments (0)