Even though this is an easy, I spent some extra time to really explain why the solution works. I think it's tricky enough to warrant that, but let me know if it felt too long though.
Really liked the O(1) explanation, thanx. Can you make the video explaining what does the term amortized exactly mean, can we assume it as same as avg time?
I appreciate the longer explanations, it’s very thorough and it clears a lot of confusion for me. And I also appreciate you mentioning that you wouldn’t be able to solve it if you did it for the first time. 😅
I used to watch your videos on 1.5x speed, yet I always had to rewind because I kept missing the logic. Once I humbled myself and decided to slow it down to 1x speed - I have a much more thorough understanding of your content. THANK YOU!
Literally just solved it today after 4 years. I think it was daily challenge or something. I remembered to push onto in-stack and pop from outstack, checking if it’s empty and doing an outstack.push( in stack.pop()). Lol 😂. But I liked your “ amortized” explanation, didn’t think of “ amortized”. - Amy
i think you should really consider changing it up and once in a while instead of saying its pretty efficient, you should say its hella efficient. would be very satisfying to hear.
Do you think it is possible to do it using one stack only (if there is a follow up question)? I think it is possible but it won't be memory efficient I guess
You can. I came up with 2 ways: 1. Create a pointer that will refer to the element that should be returned when the pop() or peek() function is called. If we call pop(), we move this pointer forward by 1 element. In push() we add elements to the end of the list, and in the function empty() we return: pointer == len(stack). 2. If you write in Python, you can set the stack as a list, and when you call pop(), return the result of pop(0). Then 0 element will be removed from the list and its value will be returned. If we compare these two methods, the first requires more memory, but all functions are executed in O(1), the second method uses less memory, but the pop() method can take O(n) time depending on the specifics of the implementation remove 0 item from list in different languages.
Queues are FIFO. Stacks are LIFO. Queue, original order: user1, user2, user3 Queue, popping: user3, user2, user1... Queue popping reverses order. This is why 2 (!) queues are necessary - reversing reversal preserves the original order 🙂
in the peek method, you can just return the first element of the stack1 rather than again popping and appending the elements. it can go like if not self.s2: return self.s1[0]
When I first started watching your videos I would probably look at this problem and take some time to do the O(n) solution. After about a year of practicing, there was literally not a microsecond that I even considered to solve it in O(n) because I instantly realized that would be trivial and the only real problem is doing this in amortized O(1). point is you helped me a lot to grow
Even though this is an easy, I spent some extra time to really explain why the solution works.
I think it's tricky enough to warrant that, but let me know if it felt too long though.
Really liked the O(1) explanation, thanx.
Can you make the video explaining what does the term amortized exactly mean, can we assume it as same as avg time?
@@akshayiithydno that was constant time operation
honestly, i only do Leetcode just when you do, so please don't stop
no its perfect.
I appreciate the longer explanations, it’s very thorough and it clears a lot of confusion for me. And I also appreciate you mentioning that you wouldn’t be able to solve it if you did it for the first time. 😅
I used to watch your videos on 1.5x speed, yet I always had to rewind because I kept missing the logic. Once I humbled myself and decided to slow it down to 1x speed - I have a much more thorough understanding of your content. THANK YOU!
ohh no i am watching in 2x.
@@mohdyasir4946 Lol don't worry, there's definitely a time and place to watch the videos quicker. I learned this after I made my original comment
Literally just solved it today after 4 years. I think it was daily challenge or something. I remembered to push onto in-stack and pop from outstack, checking if it’s empty and doing an outstack.push( in stack.pop()). Lol 😂. But I liked your “ amortized” explanation, didn’t think of “ amortized”. - Amy
i think you should really consider changing it up and once in a while instead of saying its pretty efficient, you should say its hella efficient. would be very satisfying to hear.
Great solution and explanation but this shouldn't be an *easy* question :(
Found out today that you solve daily problems , will be following these videos from today♥
Plz add this question to neetcode all on ur website it will be really helpful.
Great video
I was asked this question in my OOD round at Amazon. Messed it up :/
@NeetcodeIO , you should create a private method to avoid duplucate code lines 11 and 17
I prefer WET (write everything twice) over DRY (don't repeat yourself) 😝
TIL what WET and DRY meant... learning something new every time I watch neetcode's videos
@@NeetCodeIO 🫠
Do you think it is possible to do it using one stack only (if there is a follow up question)? I think it is possible but it won't be memory efficient I guess
You can. I came up with 2 ways:
1. Create a pointer that will refer to the element that should be returned when the pop() or peek() function is called. If we call pop(), we move this pointer forward by 1 element. In push() we add elements to the end of the list, and in the function empty() we return: pointer == len(stack).
2. If you write in Python, you can set the stack as a list, and when you call pop(), return the result of pop(0). Then 0 element will be removed from the list and its value will be returned.
If we compare these two methods, the first requires more memory, but all functions are executed in O(1), the second method uses less memory, but the pop() method can take O(n) time depending on the specifics of the implementation remove 0 item from list in different languages.
@@arturpelcharskyi1281 that's breaking the rules, because in a stack, you can only look at the top of the stack (the last element)
@@arturpelcharskyi1281great solve. I solved using the first approach
Man fuked up google’s Interview. Will be grinding your sheet and doing LT contests. Thanks for your explanation! ❤
Same here messed up with a simple question. Started grinding Daily..
is this actually correct? i think you need to move everything from the second stack to the first before pushing.
Nice🎉🎉
Queues are FIFO. Stacks are LIFO.
Queue, original order: user1, user2, user3
Queue, popping: user3, user2, user1...
Queue popping reverses order.
This is why 2 (!) queues are necessary - reversing reversal preserves the original order
🙂
Neato! Brain fried! 🧠🤯
Why is this video not listed in 'Neetcode All'?
nice
How to come up with this idea...
in the peek method, you can just return the first element of the stack1 rather than again popping and appending the elements.
it can go like
if not self.s2:
return self.s1[0]
But that violates property of stack, because in stack you can only access the last element.
@@mzafarr got it!
See 11:20
When I first started watching your videos I would probably look at this problem and take some time to do the O(n) solution. After about a year of practicing, there was literally not a microsecond that I even considered to solve it in O(n) because I instantly realized that would be trivial and the only real problem is doing this in amortized O(1). point is you helped me a lot to grow