@@TheAdityabhandari Did you solve in Java? Maybe bc Java requires explicit typing and float division is needed for possible decimals? My JS & Py3 solutions were just accepted a few mins ago and no floats were needed.
@@nokigaming6651 well the market was pretty shit 5 months ago and it's getting better but if any new grad reads this in the future: If u want to get an interview opportunity during a bad market u will probably need 2-3 personal projects that are more robust than a calculator or a pong game
@@latinochild3131 in Python, using / with two integers gives an integer result - eg 4/3 = 1. If you want to get a float answer you have to specify that your input is a float. That could cause some problems if a user wasn't aware of it! Python 3 a gives a more expected result - 1.3333.
thanks a lot! the explanation before the code is always on point 👍 I tried to do it a bit differently class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for t in tokens: if t in ['/', '-', '+', '*']: rOp = stack.pop() lOp = stack.pop() expression = lOp + t + rOp stack.append(str(int(eval(expression)))) continue stack.append(t) return stack.pop()
the use of 'eval' is not secure in the real world. if the expression can be controlled by a user facing the application, it can be crafted into a malicious input and will be run as a Python expression.
Note that using a//b in python is not the same as using int(a/b). Double slash is floor division which will also round down with negative numbers. int(a/b) will round toward zero
Another solution would be to define a recursive function `evaluate(stack)` that calls itself when another operator is encountered. You'd effectively still be using the stack data structure, only that your stack is the call stack's stack frames!
That was the solution I came up with on my own. I thought it was clever but it also looks way more complex compared to this solution. On the other hand my memory came through in the top 98.5% so it's clearly a good approach on that front lol
I love your videos. Minor issue was the explanation of popping the stack to assign values to a and b. You say that we want to “subtract the one that was popped second from the one that was popped first”. I believe you just mixed up the words, but in case others got slightly confused, b actually gets the value that is popped first and a gets the value popped second. This is clear if you take an input example [2, 1, -], which you actually discussed at 4:30 in the video, this would be 2 - 1. Therefore you would want to subtract the one popped first from the one popped second. And in python, because tuple unpacking is done right to left, b did indeed get the first popped value, so your solution is still valid despite mixing up the words.
This could have been a good opportunity to introduce lambda syntax: ``` class Solution: def evalRPN(self, tokens: List[str]) -> int: operatorMap = { "+": lambda l,r: l + r, "*": lambda l,r: l * r, "-": lambda l,r: l - r, "/": lambda l,r: int(l / r), } stack = [] for token in tokens: if token in operatorMap: right = stack.pop() left = stack.pop() token = operatorMap[token](left, right) stack.append(int(token)) return stack.pop() ```
@@vasudhajha9115 Almost! The spec includes this note: "Note that division between two integers should truncate toward zero." a//b will always truncate downwards so it does not work for negative operands.
No need to do the a, b to do a swap for subtraction. Worst case every operator is “-“ and you made new a,b objects each time in the for loop. Instead notice that “b - a” is equal to “-a + b”. Thus you can write it in one line with no a and b needed: stack.append(-stack.pop()+stack.pop()) Likewise, we can assume this is a valid RPN per the problem description, which your solution correctly assumes. Thus we can avoid the temp a,b for division as well using the 0 and 1 index for denominator and numerator respectively. Thanks for the videos. Only trying to help simplify things.
I have not tried this one, but if the statement is always valid, would it work if we don’t use stack but just 2 number var? First 2 tokens always assign to 2 int var. Next is operator, apply then assign to int1. Next is number, assign to int2. Repeat the above 2 for every subsequent operator & number. Return int1 value.
Can anyone explain why I cannot use b//a to substitute int(b/a) ? I still got 0 from b//a but cannot pass below test case. Input tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output 12 Expected 22
for negative operations, // will round downwards (i.e -1.2 will round to -2) while the spec says it should round closest to zero (so it should round to -1 in this case). You use int(b/a) for that.
Curious as to how this works since the input values in the array are strings and there's no sort of type casting happening. ("2" * "2") for example should fail.
I solved this problem by making a dictionary with the values being the operators and checking to see if c = an operation in the dictionary. If it does pop right pop left then left (insert operant) right =
I think you need to strongly emphasize the correct way to approach the division and what it means to round towards zero. I'm assuming many people in the comments are having trouble between floor division and truncating. I think talking about this conceptually would help many of us especially if coding it up in a different language
this problem could be renamed: implement basic calculator you will find that in trying to implement a basic calculator to parse a string, it is much easier to do it with prefix notation isntead of infix ( + a b vs. a + b). at that point you are doing reverse polish notation as the problem specifies...
I like to avoid the "elif" statements by storing the operators in a dict (the deque can ofc just be a list): d = {"+": operator.add, "-": operator.sub, "/": operator.truediv, "*": operator.mul} l = ["+", "-", "*", "/"] def reverse_polish_notation(tokens): s = deque() for token in tokens: if token not in l: s.append(int(token)) else: second, first = s.pop(), s.pop() s.append(int(d[token](first, second))) return s.pop()
If I am using javascript what can i do when declaring [a, b] ? I try to do const [a, b] and const [c, d] so avoid having the same variable declaring twice. Its there a better way to do this? Thanks a lot for the video as always! learning so much!
Can someone tell me that why are we subtracting number that was popped 2nd with the number that was popped first? How do we know that the 2nd popped number is the biggest of them.
I know it's long time when you commented this but I will explain.This is becouse we have something like 5 4 - and we want to do 5-4 becouse this is representation for reverse polish notation.We have 2 numbers and this 2 numbers is in relation with this first sign. When we push on stack that means we go over array and push it like first me push 5 [5] ,after we push 4 and this is how look like list [5,4] and when we do .pop() this first number will be 4,second pop is 5 and now you can figure out.
Would this be doable in O(n) instead of O(2n)? Yes I know technically they're the same but practically they aren't. The way I have it figured in my head is that you could store the first digit of the array. Then every two elements after would be a digit and an operator. This would let you iterate through the array only once. My other instinct to solving it would have been with leading/trailing pointer style. Trailing pointer to keep track of the numbers, leading pointer to find the operators
I am wrong, using pointers will still need O(n) space if there are multiple complex expressions, which become operands of outer operator. Therefore, using stack is the best solution.
Stack never be empty becouse they clear this edge case(and other) every input in problem is good. Everything what you need to do is to do this callculation on polish way :)
Copying this comment from Leetcode for anyone confused about int(b / a) and why (b // a) doesn't work. Credit to user A_R_K for the comment. "// is the floor function. / is the divide function. By definition floor function would round the number to the smallest integer lesser than or equal to it. Hence, -17//6 is -3. This is because -3 is the smallest integrer lesser than or equal to -2.833.. One should ideally use int() to truncate the decimals."
class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for t in tokens: if t not in '+-*/': stack.append(int(t)) else: v2, v1 = stack.pop(), stack.pop() if t == "+": stack.append(v1 + v2) elif t == '-': stack.append(v1 - v2) elif t == '*': stack.append(v1 * v2) else: stack.append(int(v1 / v2)) return stack[-1]
If the stack will always have at most 2 elements, the the space complexity is technically O(1) no matter how large the input array, it will always be constant. Right?
I found a way to improve the time complexity by using the operator library.The logic is still the same but cut down the runtime by 50% import operator class Solution(object): def evalRPN(self, tokens): """ :type tokens: List[str] :rtype: int """ stack = [] op = { "+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv } for x in tokens: if x in op: a,b = stack.pop(), stack.pop() stack.append(int(op[x](b,a))) else: stack.append(int(x)) print(stack) return stack[0]
I have implemented the same problem in Java. But youtube is not allowing me to add a link to implementation of it in comment so I have requested @neetcode, to post a link of my java implementation to here as well.
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
Java Code (by a viewer): github.com/ndesai15/coding-java/blob/master/src/com/coding/patterns/stacks/ReversePolishNotation.java
The division operator requires the numerator to be converted to float in leetcode for the solution to be accepted, which is kind of weird
@@TheAdityabhandari Did you solve in Java? Maybe bc Java requires explicit typing and float division is needed for possible decimals? My JS & Py3 solutions were just accepted a few mins ago and no floats were needed.
Thank you so much for your videos, I got a job offer from Microsoft, without your videos this is not possible.
Hi bro can we connect by any chance on linkedin, if so can you plz drop your linkedin
Hi,
If you don't mind, can we connect on LinkedIn?
How did you get the interview in the first place?
@@nokigaming6651 well the market was pretty shit 5 months ago and it's getting better but if any new grad reads this in the future:
If u want to get an interview opportunity during a bad market u will probably need 2-3 personal projects that are more robust than a calculator or a pong game
@@dumbfailurekms Have you got a job recently as well?
I admire how you breakdown a problem into smaller ones and make it look simple!
Int divisions work differently in Python and Python3 - if you have a failing case try replacing int(b/a) with int(float(b)/ a)
can you explain why this works? i just want to have a better understanding of it
@@latinochild3131 in Python, using / with two integers gives an integer result - eg 4/3 = 1. If you want to get a float answer you have to specify that your input is a float.
That could cause some problems if a user wasn't aware of it! Python 3 a gives a more expected result - 1.3333.
Your such a life saver thanks a lot mate
Thank you! I was failing the third case on LC but your recommendation fixed my issue.
almost wanted to smash my laptop till I saw this. Thank you.
thanks a lot! the explanation before the code is always on point 👍
I tried to do it a bit differently
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for t in tokens:
if t in ['/', '-', '+', '*']:
rOp = stack.pop()
lOp = stack.pop()
expression = lOp + t + rOp
stack.append(str(int(eval(expression))))
continue
stack.append(t)
return stack.pop()
wouldn't this result in more overall comparisons?
Using eval is quite interesting. I rarely use it myself.
the use of 'eval' is not secure in the real world. if the expression can be controlled by a user facing the application, it can be crafted into a malicious input and will be run as a Python expression.
@@deepb5204then sanitize your input
Note that using a//b in python is not the same as using int(a/b). Double slash is floor division which will also round down with negative numbers. int(a/b) will round toward zero
That was pretty useful. Thanks for explaining it .
and round() in python rounds to nearest even number
round(5.5) -> 6
round(4.5) -> 4
The explanation is so good I understood the whole algorithm just by watching till 2:59😂
Another solution would be to define a recursive function `evaluate(stack)` that calls itself when another operator is encountered. You'd effectively still be using the stack data structure, only that your stack is the call stack's stack frames!
That was the solution I came up with on my own. I thought it was clever but it also looks way more complex compared to this solution. On the other hand my memory came through in the top 98.5% so it's clearly a good approach on that front lol
I love your videos. Minor issue was the explanation of popping the stack to assign values to a and b. You say that we want to “subtract the one that was popped second from the one that was popped first”. I believe you just mixed up the words, but in case others got slightly confused, b actually gets the value that is popped first and a gets the value popped second. This is clear if you take an input example [2, 1, -], which you actually discussed at 4:30 in the video, this would be 2 - 1. Therefore you would want to subtract the one popped first from the one popped second. And in python, because tuple unpacking is done right to left, b did indeed get the first popped value, so your solution is still valid despite mixing up the words.
how did you add right bracket using keyboard shortcut at timestamp 7:28 ?
This could have been a good opportunity to introduce lambda syntax:
```
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operatorMap = {
"+": lambda l,r: l + r,
"*": lambda l,r: l * r,
"-": lambda l,r: l - r,
"/": lambda l,r: int(l / r),
}
stack = []
for token in tokens:
if token in operatorMap:
right = stack.pop()
left = stack.pop()
token = operatorMap[token](left, right)
stack.append(int(token))
return stack.pop()
```
Clean!
Thank you! I like this solution better :) One suggestion: for integer division in python you can use a // b instead of int(a / b)
@@vasudhajha9115 Almost! The spec includes this note: "Note that division between two integers should truncate toward zero." a//b will always truncate downwards so it does not work for negative operands.
@@evannoronha3261 Oh nice. I learned two new things from your answers :) Thanks!
can you please provide leetcode lists of 150 neetcode Qs
should the space complexity be O(1) since at any point in program execution we are going to store at most 2 values ?
I agree
I came with my own solution for this question (felt very proud). But my solution is not even half efficient as yours. Thanks for sharing.
No need to do the a, b to do a swap for subtraction. Worst case every operator is “-“ and you made new a,b objects each time in the for loop.
Instead notice that “b - a” is equal to “-a + b”.
Thus you can write it in one line with no a and b needed:
stack.append(-stack.pop()+stack.pop())
Likewise, we can assume this is a valid RPN per the problem description, which your solution correctly assumes. Thus we can avoid the temp a,b for division as well using the 0 and 1 index for denominator and numerator respectively.
Thanks for the videos. Only trying to help simplify things.
nice trick!
I have not tried this one, but if the statement is always valid, would it work if we don’t use stack but just 2 number var?
First 2 tokens always assign to 2 int var.
Next is operator, apply then assign to int1.
Next is number, assign to int2.
Repeat the above 2 for every subsequent operator & number.
Return int1 value.
"1 1 1 1 + + +" this is a valid statement so unless you backtrack in the input I dont think you can solve it with O(1) space
Can anyone explain why I cannot use b//a to substitute int(b/a) ? I still got 0 from b//a but cannot pass below test case.
Input
tokens =
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output
12
Expected
22
for negative operations, // will round downwards (i.e -1.2 will round to -2) while the spec says it should round closest to zero (so it should round to -1 in this case). You use int(b/a) for that.
i believe truncation or something regarding division changed from python to python3. try your solution with python3 and not just python on leetcode
what's the difference in int(a/b) and a//b in python3? I used the latter one and it was wrong. Searched on stackoverflow but still confused
a//b rounds the float number to the floor value. For example 22//7 is 3.14 so it will be rounded of to 3
so we know that the array must have at least 2 integers before a division or plus or minus or times operator?
thank you so much, your explanation that very easy to understand this problem
I felt the problem is very hard until I saw this video.
Why you still can + - * / after you pop the number? Isn't a number vanish?
Thank you. This was really helpful
Curious as to how this works since the input values in the array are strings and there's no sort of type casting happening. ("2" * "2") for example should fail.
The casting is being done in the else block of the code -- stack.append(int(c))
When I copy your code from git hub I'm getting a failing case on Leetcode, just a heads up.
Hmm, I tried it and it's working for me now. Maybe there was an extra indent when you pasted
Same here
@@loraigwe9285 Are you trying to Java code or Python?
@NeetCode python
it passes in python3 but not in python2. i don't know why though.
at 5:13, you are adding from the right side and popping from the left, that has became a queue, and not a stack,
Delightful explanation as usual! :)
I solved this problem by making a dictionary with the values being the operators and checking to see if c = an operation in the dictionary. If it does pop right pop left then left (insert operant) right =
I think you need to strongly emphasize the correct way to approach the division and what it means to round towards zero. I'm assuming many people in the comments are having trouble between floor division and truncating. I think talking about this conceptually would help many of us especially if coding it up in a different language
this problem could be renamed: implement basic calculator
you will find that in trying to implement a basic calculator to parse a string, it is much easier to do it with prefix notation isntead of infix ( + a b vs. a + b). at that point you are doing reverse polish notation as the problem specifies...
I like to avoid the "elif" statements by storing the operators in a dict (the deque can ofc just be a list):
d = {"+": operator.add, "-": operator.sub, "/": operator.truediv, "*": operator.mul}
l = ["+", "-", "*", "/"]
def reverse_polish_notation(tokens):
s = deque()
for token in tokens:
if token not in l:
s.append(int(token))
else:
second, first = s.pop(), s.pop()
s.append(int(d[token](first, second)))
return s.pop()
If I am using javascript what can i do when declaring [a, b] ? I try to do const [a, b] and const [c, d] so avoid having the same variable declaring twice. Its there a better way to do this? Thanks a lot for the video as always! learning so much!
If you are declaring the variables inside different if statements then it's fine, variable [a, b] will only be scoped for that particular code block
For some reason solution was not working, it works if you convert b in the / case to a float using float(b)/a.
Was running into the same issue. Do u know why this happens?
Please introduce DSA and DP playlist so we can get all the concepts as well before practicing question.
+1
+1
+1
you didnt explain the second example and third one?? they are quite complex and they also needs to be decoded.
please do Next Permutation, I think this question bothers lots of us!
Can someone tell me that why are we subtracting number that was popped 2nd with the number that was popped first? How do we know that the 2nd popped number is the biggest of them.
I know it's long time when you commented this but I will explain.This is becouse we have something like 5 4 - and we want to do 5-4 becouse this is representation for reverse polish notation.We have 2 numbers and this 2 numbers is in relation with this first sign.
When we push on stack that means we go over array and push it like first me push 5 [5] ,after we push 4 and this is how look like list [5,4] and when we do .pop() this first number will be 4,second pop is 5 and now you can figure out.
Does not work in Python3. It keeps giving me ValError.
for anyone debugging, you have to do int(b / a) because b // a will not work!
spent like 15 mins debugging this error loll
awesome explanation!
Would this be doable in O(n) instead of O(2n)? Yes I know technically they're the same but practically they aren't. The way I have it figured in my head is that you could store the first digit of the array. Then every two elements after would be a digit and an operator. This would let you iterate through the array only once.
My other instinct to solving it would have been with leading/trailing pointer style. Trailing pointer to keep track of the numbers, leading pointer to find the operators
They gave an incomplete example of RPN. There is no guarantee of alternating digits and symbols.
123+- = 1 - (2 + 3)
why are you talking about O(2n), the array is iterated only once, so it is O(n) :/
@@frankl1 to be fair, NeetCode said it ran in O(2n)...
@@ChrisCox-wv7oo its between 1n and 2n
We can do it in place and return that last index value as result
0:55 Yeah I think it does
best stack problem everrr
Doesnt work.. misses on the last test case
Not code yet, but my solution before watch this video is to use pointers to have time complexity O(n) but space complexity is O(1).
I am wrong, using pointers will still need O(n) space if there are multiple complex expressions, which become operands of outer operator. Therefore, using stack is the best solution.
How can you pop if the stack is empty?
Stack never be empty becouse they clear this edge case(and other) every input in problem is good.
Everything what you need to do is to do this callculation on polish way :)
thank you sir
Wait but you don't need a stack, you can just make an inOrder traversal by popping the values from the end of tokens
the code doesn't pass one test case
Thanks
thanks goat
for subtracting can't we multiply -1 to the result in the default order?
Copying this comment from Leetcode for anyone confused about int(b / a) and why (b // a) doesn't work. Credit to user A_R_K for the comment.
"// is the floor function. / is the divide function.
By definition floor function would round the number to the smallest integer lesser than or equal to it. Hence, -17//6 is -3. This is because -3 is the smallest integrer lesser than or equal to -2.833..
One should ideally use int() to truncate the decimals."
Genius!
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for t in tokens:
if t not in '+-*/':
stack.append(int(t))
else:
v2, v1 = stack.pop(), stack.pop()
if t == "+":
stack.append(v1 + v2)
elif t == '-':
stack.append(v1 - v2)
elif t == '*':
stack.append(v1 * v2)
else:
stack.append(int(v1 / v2))
return stack[-1]
Seems like a queue is needed here instead of a stack
If the stack will always have at most 2 elements, the the space complexity is technically O(1) no matter how large the input array, it will always be constant. Right?
it can have more than two elements
i have no clue why I thought RPN was so much harder than it really is
Thanks. A more terse way of writing this :
'
def evalRPN(self, tokens: List[str]) -> int:
ops = {
'+' : (lambda a,b : a+b),
'-' : (lambda a,b : a-b),
'*' : (lambda a,b : a*b),
'/' : (lambda a,b : int(float(a)/b))
}
stack = []
for c in tokens:
if c in ops:
b, a = int(stack.pop()), int(stack.pop())
stack.append(ops[c](a,b))
else:
stack.append(int(c))
return stack.pop()
This really helped, the problem looked unsolvable at first to be honest 😊
GOAT
Will you post code in C or Java also🥺 either in video or atleast in description/website 🥺
Dude, you didn't try 847?
I found a way to improve the time complexity by using the operator library.The logic is still the same but cut down the runtime by 50%
import operator
class Solution(object):
def evalRPN(self, tokens):
"""
:type tokens: List[str]
:rtype: int
"""
stack = []
op = {
"+": operator.add,
"-": operator.sub,
"*": operator.mul,
"/": operator.truediv
}
for x in tokens:
if x in op:
a,b = stack.pop(), stack.pop()
stack.append(int(op[x](b,a)))
else:
stack.append(int(x))
print(stack)
return stack[0]
Is there any channel who do like this in java or C
I have implemented the same problem in Java. But youtube is not allowing me to add a link to implementation of it in comment so I have requested @neetcode, to post a link of my java implementation to here as well.
@@neeldesai108 thank you!❤️
delicious
us
Polska gUrom! :D