LeetCode #13 Solved: Roman To Integer

Roman to Integer is quite an interesting problem on LeetCode, with an easy trick to solving it, as long as you understand how Roman numerals work.

When it comes to Roman numerals, you need to know that if a numeral is followed by another one larger than it, then you need to subtract the smaller one from the total (which is initially 0). Otherwise, you just need to add it to the total. Let's take a look at an example from LeetCode to understand better.

Input: s = 'IV'

If you're well-versed in Roman numerals, then you can immediately guess that this translates to 4. But there's a reason why.

From the lookup table given to us on LeetCode, we know that 'I' means 1 and 'V' means 5. And since a larger number (5) comes after the smaller number (1), you have to subtract the smaller one from the total, i.e., 0 - 1 = -1 and then add 5 to get -1 + 5 = 4. However, if the string was 'VI' instead of 'IV', you'd just add the two equivalent integers to the total, i.e., 0+5 = 5 and 5+1 = 6.

Let's now take a more complex problem:

Input: s = "MCMXCIV"

In this example, we're going to traverse two Roman numerals at a time, and work out what this number is in digits. Remember, in the two chosen numbers, if the value of the current numeral is less than the value of the next numeral (like C (100) < M (1000)), then we subtract the corresponding value of the smaller one from the total (total - 100). Else, we just add the corresponding value of the larger number to the total. Here's a table to make the concept clearer:

In the last iteration, our comparison operation is V < undefined which gives us false. So instead of subtracting the number from the total, we're just going to add it. If you understand this table, then you've pretty much solved the problem. All that's left to do is put all of this into code.

Translating logic into code

Let's first initialize a variable total to 0, and make our lookup table. The total will hold the total equivalent of the Roman numerals given to us as string.

let total = 0
 const lookupTable ={
     M: 1000,
     D: 500,
     C: 100,
     L: 50,
     XL: 40,
     X: 10,
     V: 5,
     I: 1
 }

Then, for the length of our given string, we're going to traverse two numerals at a time using the two-pointer approach. We'll initialize our current and next pointers and if the value of the current numeral is less than the value of the next numeral in the string, we're going to subtract the value of the current pointer from the total. Otherwise, we'll add the value of the current numeral to the total. In code, this means:

for(let i=0; i<string.length; i++){
     let curr = s[i]
     let next = s[i+1]
     if(lookupTable[curr]<lookupTable[next]){
         total = total - lookupTable[curr]
     } else{
         total = total + lookupTable[curr]
     }
 }

Now, you just need to return total. Putting all of this together, we get:

var romanToInt = function(s) {
let total = 0
 const lookupTable ={
     M: 1000,
     D: 500,
     C: 100,
     L: 50,
     XL: 40,
     X: 10,
     V: 5,
     I: 1
 }
 for(let i=0; i<s.length; i++){
     let curr = s[i]
     let next = s[i+1]
     if(lookupTable[curr]<lookupTable[next]){
         total = total - lookupTable[curr]
     } else{
         total = total + lookupTable[curr]
     }
 }
 return total
};

Number to Roman numerals

The Number to Roman numeral problem on freeCodeCamp also follows a similar approach, but instead of using the two-pointer approach, our work is made easier thanks to the modified lookup table that takes care of all the special cases. i.e., 900, 400, 90, 40, 9, 4. If the lookup table didn't contain these values, then we'd have to apply some logic similar to the one used above and come up with the corresponding Roman numerals for these values.

Since we already have all the values, all we really need to do is code an accumulator, a variable that'll store the string of Roman numerals corresponding to the number given to us. So let's start by first copying the lookup table and initializing the accumulator:

 const lookupTable = {
    M: 1000,
    CM: 900,
    D: 500,
    CD: 400,
    C: 100,
    XC: 90,
    L: 50,
    XL: 40,
    X: 10,
    IX: 9, 
    V: 5,
    IV: 4,
    I: 1,
  }

  let accumulator = ''

Next, we just need to find the largest possible number from the table that we can subtract from our given number and add its corresponding key (the Roman numeral) to our accumulator. To do that, we'll first fetch a value from the table, and as long as it's less than or equal to our given number, we'll subtract it. Otherwise, we'll continue traversing the lookup table till the end and just return the accumulator. Here's a table to make things clearer:

If we translate this into code, we get:

for(let key in lookupTable){
    const numberVal = lookupTable[key]
    while(numberVal <= num){
      num -= numberVal
      console.log(num)
      accumulator += key
    } 
  }

Now, all you need to do is return the accumulator.

return accumulator

And that's pretty much it. You now know how to convert Roman to integer and integer to Roman. Like always, you can find the entire solution on my GitHub or run it directly on OneCompiler. If you have any questions or confusion, just let me know!

---

Solving Leetcode problems is hard enough as it is, and add to that the difficulty of finding an in-depth solution that explains everything, and you find yourself stuck. Some videos are hard to follow, some don't explain the basics, while others leave you with more questions than answers. In this series, I break down Leetcode problems one at a time and walk you through a step-by-step solution. Have a question you can't understand? Send it to me, and I'll explain it in detail. And don't forget to subscribe to my newsletter to get my articles directly into your inbox!