13. Roman to Integer

Reformulated question¶

Convert a valid Roman numeral string to its integer value.

Example:

Input:  s = "MCMXCIV"
Output: 1994
Why:    M(1000) + CM(900) + XC(90) + IV(4)

Key trick¶

Scan left to right and compare each symbol with the next one.

If current value is smaller than next, subtract it.
Otherwise, add it.

Trap¶

Common mistakes:

Forgetting the subtractive cases like IV, IX, XL, XC, CD, CM.
Overcomplicating by hardcoding pairs when a simple compare-with-next rule works.
Accessing s[i + 1] without checking bounds.

Why this question is interesting¶

It tests whether you can turn a formatting rule into a clean linear scan.

Small problem.
Easy to brute force.
Good signal for careful string parsing.

Solve the problem with idiomatic python¶

class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

        total = 0

        # If a symbol is smaller than the one after it, it is subtractive.
        for i, ch in enumerate(s):
            if i + 1 < len(s) and values[ch] < values[s[i + 1]]:
                total -= values[ch]
            else:
                total += values[ch]

        return total

Pytest test¶

import pytest

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("I", 1),
        ("III", 3),
        ("IV", 4),
        ("IX", 9),
        ("LVIII", 58),
        ("XL", 40),
        ("XC", 90),
        ("CD", 400),
        ("CM", 900),
        ("MCDLXXVI", 1476),
        ("MCMXCIV", 1994),
        ("MMMCMXCIX", 3999),
    ],
)
def test_roman_to_int(s, expected):
    assert Solution().romanToInt(s) == expected

Comment my solution¶

Your solution is correct and interview-acceptable.

Good:

Handles the six subtractive pairs explicitly.
Runs in \(O(n)\) time and \(O(1)\) space.
Easy to reason about.

Could be improved:

substract and substract_pairs should be spelled subtract and subtract_pairs.
The pair-table approach is a bit more verbose than needed.
The compare-with-next solution is shorter and more general.

import pytest

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_to_int = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
                    }
        substract = {"I", "X", "C"}
        substract_pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}

        n = len(s)
        out = 0
        i = 0
        while i < n:
            ch = s[i]
            if ch in substract:
                if (i + 1) < len(s):
                    pair = ch + s[i + 1]
                    if pair in substract_pairs:
                        out += substract_pairs[pair]
                        i += 2
                        continue
            out += roman_to_int[ch]
            i += 1

        return out

@pytest.mark.parametrize(
    ("s", "expected"),
    [
        ("III", 3),
        ("LVIII", 58),
        ("MCDLXXVI", 1476),
        ("MCMXCIV", 1994)
    ]
)
def test_romanToInt(s, expected):
    assert Solution().romanToInt(s) == expected