How to solve LeetCode problem #13: Roman to Integer

Javascript – LeetCode problem #13 Roman to Integer

In this problem, we need to create a method for converting Roman numerals into Integers (i.e. MMXXIV => 2024; III => 3; IX => 9; …). Read the full problem here.

Pattern – Deconstruct the Roman numeral

The key to solving this problem is understanding the construction pattern of Roman numerals:

1. They are read as a sum of their parts and are generally written largest to smallest (thousands, hundreds, tens, singles)
   • => in simple cases, you could just add each Roman digit together
     • 2023 = MMXXIII = 1000+1000+10+10+1+1+1
2. however, there is an exception where a number in a threshold position is represented by subtraction:
   • I = 1; II =2; III =3; IV=4; V=5
   • V=5; VI = 6; VII=7; VIII =8; IX =9; X =10
   • X=10; XX=20; XXX =30; XL =40; L = 50
   • 2024 = MMXXIV = 1000+1000+10+10+(5-1)

In summary, we need to look at each letter of the Roman numeral and compare it to the following letter to determine if addition or subtraction applies.

Solution – Roman to Integer

For my solution, I first setup a map that maps each Roman numeral letter to its integer value. We will reference this later.

const romanMap = new Map([
    ['I',1],
    ['V',5],
    ['X',10],
    ['L',50],
    ['C',100],
    ['D',500],
    ['M',1000]
]);

Next, we need a way to look at each letter of the Roman numeral input and its following letter to determine whether addition or subtraction should apply. I set up two pointers (p1,p2) and started a while loop. For each letter (s[p1]) and its next letter (s[p2]), we can get their integer value (val1,val2) from the map to compare them.

Here’s how I am evaluating them:

• val1 > val 2 | e.g. 1000>100 OR val1==val2| eg. 100==100
  • this means we are moving through the construction pattern in the expected way (from largest to smallest). The subtraction rule does not apply here => add val1 to the result, move pointers 1 ahead
• val2==undefined
  • this happens if p1 reaches the last letter of the Roman numeral, since there is no comparison to do => add val1 to the result, move pointers 1 ahead (in this case that will break the loop)
• else (val1 < val2) | e.g. 1<10
  • this means we have found a threshold value that needs to be constructed via subtraction => add (val2-val1) to the result, move the pointers 2 ahead

Example: MMXXIV (2024)

result = 0
M==M || result + M (1000) = 1000
M > X || result + M (1000) = 2000
X==X || result + X (10) = 2010
X > I || result + X (10) = 2020
I < V || result + V-I (5-1) = 2024

Here’s the full code:

const romanMap = new Map([
    ['I',1],
    ['V',5],
    ['X',10],
    ['L',50],
    ['C',100],
    ['D',500],
    ['M',1000]
]);

var romanToInt = function(s) {
    let p1 = 0;
    let p2 = 1;
    let result = 0;

    while(p2 <= s.length){
        
        let val1 = romanMap.get(s[p1]);
        let val2 = romanMap.get(s[p2]);

        if(val2 == undefined || val1 > val2 || val1 == val2 ){
            result += val1;
            p1++
            p2++
        }
        else{
            result += val2 - val1;
            p1 = p2 +1;
            p2 = p2 +2;
        }
    }
    return result;
};

This is how I solved LeetCode problem #13 Roman to Integer in Javascript. See other LeetCode solutions