Roman to Integer

Problem

Roman numerals use seven symbols with fixed values: I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Numbers are written by placing symbols from largest to smallest and adding their values — except for six subtractive cases where a smaller symbol precedes a larger one and is subtracted: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. Given a valid Roman numeral string, return its integer value.

Examples

• "III" → 3 — 1 + 1 + 1.
• "LVIII" → 58 — 50 + 5 + 1 + 1 + 1.
• "MCMXCIV" → 1994 — M(1000) + CM(900) + XC(90) + IV(4).

Constraints

• 1 <= len(s) <= 15
• s is a valid Roman numeral in the range [1, 3999].

Think about it first

TL;DR

Single left-to-right pass: add each symbol’s value, but subtract it when it’s smaller than its right neighbor — O(n) time, O(1) space.

Approach 1 — Compare each symbol with its right neighbor

Roman numerals are additive except for the six subtractive pairs, and every subtractive pair is detectable locally: a symbol is subtracted precisely when a strictly larger symbol follows it. Walk the string once and decide add-or-subtract per character.

def romanToInt(s: str) -> int:
    val = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
           'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        if i + 1 < len(s) and val[s[i]] < val[s[i + 1]]:
            total -= val[s[i]]
        else:
            total += val[s[i]]
    return total

Walkthrough with "MCMXCIV":

Result: 1994.

Complexity: O(n) time, O(1) space (the value map is a fixed 7 entries).

Approach 2 — Right-to-left with a running maximum

Scanning from the right, the value immediately to the right is always the previously processed symbol. If the current symbol’s value is smaller than that, it is a subtractive prefix; otherwise add it. This avoids the i + 1 bounds check.

def romanToInt(s: str) -> int:
    val = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
           'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev = 0
    for ch in reversed(s):
        cur = val[ch]
        if cur < prev:
            total -= cur
        else:
            total += cur
        prev = cur
    return total

Walkthrough with "IX": process X=10 first (cur=10 ≥ prev=0 → add, total=10, prev=10), then I=1 (cur=1 < prev=10 → subtract, total=9). Result: 9.

Complexity: O(n) time, O(1) space — same asymptotics, just a different traversal order.

Common pitfalls

• Forgetting the bounds check on the right neighbor in the left-to-right version; the last symbol has no neighbor and must always be added.
• Using <= instead of < for the subtraction test — equal adjacent symbols (like II) are additive, not subtractive.
• Hardcoding all six two-letter pairs into the map; comparing neighboring single-symbol values handles every case automatically.

Pattern takeaway

When a notation is mostly additive with a few local exceptions, a single pass that inspects each element against its immediate neighbor usually suffices. There is no need to special-case each exception explicitly when the exception has a uniform local signature: here, a smaller value directly left of a larger one.