Roman to Integer

Q: What is the time complexity of Roman to Integer?

Both approaches read each character once, so the time is O(n) for a numeral of n characters. The extra space is O(1) , because the lookup tables have a fixed size. A numeral from 1 to 3999 has at most 15 characters.

EasyMath and simulation Hashing

+10

Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. The symbols are written from largest to smallest and added up, except in six subtractive pairs where a smaller symbol comes first and is taken away from the larger one: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900.

You get a valid Roman numeral s. Return the integer it stands for.

Function

romanToInt(s: string) → integer

sstring: a valid Roman numeral in capital letters
Returnsinteger: the value of the numeral, from 1 to 3999

Constraints

1 ≤ s.length ≤ 15
s contains only the characters I, V, X, L, C, D and M.
s is a valid Roman numeral for a value from 1 to 3999.

Examples

Input: s = "XXVII"
Output: 27
Explanation: XX is 10 + 10, V is 5 and II is 1 + 1, so the total is 27. No symbol is followed by a larger one, so every symbol is added.

Input: s = "CDXLIV"
Output: 444
Explanation: The numeral is three subtractive pairs in a row: CD is 400, XL is 40 and IV is 4, which makes 444.

Input: s = "MCDXCII"
Output: 1492
Explanation: M is 1000, CD is 400, XC is 90 and II is 2, so the numeral is 1492. Pairs and plain symbols mix freely.

Follow-up

Can you write the reverse, turning an integer from 1 to 3999 into its Roman numeral?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Most of a numeral is a plain sum, so the problem is spotting the six subtractive pairs. You can look them up as two-letter tokens, or use one rule that covers all six: a symbol worth less than its right neighbor is subtracted. Either way, one pass gives the answer.

Read subtractive pairs as tokens

Intuition

Read the numeral as a row of tokens: single symbols, plus the six two-symbol pairs IV, IX, XL, XC, CD and CM. Add up the token values and you have the number. MCDXCII splits into M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

Check for a pair before a single symbol, or the X of XC adds 10 and then 100. The check is safe: in a valid numeral a smaller symbol stands right before a larger one only inside one of these pairs, so every pair you find is real.

Each step consumes one or two characters and the tables have a fixed size: O(n) time, O(1) extra space.

Algorithm

Make one table for the six pairs and one for the seven single symbols.
Start at index 0 with a total of 0.
If the two characters at the index form a pair, add the pair's value and move the index by 2.
Otherwise add the single symbol's value and move the index by 1.
When the index passes the end, return the total.

def romanToInt(s):
    pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
    singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    i = 0
    while i < len(s):
        two = s[i:i + 2]
        if two in pairs:
            total += pairs[two]
            i += 2
        else:
            total += singles[s[i]]
            i += 1
    return total

Compare each symbol with the next one

Intuition

In each of the six pairs, the first symbol is worth less than the second, and the pair is worth the second minus the first. So you can drop the pair table and use one rule: subtract a symbol worth less than its right neighbor, add every other symbol. CM becomes -100 + 1000 = 900, the value the token reading gives.

In MCDXCII, C is followed by a larger D and X by a larger C, so the total is 1000 - 100 + 500 - 10 + 100 + 1 + 1 = 1492. The comparison is strictly less than: equal neighbors are added, which makes II 2. The rule is correct for the same reason as the tokens: a smaller symbol comes right before a larger one only as the first half of a pair.

One look at each character and one running total: O(n) time, O(1) extra space.

Algorithm

Store the value of each of the seven symbols.
Loop over the indices of s with a running total that starts at 0.
If the next symbol exists and is worth more than the current one, subtract the current value.
Otherwise add the current value.
Return the total after the loop.

def romanToInt(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        value = values[s[i]]
        # A symbol worth less than the one after it is subtracted, like the I in IV.
        if i + 1 < len(s) and value < values[s[i + 1]]:
            total -= value
        else:
            total += value
    return total

Pitfalls and edge cases

Using less than or equal instead of strictly less than. Then II and XX both come out as 0, because each first symbol is subtracted.
Reading s[i+1] on the last character, where it does not exist. Check i+1 against the length first, and always add the last symbol.
In the token version, trying single symbols before pairs. XC then reads as 10 + 100 = 110.
Forgetting that Lua and R strings start at index 1, so the last symbol is at #s or nchar(s).

Frequently asked questions3

What is the time complexity of Roman to Integer?

Both approaches read each character once, so the time is O(n) for a numeral of n characters. The extra space is O(1), because the lookup tables have a fixed size. A numeral from 1 to 3999 has at most 15 characters.

Can you convert a Roman numeral from right to left?

Yes. Walk from the last symbol to the first and remember the value of the symbol to the right. If the current symbol is worth less than that one, subtract it; otherwise add it. It is the same rule as the left to right version, seen from the other side.

Does this solution check that the numeral is valid?

No. The problem promises a valid numeral, so the code only adds and subtracts. An invalid string such as IIII or VV still returns a number, 4 or 10. To validate, convert the result back to a numeral and compare it with the input.

def romanToInt(s):
    # Write code here

Test #1

Test #2

Test #3

Argument

s = "XXVII"

Expected Output