Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- getMin() – Retrieve the minimum element in the stack.
MinStack minStack = new MinStack();
minStack.getMin(); --> Returns -3.
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
So…fun fact, I deleted all my code for this challenge on accident and had to redo it! Backstory: I went to make this post and I realized my vim setup sucked. Staying home due to COVID-19 has made me stir crazy. Well, that and my home setup has always been okay, but as I have grown older it no longer matches what I would consider to be an ideal work from home setup. Ten years of banging away at a keyboard has made me realize things:
That being said, I’ve been less and less interested in “cool” hardware and more and more interested in ergonomics. Things that help keep my body in top shape so I can live a long, happy life. Stuff like standing desks, chairs or stools that improve posture, mice that are made to minimize the effects of RSI & carpal tunnel, etc. Of course, that has led me to really absurd ideas like swapping keyboard maps (something I’ve actually done before. I can type Dvorak decently. I could probably make an entire separate post on my feelings about alternative keymaps though), or keyboards like the Kinesis Advantage 2 and ErgoDox EZ (pictured below).
The Kinesis Advantage 2 ErgoDox EZ
Anyway, I’m going down a rabbit hole here, but basically I’ve been trying to redo my home setup to make it match what I currently want in a work desk - because it’s definitely not that. The first part came today, and that was my 32 inch BenQ HDR display. It’s awesome. I forgot how badly the web sucked in 4k though. Still looks like we have a ways to go there, so I had to scale the text up a bit otherwise it’s absurd and unreadable.
Other than that, it’s great. Took some time to get everything configured, but I completely moved my Windows/Linux PC into the closet for the time being. I don’t know if I really need it anymore. Lately I’ve been thinking more about living more “minimalist” and a big, loud desktop PC that dual boots is just not something I need anymore. If I have my MacBook Pro and a dock, I can do everything I need to do. So that’s the plan going forward: just my MacBook Pro and a dock. I can dock in when I’m home and use the big display - then when I need to head to class or I’m traveling, I can just grab it and go - no more syncing filesystems or pushing to repositories, it’s the same machine.
Anyway, I’m totally off-topic. I got lost in vim configuration for this new display and totally deleted my solution like a dumbass. I tried to recover it, but leetcode doesn’t save your solution, so I had to solve it again. Fortunately for me, I could use the practice and it was pretty easy anyway.
This solution doesn’t really have a time complexity because today you’re designing an object. I suppose if we were to look at the functions I was asked to design and ask ourselves which has the worst time complexity, it would be
GetMin() which has a time complexity of O(n). The space complexity of the object would just be O(n) as well - the size of the elements that you push onto it.