Roman to Integer

Adding every Roman symbol works for LVIII, but it turns IV into 6. The reliable Roman to Integer solution is a left-to-right scan with one local question: is the current value smaller than the next value?

If it is, subtract the current value. Otherwise, add it.

That small lookahead handles all six canonical subtractive pairs without hard-coding six separate cases.

Read the problem contract

You receive a valid Roman-numeral string and return its integer value.

The input:

• Has length from 1 to 15.
• Contains only I, V, X, L, C, D, and M.
• Represents a valid value from 1 through 3999.

The symbol values are fixed:

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

Most numerals are additive. For example:

• III = 1 + 1 + 1 = 3
• LVIII = 50 + 5 + 1 + 1 + 1 = 58

The exception is subtractive notation. These are the valid subtractive pairs:

Pair	Value
IV	4
IX	9
XL	40
XC	90
CD	400
CM	900

The input is guaranteed to be valid, so we do not need to reject malformed forms such as IL, lowercase symbols, or illegal repetitions. Validation would be a separate problem.

Find the local lookahead rule

Start with the tempting baseline:

1. Map each character to its value.
2. Add every value.

That baseline is correct for descending or equal-value sequences. It handles III, VIII, LVIII, and MCC.

It fails when a smaller symbol appears immediately before a larger one:

IV

The values are 1 and 5. The I is not an independent +1; it is the leading symbol of the subtractive pair IV. Its contribution is -1, followed by +5:

-1 + 5 = 4

So the local rule is:

• If current < next, subtract the current value.
• Otherwise, add the current value.
• The final symbol has no next symbol, so add it.

This is the entire parsing decision. We do not need to ask whether the current characters spell IV, IX, XL, or another named pair. The adjacent values already reveal the transition.

For example, scan MCMXCIV:

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

The smaller-before-larger transitions identify CM, XC, and IV automatically:

M   +1000
C   -100
M   +1000
X   -10
C   +100
I   -1
V   +5
----------------
     1994

The parser is a bounded string scan: fixed symbol lookup, one neighboring comparison, and one accumulator.

Choose the state and invariant

The algorithm needs three pieces of state:

1. A dictionary that maps symbols to values.
2. An index identifying the current character.
3. A running total.

The dictionary is lookup infrastructure. The main pattern is the evolving accumulator controlled by a local transition.

Use this invariant:

Before processing index i, total equals the value contributed by every symbol before i, with each subtractive relationship in that prefix accounted for exactly once.

At index i, look at the current value and, if it exists, the next value.

• If the current value is at least the next value, add it.
• If the current value is smaller than the next value, subtract it.
• Advance the index by exactly one.

The next iteration will process the larger symbol normally. For IV, the first iteration contributes -1; the second contributes +5. The pair is accounted for once, with the correct total.

A different implementation can consume the whole pair at once:

if current < next:
    add next - current
    skip two positions

That version is also correct. I prefer the one-symbol-at-a-time scan for a beginner because the invariant stays visible: every iteration consumes exactly one character, and every character receives one signed contribution.

Why adding everything fails

The naive approach is not useless. It is a correct model for the additive part of Roman numerals.

total = sum(values[ch] for ch in s)

For LVIII, this produces:

50 + 5 + 1 + 1 + 1 = 58

But for IV, it produces:

1 + 5 = 6

The repeated work is not expensive computation. The missing information is adjacency. The meaning of a symbol depends on whether the next symbol is larger.

The repair is small:

• Keep the fixed lookup table.
• Keep the single pass.
• Add a comparison with the next symbol.
• Choose the sign of the current contribution.

This is why the problem may be tagged with hash tables or maps, but the durable lesson is not “use hashing.” The durable lesson is: track the smallest evolving summary that determines the next transition.

Here, that summary is the running total plus one-symbol lookahead.

Trace ordinary and subtractive inputs

First, an ordinary additive input:

III

Index	Current	Next	Action	Total
0	1	1	add 1	1
1	1	1	add 1	2
2	1	—	add 1	3

Equal values use the additive branch. The final position also uses the additive branch because there is no successor.

Now trace the mixed input MCMXCIV:

Index	Current	Next	Action	Total
0	1000	100	add 1000	1000
1	100	1000	subtract 100	900
2	1000	10	add 1000	1900
3	10	100	subtract 10	1890
4	100	1	add 100	1990
5	1	5	subtract 1	1989
6	5	—	add 5	1994

Every symbol is processed once. The symbols that begin subtractive pairs contribute negatively, and the larger symbols are still processed normally on their own turns.

That is the state transition to keep in your head:

Compare. Choose a sign. Add one contribution. Move one position.

Write the Python scan

The Python implementation follows the invariant directly.

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

    total = 0
    i = 0

    while i < len(s):
        current = values[s[i]]

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

        i += 1

    return total

The important details are easy to miss under interview pressure:

• has_next protects the final position from an out-of-bounds lookup.
• A current value smaller than the next value is subtracted, not paired and skipped.
• The index advances by one on every iteration.
• The last symbol is added because has_next is false.

You can make the final-position behavior explicit with a default next value, but that introduces another convention the reader must remember. The boundary check is clearer here.

A reverse scan is another valid implementation. Starting at the right, you can compare each value with the largest value already seen and subtract when the current value is smaller. That avoids explicit lookahead, but it changes the mental direction. For this derivation, the left-to-right scan makes the local rule easiest to see.

Prove the result

We can prove correctness by checking what one iteration does to the invariant.

Assume that before index i, total correctly represents the value of the processed prefix.

At index i, there are two cases:

1. Current value is greater than or equal to the next value, or there is no next value.
   The current symbol is an ordinary additive contribution, so adding its value preserves the invariant.

2. Current value is smaller than the next value.
   Because the input is guaranteed to be a valid Roman numeral, the current symbol is the leading symbol of a valid subtractive relationship. Its contribution must be negative, so subtracting it preserves the invariant.

In both cases, the algorithm processes the current symbol exactly once and advances to the next position. When the scan finishes, every input symbol has contributed exactly once, including the final symbol. Therefore, total equals the integer value of the full Roman numeral.

The proof depends on the valid-input contract. If arbitrary strings were allowed, the comparison rule alone would not validate whether every smaller-before-larger arrangement is a legal Roman pair. For this problem, malformed input is explicitly outside the contract.

Complexity

Let n be the length of the string.

• Time: O(n)
  The loop visits each character once and performs constant-time dictionary lookups and comparisons.

• Extra space: O(1)
  The lookup table contains a fixed seven-symbol alphabet. The accumulator and index also use constant space.

The input string itself is not counted as extra space.

Test the boundary transitions

Good tests target the branch changes, not just random examples.

Minimum and additive cases

I      -> 1
III    -> 3
VIII   -> 8

These confirm that ordinary additions and repeated symbols work.

Descending input

LVIII  -> 58

This checks a larger symbol followed by smaller symbols and a repeated tail.

Every canonical subtractive pair

IV  -> 4
IX  -> 9
XL  -> 40
XC  -> 90
CD  -> 400
CM  -> 900

These confirm that the local comparison handles all allowed pair boundaries.

Mixed input

MCMXCIV -> 1994

This combines ordinary additions with subtractive transitions at multiple positions.

Final-position boundary

VI -> 6
IV -> 4

The first checks that the final I is added. The second checks that the lookahead logic does not accidentally skip or double-count the final V.

Lowercase characters, malformed pairs such as IL, and noncanonical strings are outside the guaranteed-input contract. Do not quietly add validation logic unless the problem asks for it. Extra rules create extra branches, and extra branches create extra ways to obscure the core parser.

The transferable pattern

When a symbolic sequence is mostly additive but contains a bounded local exception, do not begin with a table of special cases.

Start with:

1. Map each symbol to a value.
2. Identify the smallest neighborhood that changes meaning.
3. Compare adjacent state.
4. Add a signed contribution to an accumulator.
5. State what one iteration consumes.
6. Test one ordinary run and one transition that changes the sign.

For Roman numerals, the neighborhood is two symbols: the current symbol and its successor. The invariant is the running total for the consumed prefix.

The implementation is short because the reasoning is explicit. Compare. Choose a sign. Accumulate. Advance. That is the Roman to Integer solution—and a useful string-scan pattern beyond Roman numerals.