Today I solved an easy category problem named "Min Stack". Problem statement was to design a stack data structure which has getMin() operation along with all regular stack operations like Push, Pop, Peek/Top.
Next I started checking for solutions having better timing than my solutions. Sample solution present under best time category was created using Linked List where each item stores min value along with it. By using this approach it avoided multiple if checks as were present in my solution and made code look a lot more cleaner and run faster. This solution uses O(N) space in all cases while mine uses O(N) space in worst case but that is kind of tradeoff you make for speed.
Why I posted this as a blog, just so as at least a future me may read this again. Everyone else who reads this is a bonus ;)
I used two stack approach, where one stack was for regular stack operations and other was to keep track of min values. At each push if pushed values is smaller or equal to the last smallest value then I push value in min values stack. You may take a look at my code here. Below is screenshot of the solution:
Why I posted this as a blog, just so as at least a future me may read this again. Everyone else who reads this is a bonus ;)
