Problem 49:Min Stack[Google]
We're almost to 50. To celebrate this, we got a DSA Design Question
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey
Hey there my lovely reader,
Time really flew by huh. Before we realized it, we were at problem number 49. So close to 50. That means I’ve been writing for almost a year at this point. To celebrate this special occasion, I’ve decided to run a special promo. You can now get this newsletter for 50% off. This offer will be available for a limited time only.
This amounts to the low daily cost of 11 INR or 0.14 USD.
If you’re on the fence about trying it out, here is a sample solution. We cover the Boolean Satisfiability problem, which is widely regarded as one of the hardest problems asked in Coding Interviews (it is based on a still-unsolved, million-dollar problem in Computer Science).
Getting back to the question for the week, we have a question that you have to know. Whether it’s to ace your interviews, boost your rankings in Competitive Programming, or simply want to develop your problem-solving skills, this question is a must-have in your toolkit. I really like this problem, because it incorporates Data Structure Design, which is a very important skill in software engineering.
This problem can be found as problem 155. Min Stack on Leetcode.
Problem
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 elementval
onto 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.
You must implement a solution with O(1)
time complexity for each function.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
Constraints:
-231 <= val <= 231 - 1
Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks.At most
3 * 104
calls will be made topush
,pop
,top
, andgetMin
.
You can test your solution here
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on next. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of these questions, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75