Roman to Integer — InterviewPrepKit

Solving tips

Recognize this as a local-exception scan: numerals are additive except when a smaller symbol sits directly left of a larger one, which signals subtraction.
Key insight: add each symbol's value, but subtract it when val[s[i]] < val[s[i+1]]; no need to hardcode the six subtractive pairs.
Target O(n) time and O(1) space (the 7-entry value map is fixed size).
Common pitfall: use strict < not <= (equal neighbors like II are additive), and always add the last symbol which has no right neighbor.

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

Hint 1

Map each symbol to its value. Almost every symbol simply adds its value to a running total — the subtractive pairs are the only exception.

Hint 2

A symbol is subtracted exactly when its value is smaller than the value of the symbol immediately to its right (e.g. the `I` in `IV`). Otherwise it is added.

Hint 3

Scan left to right comparing each symbol with its right neighbor — subtract when strictly smaller, add otherwise. (Scanning right to left works too: compare each symbol with the previous, larger-so-far value.)

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

The insight: 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. So walk the string once and decide add-or-subtract per character.

class Solution:
    def romanToInt(self, 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":

i	symbol	next	rule	total
0	M=1000	C=100	1000 ≥ 100 → add	1000
1	C=100	M=1000	100 < 1000 → subtract	900
2	M=1000	X=10	add	1900
3	X=10	C=100	10 < 100 → subtract	1890
4	C=100	I=1	add	1990
5	I=1	V=5	1 < 5 → subtract	1989
6	V=5	—	add	1994

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

The insight: scanning from the right, you always know the value immediately to the right (the previous symbol). If the current symbol’s value is smaller than that, it’s a subtractive prefix; otherwise add it. This avoids the i + 1 bounds check.

class Solution:
    def romanToInt(self, 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 — you rarely need to special-case each exception explicitly if the exception has a uniform local signature (here: “smaller value directly left of a larger one”).