Roman to Integer
Convert Roman numerals to integers by subtracting whenever a smaller symbol precedes a larger one
Problem Statement
Convert a Roman numeral string to an integer.
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Input: "III" → 3
Input: "LVIII" → 58 (L=50, V=5, III=3)
Input: "MCMXCIV" → 1994 (M=1000, CM=900, XC=90, IV=4)Intuition
Roman numerals are usually written largest-to-smallest, and you just add: LVIII is 50 + 5 + 1 + 1 + 1 = 58.
The exception is subtractive notation. To avoid four repeated symbols, a smaller symbol placed before a larger one is subtracted: IV is 4, not 6. There are six such pairs — IV, IX, XL, XC, CD, CM.
Special-casing all six is tedious. There is a single rule that covers everything.
The key insight
Scan left to right. For each symbol, compare it with the next one:
- If the current value is less than the next → subtract it.
- Otherwise → add it.
That one comparison handles all six subtractive pairs and every ordinary case, with no lookup table of pairs.
Check it on MCMXCIV:
M (1000) vs C (100) → 1000 ≥ 100 → +1000 total 1000
C (100) vs M (1000) → 100 < 1000 → -100 total 900
M (1000) vs X (10) → 1000 ≥ 10 → +1000 total 1900
X (10) vs C (100) → 10 < 100 → -10 total 1890
C (100) vs I (1) → 100 ≥ 1 → +100 total 1990
I (1) vs V (5) → 1 < 5 → -1 total 1989
V (5) — last symbol, always added → +5 total 1994The last symbol has nothing after it, so it is always added.
Watch it run
Approach
Walk the string, looking one character ahead
If value[i] < value[i+1], subtract; otherwise add.
Always add the final symbol
It has no successor, so the subtraction rule cannot apply.
Solution
def roman_to_int(s: str) -> int:
"""Convert a Roman numeral to its integer value."""
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
for i in range(len(s)):
# A smaller symbol before a larger one means subtraction.
if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
total -= values[s[i]]
else:
total += values[s[i]]
return totalThe right-to-left variant
Scanning backwards removes the bounds check. Track the previous (larger-index) value: if the current value is smaller, subtract; otherwise add.
def roman_to_int_reverse(s: str) -> int:
values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
total = 0
prev = 0
for char in reversed(s):
value = values[char]
total += -value if value < prev else value
prev = value
return totalBoth are O(n); pick whichever reads more naturally to you.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time — one pass with a constant-time map lookup per character.
- Space — the value map has a fixed 7 entries, so it does not grow with the input.
Edge Cases
Related Problems
- Integer to Roman — the inverse conversion, which is greedy rather than comparative
- Evaluate Reverse Polish Notation — another notation-parsing problem