Day 14 of 30 days of Data Structures and Algorithms and System Design Simplified — Stack
Welcome back peeps. Hope all’s well. In this post we will cover Stack as follows —
What and Why Stack (in 2–3 sentences)?
How does Stack work?
Important Patterns and Techniques in Stack Questions
Most Important Questions with Solutions
Tips and Techniques to solve Stack Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Stack
Importance : Very High
Note : New stack questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Stack?
Stack is one of the most important linear data structure in which one can stack the items in a particular fashion ( LIFO — Last in First Out).
It has one end through which you can add and remove the elements in the stack.
Examples of Stack problems —
Valid Parentheses
Min/Max Stack
Tree Traversals
Parsers
Binary Search Tree Questions etc
How does Stack work?
A stack works using two main operations push and pop. When an element is added to the stack, it is placed on the top of the stack. The element that was added last will be the first one to be removed.
There are two functions that are important in stack:
- Push() : Add the element to the top of the stack
- Pop() : Remove the element from the top of the stack
The stack pointer is a register that holds the address to the top item in the stack. It’s called the “top” of the stack.
The main Operations of stack are —
Push : Insert an element at the top of the stack
Pop: Remove the top element of the stack
Top : To return the top element of the stack without removing it
IsEmpty : To check if the stack is empty
Important Patterns and Techniques in Stack Questions
Some important patterns and techniques in stack questions include:
- LIFO (Last In First Out) principle: This principle is used to keep track of the order of elements in the stack and to determine which element should be removed next.
- Using stack to reverse order of elements: This technique is used to reverse the order of elements in an array or a string, by inserting the elements into a stack one at a time, and then removing them in reverse order.
- Using stack to check balanced Parentheses: This technique is used to check whether an expression contains matching parentheses, by pushing opening parentheses onto a stack and popping them off when a matching closing parenthesis is encountered.
- Using stack to implement Depth First Search: This technique is used to implement the Depth First Search algorithm by using a stack to keep track of the next vertex to visit.
It important to know two methods that are very important — push and pop.
You can push the element using append method and pop the element using remove method.
Patterns → Questions like below belong to Stack( not limited to):
Design Browser History
Min/Max Stacks
Jump Games
Validate Sequences
Remove Duplicates
Valid Parentheses
Min/Max Stack
Tree Traversals
Parsers
Binary Search Tree Questions etc
Most Important Questions with Solutions
Note : New stack questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important stack questions.
Valid Parentheses
Question —
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example :
Input: s = "()[]{}"
Output : TrueSolution :
Main Logic/Idea —
The main logic here is using hash map to map the close parentheses to open parentheses, append to the stack and using pop the similar match parentheses while traversing through the stack.
Implementation —
def isValid(self, s: str) -> bool:
parenthesisMap = { ")":"(", "]":"[", "}":"{" }
ans = []
for i in s:
if i not in parenthesisMap:
ans.append(i)
continue
if not ans or ans[-1] != parenthesisMap[i]:
return False
ans.pop()
return not ansQuestion Link
Similar Pattern —
Check If Word Is Valid After Substitutions
Check if a Parentheses String Can Be Valid
Move Pieces to Obtain a String
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Min Stack
Question —
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack()initializes the stack object.void push(int val)pushes the elementvalonto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
Example 1:
Input:["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]Solution :
Main Logic/Idea —
The main logic is — take two stacks ( in one stack store values and for other store the min values) and maintain a pointer ( say top) to get the top element of the stack. Push function is to append the values in both the stacks. Pop function is to remove the top element. To get min, retrieve from the top of the minstack.
Implementation —
class MinStack:def __init__(self):
self.stack = []
self.mStack = []def push(self, val: int) -> None:
self.stack.append(val)
val = min( val, self.mStack[-1] if self.mStack else val)
self.mStack.append(val)def pop(self) -> None:
self.stack.pop()
self.mStack.pop()def top(self) -> int:
return self.stack[-1]def getMin(self) -> int:
return self.mStack[-1]Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Next Greater Element I
Question —
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example :
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]Solution :
Main Logic/Idea —
The main logic is to add the elements from num2 and see if there’s same element is nums1. If there’s an element in nums1 take its index and store it in the ans array after checking if there’s any corresponding greater element in nums2.
Implementation —
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
nIndx = {no:index for index,no in enumerate(nums1)}
ans = [-1] * len(nums1)
stck = []
for i in range(len(nums2)):
curr = nums2[i]
while stck and curr > stck[-1]:
val = stck.pop()
ix = nIndx[val]
ans[ix] = curr
if curr in nIndx:
stck.append(curr)
return ansQuestion Link
Similar Pattern —
Sum of Total Strength of Wizards
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New stack questions with solutions are added every day. So keep checking this post daily.
Complexity Analysis
Search an element : O(n)
Access element in the stack : O(n)
Insert element in the stack : O(1)
Remove element from the stack : O(1)
Tips and Techniques to solve Stack Questions Fast.
Few things can help you with stack related questions -
Know how recursion works.
Know the important methods/functions of stack before solving the stack questions.
Know how to move “top” pointer of the stack.
Know how to move pointers for two stacks simultaneously.
Know how hash map/hash set works.
That’s it for now. Day 6: Queue coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
