LeetCode 13: Roman to Integer

Problem Restatement

We are given a Roman numeral string s.

We need to convert it into an integer.

Roman numerals use seven symbols:

Usually, Roman numerals are written from largest to smallest.

For example:

VIII = 5 + 1 + 1 + 1 = 8

But there are six subtractive cases:

The input is guaranteed to be a valid Roman numeral in the range [1, 3999]. The string length is between 1 and 15, and it contains only I, V, X, L, C, D, and M.

Input and Output

Example function shape:

def romanToInt(s: str) -> int:
    ...

Examples

Example 1:

s = "III"

Value:

1 + 1 + 1 = 3

Output:

3

Example 2:

s = "LVIII"

Break it down:

L = 50
V = 5
III = 3

Total:

50 + 5 + 3 = 58

Output:

58

Example 3:

s = "MCMXCIV"

Break it down:

M = 1000
CM = 900
XC = 90
IV = 4

Total:

1000 + 900 + 90 + 4 = 1994

Output:

1994

First Thought: Check Special Pairs Manually

One direct approach is to scan the string and check whether the current character and the next character form one of the six subtractive pairs:

IV, IX, XL, XC, CD, CM

If we see one of these pairs, add its special value and skip two characters.

Otherwise, add the value of the current symbol and move one character.

This works.

But there is an even simpler rule.

Key Insight

When a smaller Roman value appears before a larger Roman value, we subtract it.

Otherwise, we add it.

For example:

IV

I is smaller than V, so:

-1 + 5 = 4

For:

VI

V is larger than I, so:

5 + 1 = 6

So for each symbol:

• if its value is less than the next symbol’s value, subtract it
• otherwise, add it

This rule correctly handles all six subtractive cases.

Visual Walkthrough

Use:

s = "MCMXCIV"

Map each symbol:

M = 1000
C = 100
M = 1000
X = 10
C = 100
I = 1
V = 5

Now scan left to right.

M is followed by C.

1000 >= 100
add 1000

C is followed by M.

100 < 1000
subtract 100

M is followed by X.

1000 >= 10
add 1000

X is followed by C.

10 < 100
subtract 10

C is followed by I.

100 >= 1
add 100

I is followed by V.

1 < 5
subtract 1

V is the last symbol, so add it.

Total:

1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994

Algorithm

1. Store Roman symbol values in a dictionary.
2. Initialize total = 0.
3. Scan every character by index.
4. For each character:
   • get its value
   • if the next character exists and has a larger value, subtract current value
   • otherwise, add current value
5. Return total.

Correctness

The Roman numeral is valid, so every subtractive case appears as a smaller symbol before a larger symbol.

The algorithm detects exactly that situation by comparing the current value with the next value.

If the current value is smaller than the next value, the current symbol contributes negatively as part of a subtractive pair.

Otherwise, the current symbol contributes normally and is added.

Every symbol is processed once.

For additive groups such as VIII, all symbols are added.

For subtractive groups such as IV, the first symbol is subtracted and the second symbol is added, producing the correct value.

Therefore the final total equals the integer represented by the Roman numeral.

Complexity

Since s.length <= 15, this is constant-bounded for the original constraints.

Implementation

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

        total = 0

        for i in range(len(s)):
            current = value[s[i]]

            if i + 1 < len(s) and current < value[s[i + 1]]:
                total -= current
            else:
                total += current

        return total

Code Explanation

The dictionary stores the value of each Roman symbol:

value = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}

We scan the string by index:

for i in range(len(s)):

For each symbol, read its value:

current = value[s[i]]

If the next symbol exists and is larger:

if i + 1 < len(s) and current < value[s[i + 1]]:

then this symbol is part of a subtractive pair, so subtract it:

total -= current

Otherwise, add it:

total += current

Finally:

return total

Testing

def run_tests():
    s = Solution()

    assert s.romanToInt("III") == 3
    assert s.romanToInt("LVIII") == 58
    assert s.romanToInt("MCMXCIV") == 1994
    assert s.romanToInt("IV") == 4
    assert s.romanToInt("IX") == 9
    assert s.romanToInt("XL") == 40
    assert s.romanToInt("XC") == 90
    assert s.romanToInt("CD") == 400
    assert s.romanToInt("CM") == 900
    assert s.romanToInt("MMMCMXCIX") == 3999

    print("all tests passed")

run_tests()