This content originally appeared on DEV Community and was authored by DEV Community
Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
155. Min Stack
Difficulty: Easy Language: JavaScript
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]
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,topandgetMinoperations will always be called on non-empty stacks. - At most
3 * 104calls will be made topush,pop,top, andgetMin.
Solution:
Highlight of this problem is constant time O(1) (note 2) is required instead of linear time. And the key to solve it is to create two stack: one regular 'stack' and a 'min' stack to store minimun value of all elements being added. To further explain, when a new element is added to the 'stack', compare this element with the smallest element in 'min' stack. If the new element is smaller than the smallest element in 'min' stack, add this new element to the 'min' stack. If it equals or greater than current smallest element in 'min' stack, push duplicate the smallest element in 'min' stack and push it to 'min' stack again. This way, the last or top element in the 'min' stack in always the minimum. And when we need to access the minimum value, we just need to get the last element in 'min' stack.
class MinStack {
constructor() {
this.stack = [];
this.min = [];
}
//construct (note 1) two stack under class MinStack. One regular
//'stack and the other 'min' stack used to store minimum value
push(x) {
if (!this.min.length) this.min.push(x);
else this.min.push(Math.min(x, this.getMin()));
//If length (note 3) of 'min' stack does not exist (note 4), then
//it's an empty array. Push (note 5) element 'x' into 'min'
//stack.If 'min' stack is not empty, compare 'x' and the smallest
//value currently in 'min' stack, and push the smaller value into
//'min' stack.
this.stack.push(x);
//Push (note 5) element 'x' into the regular 'stack'.
}
pop() {
this.min.pop()
return this.stack.pop()
//Pop (note 6) last element from both stack
}
top() {
return this.stack[this.stack.length-1];
//return last element of the stack
}
getMin() {
return this.min[this.min.length-1];
//return last element of the stack which is also the minumum
}
}
Time and Space Complexity
- Time: O(1)
- Space: O(2N)
References:
LeetCode Problem Link
LeetCode Discussion: control_the_narrative
Youtube: Andy Gala
Note 1: Classes (JS/ES6)
Note 2: Constant time
Note 3: Array.length
Note 4: Logical NOT (!)
Note 5: Array.push()
Note 6: Array.pop()
Blog Cover Image Credit
This content originally appeared on DEV Community and was authored by DEV Community
DEV Community | Sciencx (2022-03-05T01:55:19+00:00) Day 23 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#155. Min Stack(Easy/JavaScript). Retrieved from https://www.scien.cx/2022/03/05/day-23-of-studying-leetcode-solution-until-i-can-solve-one-on-my-own-problem155-min-stackeasy-javascript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.