In this article, we will solve “Roman to Integer” problem. The details of the problem can be found here in LeetCode.

In LeetCode, the problem is labelled as easy, however, in my opinion, if you never saw this problem before and didn’t know much about how Roman numerals work, it could be hard to come up with the solution. The good news is that the implementation itself isn’t too hard so once you go through this article and understand the core concept, you will easily solve this problem when you see it again in the technical interview.

In this article, I will walk you through the code with JavaScript and also at the end, I have provided the complete code in Python too.

Before diving into the solution, please read the description of the problem in LeetCode page and understand the rule of the Roman numerals. Here are three important things to remember:

Roman numerals are usually written largest to smallest from left to right
There are six instances where subtraction is used
It is guaranteed that s is a valid roman numeral in the range [1, 3999]

Once you have read the problem and have some ideas of the Roman numerals, let’s take a look at the examples.

Examples

`III` returns `3`

I = 1
I = 1
I = 1

We are simply adding three 1 so it returns 3.

1 + 1 + 1 = 3

`LVIII` returns `58`

L = 50
V = 5
I = 1
I = 1
I = 1

All roman numerals here are largest to smallest from left to right, so we are just adding those numbers and it returns 58.

50 + 5 + 1 + 1 + 1 = 58

`MCMXCIV` returns `1994`

M = 1000
C, M = 900
X, C = 90
I, V = 4

For the first subtraction, because C is smaller than M but C is located left to M, we need to subtract it so M - C = 900 . The same principle applies to X, C and I, V. At the end, adding the numbers all up returns 1994.

1000 + 900 + 90 + 4 = 1994

Implementation in JavaScript

Here is the complete code in JavaScript.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  romanToInt(s) {
    let total = 0;
    let i = 0;

    while (i < s.length) {
      const currentValue = romanSymbols[s[i]];
      const nextValue = romanSymbols[s[i + 1]];

      if (currentValue < nextValue) {
        total += nextValue - currentValue;
        i += 2;
      } else {
        total += currentValue;
        i++;
      }
    }

    return total;
  }
}

Implementation steps

1. Create a hash table so that we can have instant access to it to find the corresponding number to the symbols.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

2. Create class and romanToInt method.

class Solution {
  romanToInt(s) {
  }
}

3. Initialise the total which we are going to return later in the function, and i for using in the while loop.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  romanToInt(s) {
    let total = 0;
    let i = 0;
  
    return total;
  }
}

4. Iterate with the while loop until the i which we will increment in each iteration is smaller than the length of s. We are going to use i to get each character of the given roman number.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  romanToInt(s) {
    let total = 0;
    let i = 0;
  
    while(i < s.length) {
  
    }
  
    return total;
  }
}

We are going to have two conditions:

when the numeric value of the current roman character is smaller than the next one
when the numeric value of the current roman character is bigger than the next one

and we are going to do the second first as it’s easier to understand.

5. So basically the second condition will be the else of the first condition and we are just going to find the numeric value and add it to the total. To get the current roman character, it will be s[i] and with that, we will access the hash table to get the numeric value of it, romanSymbols[s[i]].

Also we will increment i by 1.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  function romanToInt(s) {
    let total = 0;
    let i = 0;
  
    while(i < s.length) {
      if () {
      } else {
        total += romanSymbols[s[i]];
        i++;
      }
    }
  
    return total;
  }
}

6. Let’s cover the first condition which the numeric value of the current roman character is smaller than the next one.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  function romanToInt(s) {
    let total = 0;
    let i = 0;
  
    while(i < s.length) {
      if (romanSymbols[s[i]] < romanSymbols[s[i + 1]]) {
      } else {
        total += romanSymbols[s[i]];
        i++;
      }
    }
  
    return total;
  }
}

7. Subtract the current one from the next one and increment i by 2 because we want to move the pointer to 2 steps ahead as we have already done with both current and next character.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  function romanToInt(s) {
    let total = 0;
    let i = 0;
  
    while(i < s.length) {
      if (romanSymbols[s[i]] < romanSymbols[s[i + 1]]) {
        total += romanSymbols[s[i + 1]] - romanSymbols[s[i]];
        i += 2;
      } else {
        total += romanSymbols[s[i]];
        i++;
      }
    }
  
    return total;
  }
}

That’s all.

Just to make it easier to read, we could define the currentValue and nextValue but it’s just an optional.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  romanToInt(s) {
    let total = 0;
    let i = 0;
  
    while(i < s.length) {
      const currentValue = romanSymbols[s[i]];
      const nextValue = romanSymbols[s[i + 1]];

      if (currentValue < nextValue) {
        total += nextValue - currentValue;
        i += 2;
      } else {
        total += currentValue;
        i++;
      }
    }
  
    return total;
  }
}

One thing to note is with const nextValue = romanSymbols[s[i + 1]]; (line 18) will be out of array length and give us the undefined if the current pointer is at the end of the array. In JavaScript, the comparison with the undefined (line 20) will still work because it evaluates incompatible types with an operator to false. But in other languages like Python below, it will throw an error because the nextValue is out of range.

To make sure we satisfy this too, we need to re-write our code back to the previous one with one more comparison in the if statement.

const romanSymbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
};

class Solution {
  romanToInt(s) {
    let total = 0;
    let i = 0;
  
    while(i < s.length) {
      if (i + 1 < s.length && romanSymbols[s[i]] < romanSymbols[s[i + 1]]) {
        total += romanSymbols[s[i + 1]] - romanSymbols[s[i]];
        i += 2;
      } else {
        total += romanSymbols[s[i]];
        i++;
      }
    }
  
    return total;
  }
}

Python

Here is the complete code in Python.

roman_symbols = {
  "I": 1,
  "V": 5,
  "X": 10,
  "L": 50,
  "C": 100,
  "D": 500,
  "M": 1000,
}

class Solution:
  def roman_to_int(self, s: str) -> int:
    total = 0
    i = 0

    while i < len(s):
        if i + 1 < len(s) and roman_symbols[s[i]] < roman_symbols[s[i + 1]]:
          total += roman_symbols[s[i + 1]] - roman_symbols[s[i]]
          i += 2
        else:
          total += roman_symbols[s[i]]
          i++
    return total

Big O

Time complexity

Because the largest number of the Roman numerals is 3999 (MMMCMXCIX), the time complexity will be O(1). If there were no upper limit for the Roman numerals, it would be O(n) runtime.

Space complexity

There is no value increasing in size so it will be O(1) for the space complexity.