Roman to Integer

Roman to Integer is a classic string warm-up. Roman numerals are almost just "add up the symbols" — except for a handful of subtractive pairs like IV (4) and IX (9). The whole problem is spotting those pairs cleanly in a single pass.

The slow way first

You could scan for each two-character subtractive pair (CM, XC, IV, …), special-case all six, and handle every other character on its own. That works, but it is a pile of if branches that is easy to get wrong, and it reads the string in awkward chunks.

The question to ask: is there one rule that covers both the add case and the subtract case? There is — and it only needs to peek one symbol ahead.

The idea: subtract when a bigger symbol follows

Walk the string left to right. For each symbol look at its value cur. Compare it to the next symbol's value:

• If cur is less than the next value, this symbol is part of a subtractive pair, so subtract it.
• Otherwise (it is greater or equal, or it is the last symbol), add it.

That single rule reproduces every subtractive pair automatically: in IV, the I (1) is less than V (5) so we subtract 1, then add 5 → 4. No special cases.

The key insight: the subtractive rule is local — it only depends on the current symbol and the one immediately after it, so one left-to-right pass with a single peek is enough.

Walk through it

Step through the animation on MMXXIV. The pointer i scans left to right and the total label updates underneath. The two Ms add 1000 each (total 2000), the two Xs add 10 each (total 2020), and then comes the only subtraction: the I (1) sits before V (5), so it is subtracted (total 2019). Finally the V is added because nothing follows it, giving 2024.

Pseudocode

value = { I:1, V:5, X:10, L:50, C:100, D:500, M:1000 }
total = 0
for each index i in s:
    cur = value of s[i]
    if there is a next symbol and cur < value of s[i+1]:
        total = total - cur        # subtractive pair, e.g. IV, XC
    else:
        total = total + cur        # normal add
return total

The Python solution

def roman_to_int(s):
    value = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        cur = value[s[i]]
        if i + 1 < len(s) and cur < value[s[i + 1]]:
            total -= cur
        else:
            total += cur
    return total

• value is a dictionary mapping each symbol to its number.
• cur = value[s[i]] is the value of the symbol we are standing on.
• Line 6 is the heart of it: i + 1 < len(s) guards the last symbol (no peek possible), and cur < value[s[i + 1]] detects a subtractive pair.
• When that test is true we subtract cur; otherwise we add it.
• The last symbol always takes the else branch, because there is no next value to compare against.

Complexity

The value map has a fixed size of seven entries, so it does not grow with the input — the extra space is O(1). We make exactly one pass with a constant-time lookup and peek per character.

When this pattern shows up

Practice