Roman to Integer - Leetcode 13 - Python

[@zexisun1243]

I love how the negative numbers is applied here(when small numbers are being put before the largers), it is very inspiring

[@haru5214]

Hey I love your positivity and way of thinking ❤

[@Historyiswatching]

This is easy?! Oh noooooooo I'm screwed

[@arnaldoramirez4279]

im felling you my brother 🤣

[@one_step_sideways]

Just learn your language and data structures more. And it takes time to become confident when doing interview questions. How are you doing so far btw?

[@turell-tate]

update us on your progress 😂

[@abuchikingsley124]

😂

[@o__bean__o]

My code only passed in Case 1 and Cast 2 😂 case 3 😵

[@abhishekr700]

Nobody highlights this so clearly that there can only be 1 symbol on the left for substraction case, you just made it clear !

[@Phi_AI]

Great solution, NeetCode. Your videos help a lot. Here is another solution: trick is to always add roman values, but if previous roman value is smaller than next one, subtract it twice. (because we already added it on the previous step). here is the code: roman = {} roman["I"] = 1 roman["V"] = 5 roman["X"] = 10 roman["L"] = 50 roman["C"] = 100 roman["D"] = 500 roman["M"] = 1000 int_sum = roman[s[0]] for i in range(1,len(s)): if roman[s[i-1]] < roman[s[i]]: int_sum -= 2*roman[s[i-1]] int_sum += roman[s[i]] for example, "XC" which is 90 will be computed as step 1: int_sum = roman[s[0]] (10) step 2: since roman[s[1]] > roman[s[0]], int_sum = -2*roman[s[0]] + int_sum + roman[s[1]] (- 2*10 + 10 + 100)

[@riyatiwari7178]

You're amazing, thank you for the lucid explanation, breaking down how to reach the problem. 😊

[@abuchikingsley124]

Did this yesterday. My solution was too complex, but faster. This is way easier to grasp.

[@DarklordMcsweetTeaSipper]

I never thought I would be able to understand how this problem worked, thanks so much.

[@jideabdqudus]

I watch this channel while eating. Keep it going mate :)

[@xReisk]

Bro I just wanted to take a look how others solved this and Im so happy my solution its close to yours, literally one/two lines differently. Happy to see that I was able to come with a simple solution like you, good minds think alike 😁

[@xhenex7622]

crange

[@xReisk]

@@xhenex7622 u ok mr pro?

[@zerosandones7547]

You really know how to clear the confusion. THANK YOU!

[@cometomatt]

this is the best explanation of this problem. clean and simple.

[@alf8988]

If you keep a prev variable you can simply add the value of the numeral each iteration and substract previous twice if it is smaller than the current numeral

[@GoziePO]

I tried that, but I think this method is a bit cleaner/more straight forward.

[@alifeoflaurels]

hey, i understand this concept but what about the very last number in the index? how does the code account for that since there's no subsequent number to compare it with? been stuck in leetcode for a while

[@sharkPause1]

That's what the else statement is for the if statement runs when all their conditions are true if not then run the else statement since we're at the last character, the i+1 condition returns false because i+1 is bigger than the length of the string, so we run the else statement hope that clears things up

[@alifeoflaurels]

@@sharkPause1 thanks it really helps!

[@bleachie]

@@sharkPause1 except that would actually raise an indexError: index out of bounds. I know because I ran into this error, and my solution was to check up to len(s)-1 and then anded and if statement check and handle the end of the string

[@sirmidor]

@@bleachie No, that would not happen if you use the exact code in the video. This is because conditional expressions made with the boolean keywords not/and/or 'short-circuit' in Python. If you have a combined conditional expression like 'i + 1 < len(s) AND [anything else here]', if the first part of the expression evaluates to False, the second part will not be executed. This is why the code works: When i = len(s) - 1 (the final value that range(len(s) will yield), the first condition ('i + 1 < len(s)') is not True and therefore the second part does not execute, avoiding an IndexError. You can test this with a simple example: Dividing by 0 in Python always raises a ZeroDivisionError if executed, but the following code will not raise it: '1 > 2 and 5 // 0' Because 1 > 2 is False, the second part, which would throw an error, is never executed. This is why the order of your conditional expressions matters. If you would run '5 // 0 and 1 > 2', it will always raise an error.

[@joonghokim2449]

Another way to solve this is to go through the string from the end and in reverse and keeping track of the previous number. If the current number is smaller than the previous, you subtract from the result, else you can just add to the result. I find it a little easier to implement since you are not looking ahead at the next value, so there is no need to check if the next value exists within the bounds.

[@koearnn3219]

to understand better you have to understand the outputs of each instruction, check the outputs of str="XVIII" for i in range(len(str)): #print(i) #print first #print(str[i]) #2nd str = "XVIII" for i in range(len(str)): print(f"i: {i}, c: {str[i]}") and you will get it sooner, basically is the explanation of comparing 2 chars and compare the value with the map and check that is >1 letter, cant be 0 that's why the line 11

[@ShaikSharmila-tq6bc]

I am not getting output for the folllowing string i.e MCMXCIV If i use your method then the answer is 1990 But the answer is 1994 How????? Please reply

[@atlasatlantis8447]

As a beginner, this is what I tried. I am wondering, is there a way to do it my way? With indexes in if statements? Roman = ['I', 'V', 'X', 'L', 'C', 'D', 'M'] I = str(1) V = str(5) X = str(10) L = str(50) C = str(100) D = str(500) M = str(1000) if D[ ] < M[ ]: D = str(-500) else: D = str(500) print(M,D) print(D,M)

[@abhineetsingh6720]

concise, no bs. very good

[@pekarna]

Small adjustment: We do not need to do the lookahead. Instead, we can keep the last value added, and if it is smaller than the current, we can substract it twice. Imho that's faster than looking into each character twice, looking into a hashmap twice, and check the current position against the end. var int = 0 var lastVal = 0 for (c in s) { val curVal = conv[c]!! int += curVal if (lastVal < curVal) int -= lastVal shl 1 lastVal = curVal }

[@GoldAMG]

This won't work if there are duplicate smaller values before a larger value.

[@叶文琴-x7s]

@@GoldAMG there can only be one

[@abuchikingsley124]

Yeah. Implemented something similar. Repeated symbols and special cases like IX, XC etc were computed in a single loop and i is moved 2 or 3 places forward.

[@a4rdev]

I feel so dumb, I can't figure out how to solve these on my own so I just look up the answer and then it makes sense. The only way I'll pass an interview is by memorization at this point.

[@one_step_sideways]

No, it's just that you didn't learn or get accustomed to some of the complex data structures like hashmaps/dictionaries in Python. I knew I needed to use some kind of dictionary for this one (i mean, it's literally explicitly hinted at in the question with the keys and values) and that was indeed the case. So all you need to do is get accustomed to data structures like knowing when to use which and the rest of your logic would be a simple "if-else" statement. It's just a matter of taking some more time to learn Python or other language that you use.

[@wokeclub1844]

@@one_step_sideways Thanks for the reassurance man.

[@adityavardhanjain]

I understood the logic of the Roman numerals but didn't really understand the execution. Thanks for the vid.

[@geekydanish5990]

this is more intuitive i feel class Solution: def romanToInt(self, s: str) -> int: romans = {'M': 1000, 'D': 500 , 'C': 100, 'L': 50, 'X': 10,'V': 5,'I': 1} prev,running_total = 0,0 for i in range(len(s)-1,-1,-1): curr = romans[s[i]] if prev > curr: running_total -= curr else: running_total += curr prev = curr return running_total

[@chaitanyakhot3842]

I had a similar solution to yours but I iterated the loop backwards. Here's my solution: class Solution: def romanToInt(self, s: str) -> int: roman = s.strip("") convert = {"I" : 1, "V" : 5, "X" : 10, "L" : 50, "C" : 100, "D" : 500, "M" : 1000} num = convert[roman[len(roman) - 1]] for letter in range(len(roman) - 2, -1, -1): if convert[roman[letter]] < convert[roman[letter + 1]]: num -=convert[roman[letter]] else: num += convert[roman[letter]] return num

[@jindaldreams]

Thanks Neetcode for awesome explanations. Where can I find the code snippet to your solutions ?

[@ayomikunogunjuyigbe1286]

Great video, really helpful! I am still confused about something, why are we maintaining (res=0)?

[@CharounsonSaintilus]

He's just initializing the result he'll eventually return to zero. Notice that result is being added to or subtracted from, so we need to initialize before we can do that.

[@siddhantsehgal9900]

Can you go over this one? (1878. Get Biggest Three Rhombus Sums in a Grid)

[@LordPython-xi3yw]

damn the way this question was explained in the leetcode was far more complex than the solution

[@Carmadon100]

your videos are amazing. Hope I can pass the screening!

[@izrafaturrahman9174]

Great video, however I think the problem link in the description leads to a different problem.

[@NeetCode]

Sorry bout that, should be fixed.

[@izrafaturrahman9174]

@@NeetCode No problem, keep up the good work!

[@wokeclub1844]

Funny how I stumble upon this video exactly a year after it was posted.

[@sepia2008]

Lol, I did it kinda the same. Basically I had a dictionary but then i converted the string given to a list and then created a new list of the values of that given string so instead of XIII i had [10 1 1 1] and then did the addition for this particular list :) proud i made it by myself

[@deeptimayeemaharana2448]

i dont understand if we swap the if-else sequence then we get errors, can someone explain?>

[@muhammadtaimoor876]

Can be because of short circuiting. (if an AND sees a False early, it won't check the next expression, it will just return False)

[@suraj-ej6oq]

You are awesome👍👏😊 please continue like this, this was really helpful for us

[@andrewchen3247]

I have a quick question. Since you are only adding and subtracting in the for loop and incrementing by 1 each time, wouldn’t that cause the program to recount pairs? For example, wouldn’t IVI be counted as 4 + 5 + 1 instead of 4 + 1 because the loop is checking each letter, regardless of if it has already appeared in a pair and has been counted already?

[@idqnnez1338]

I understand how you think, but this is how it would be: -1 + 5 + 1 Since the program doesn't know that IV is for, it knows that a "I" before a "V" is "-1".

[@picture_of_a_swan]

Thank you for this explanation! I didn't even think to use hashmap for some reason, so my code was originally stupidly long (I used a switch case to assign the roman numbers🤦‍♂)

[@jigyarthjoshi6002]

hey same i did. But the switch case is better because it can also find if the roman number is valid or not unlike this code. My solution is this -> class Solution { public: int romanToInt(string s) { int count = 0, n = s.size(); for(int i = 0; i < n; i++){ switch(s[i]){ case 'M': count += 1000; break; case 'D': count += 500; break; case 'C': if(s[i+1]== 'M') { count += 900; i++; }else if(s[i+1]== 'D'){ count+=400; i++; }else count += 100; break; case 'L': count+= 50; break; case 'X': if(s[i+1]== 'L') { count += 40; i++; }else if(s[i+1]== 'C'){ count+=90; i++; }else count += 10; break; case 'V': count+=5; break; case 'I': if(s[i+1]== 'X') { count += 9; i++; }else if(s[i+1]== 'V'){ count+=4; i++; }else count += 1; break; } } return count; } };

[@OwenWu-f9t]

so this question assumes that we can't have LD? because D has a larger value than L, but then you don't subtract 50 from 500.

[@Punibaba1]

You should consider doing Integer to Roman.

[@premraja55]

Great explanation!

[@Avuvos]

great video as per usual! can you do 542. 01 Matrix, please? :)

[@ninadpanchal7086]

we making out of rome with this one!!

[@Morimove]

Please provide cpp and java solution also. it is really helpful

[@Joelvarghese6]

The code I wrote was 40 lines, you solved it in 17 lines...

[@UndertakerPth]

I know that feel bro...

[@kingsleyatuba]

Can someone please tell me why this doesnt work for line 11: if values[s[i]] < values[s[i+1]] and i+1 < len(s) Since it's an 'and' operator, should it matter which one comes first?

[@Nick-zw7gg]

I found this interesting too and I don't know why.

[@longmai6888]

Since it's an if statement using 'and' operator, you need Both conditions to be TRUE in order for line 12 to be executed. And, it shouldn't matter which statement comes first since you would need to satisfy both. I hope that explains it!

[@shrijeet.gaikwad]

No

[@nicolassilvadossantos9688]

You need to validate whether there is i+1 first, or the first statement will throw an error accessing a value that doesn't exist.

[@brahimelhoube9532]

Great channel 🎉

[@deshawnbattle7510]

Great video!

[@milanpatel6240]

You are too good man

[@mr.carguy6271]

what is inbounce said by neetcode ?can someone explain me?

[@alishahbaz6062]

Great explanation! the time complexity will also be O(1) because the largest possible numberal will have 15 letters in it, and then we will only have to iterate 15 times. So O(15) can be considered O(1)

[@anshgupta9880]

It will be O(n)

[@xtunasil0]

+ the way he wrote the code would prevent that: range(len(s))

[@tommyw5332]

I did it recursively for the funs.

[@komasdfg]

oh man, the front is always bigger than the back. Why did my brain not notice that. Thanks.

[@joaovitorsoares9119]

but is 999 CMXCIX? can we do this IM?

[@saurabhbarasiya4721]

thanks for sharing this

[@amrholo4445]

Thanks a lot sir

[@fuyeekee]

if I try the example of IM gets me the 999, is that correct?

[@NeetCode]

yeah, i think so

[@semilshah8252]

if i+1 < len(s) and roman[s[i]] < roman[s[i+1]]: from above line i didnt understand why i+1 < len(s) is written can somebody explain??

[@maratheshrutidattatray2045]

i + 1 < len(s) helps the iteration to stop when the len of s is reached. lets say len(s)== 4 you want your loop to go 4 times but not 4 + 1 as its beyond the bounds.. I hope I made it clear! So as fas as i + 1 < len (s ) the loop is valid.

[@kingsleyatuba]

@@maratheshrutidattatray2045 Can you please tell me why this doesnt work for line 11: if values[s[i]] < values[s[i+1]] and i+1 < len(s) Since it's an 'and' operator, should it matter which one comes first?

[@kingsoonkit9234]

Me thinking that my 140+ lines of crap code was super smart, then i saw this video :'D

[@bisanghoul3632]

Doesn’t the hashmap in this case increase the space complexity? i inow there are only 5 items in it, but still why the extra space when u can use a switch for example?

[@iloveyourodman7023]

im so confused man, WHAT is the problem. like WHAT is the question? i don't see what they're asking us to do

[@atlasatlantis8447]

The biggest problem I am having with this, is there is no question! The problem dose not ask me a question. What the hell dose the problem want? Do they want us to write a program that converts Roman numbers to inters? I assume this, but the problem dose not even ask you a question.

[@Eltopshottah]

Who’s comes up with this I need to have a chat with them 😂

[@gouravkumarshaw5467]

Great!!

[@SoCalCycling]

c++ 15ms 6.1mb

[@JackMari]

BTW "IM" is invalid, 999 = "CMXCIX"

[@one_step_sideways]

He addressed that in the video

[@ombothre2350]

1:57 Us

[@lukaszplachecki8723]

🎉

[@aboalabds]

IIIX will return wrong result need to add another elif class Solution: def romanToInt(self, s): roman = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000} res = 0 for i in range(len(s)): if (i+1 < len(s) and roman[s[i]] < roman[s[i+1]]): res -= roman[s[i]] elif (i+1 < len(s) and roman[s[i]] == roman[s[i+1]]): res -= roman[s[i]] else: res += roman[s[i]] return res

[@shinduratmoro2282]

yea but isn't IIIX is invalid? you can't put multiple lesser value behind greater value. if you wish to have 7 as a result, the roman should be VII instead of IIIX.

[@jvfr-]

this is hard

[@krateskim4169]

nice

[@lakshayrohilla873]

This solution wont work for "II"

[@NeetCode]

What will it return?

[@oladipotimothy6007]

Watch out for case sensitive romans. Solution works!

[@sreeru]

Easy for who? Newton?

[@BurhanCerit]

nice..

[@SiarheiAkhramenia]

There is no such thing as IM in Roman numbers. Just an inaccurate example.

[@js8597]

im trying this on my own and cant figure out why my solution doesnt work correctly. More interested in what is wrong with my logic than this person's solution. class Solution(object): def romanToInt(s): romans = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000} total = [] result = 0 for l in s: total.append(romans[l]) for num in total: number_totheright = total[total.index(num)+1] try: if num < number_totheright: result -= num else: result += num # last number wont have a 'number_totheright' except IndexError: result += num print(result) Solution.romanToInt('CMXC')

[@atlasatlantis8447]

This video is poor quality for learning. How about showing us how to run the code? As a beginner, I want to learn how to actually use the code. Running what you have, dose nothing.

[@bluemoon7890]

"I am getting this error, someone plz help" TypeError: None is not valid value for the expected return type integer raise TypeError(str(ret) + " is not valid value for the expected return type integer"); Line 37 in _driver (Solution.py) _driver() Line 44 in (Solution.py) During handling of the above exception, another exception occurred: TypeError: '

[@srigkt]

"III" "LVIII" "MCMXCIV" "MCV" "CMXCVIII" - results for the last two roman letters are incorrect as per leetcode. here is the code i put in for the same. Can u please help explain why? Input: "III" "LVIII" "MCMXCIV" "MCV" "CMXCVIII" Output: 3 58 1994 905 798 Expected: 3 58 1994 1105 998 ################# class Solution: def romanToInt(self, s: str) -> int: roman={"I":"1","V":"5","X":"10","L":"50","C":"100","D":"500","M":"1000"} res=0 for i in range(len(s)): if i+1

[@tarunmuppuri1106]

class Solution: def romanToInt(self, s: str) -> int: HashMap = {"I":1,"V":5,"L":50,"X":10,"C":100,"M":1000,"D":500} ans=0 for i in range(len(s)): if i+1

[@tarunmuppuri1106]

In hashmap u should not give numbers in string.While compariing it takes ascii values which leads to wrong interpretution

[@srigkt]

@@tarunmuppuri1106 it solved thank u

[@zara4257]

why does everyone keep saying it's easy? 🥲🥲

[@sunithakumari333]

Becoz it's easy if u know school math related to numbers and their different notations 😄