LeetCode #13 Easy

Roman to Integer

Convert a Roman numeral string to its integer value.

stringhash-tablemath
Open on LeetCode ↗
02

Intuition

💡

Roman numerals add up left to right, except when a smaller symbol sits before a larger one (like IV or IX) — then it is subtracted. So compare each symbol to its right neighbor to decide add or subtract.

03

Approach

1

Special-casing every pair is fragile

You could hard-code the six subtractive combinations — IV, IX, XL, XC, CD, CM — and add up the rest. It works but it's verbose, and it's easy to forget one or mishandle overlaps. There's a single unifying rule that makes all six fall out automatically.

2

Subtract only when a smaller symbol precedes a larger one

Roman numerals are additive by default; the only time a symbol is subtracted is when a smaller value sits immediately before a larger one (the I in IV, the X in XC). So the rule is purely local: compare each symbol to its right neighbor. If val[s[i]] < val[s[i+1]], this symbol is being used subtractively — subtract it; otherwise add it. That one comparison captures every subtractive case without listing any of them.

3

One left-to-right pass with a running total

Walk the string once, applying that rule and accumulating into total. The last symbol has no neighbor, so it always adds. Because each decision needs only the current symbol and the next one, the whole thing is a single O(n) scan with a fixed-size lookup table — O(1) extra space.

04

Solution & live demo

python
1class Solution:
2 def romanToInt(self, s):
3 val = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
4 'C': 100, 'D': 500, 'M': 1000}
5 total = 0
6 for i, ch in enumerate(s):
7 if i + 1 < len(s) and val[ch] < val[s[i + 1]]:
8 total -= val[ch]
9 else:
10 total += val[ch]
11 return total
05

Edge cases

Subtractive at the end, e.g. 'IX'

I (1) is less than X (10) so it subtracts; X has no successor so it adds — total 9.

Single symbol, e.g. 'V'

No successor exists, so it is simply added.

Repeated symbols, e.g. 'III'

Each I has an equal (not greater) successor, so all are added — total 3.

06

Complexity

Time
O(n)
Space
O(1)
One pass; the value map is fixed size.