Roman to Integer (LeetCode 13)

The problem

You get a valid Roman numeral as a string made of I V X L C D M (1, 5, 10, 50, 100, 500, 1000). Normally symbols are written largest to smallest and simply added up. Six pairs use subtraction instead: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900. Return the integer value.

Input:  s = "MCMXCIV"
Output: 1994

M = 1000, CM = 900, XC = 90, IV = 4, and 1000 + 900 + 90 + 4 = 1994.

How to think about it

Start with brute force. You could list all six subtractive pairs, scan the string, and at each position first check whether the next two characters form one of those pairs. That works, but it is a pile of special cases, and it is easy to forget one or to skip the wrong number of characters after a match.

The key insight: a symbol is subtracted exactly when a larger symbol comes right after it. In IV, the I sits before a bigger V, so it counts as −1 and the V as +5, giving 4. In VI, the I comes after the V, so both add. This one rule covers all six pairs at once. You never need to treat pairs as units: each character independently contributes either +value or −value, decided by a one-character lookahead.

Why this is enough. In a valid numeral, a smaller symbol before a larger one only ever happens in those six subtractive pairs. So “compare with the next symbol” gives exactly the right sign every time, and a single left-to-right pass adds everything up.

Which pattern is this? A linear scan with a lookup table and one step of lookahead, from the number-tricks side of math & geometry. The tell is “a value is built symbol by symbol, and a symbol’s meaning depends on its neighbour”.

Approach

1. Store the value of each symbol in a dictionary.
2. Start total at 0 and walk the string with its index.
3. If there is a next character and the current symbol’s value is smaller than the next one’s, subtract the current value.
4. Otherwise add it.
5. Return total.

Solution

def roman_to_int(s):
    vals = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
    total = 0
    for i, c in enumerate(s):
        if i + 1 < len(s) and vals[c] < vals[s[i+1]]:   # smaller before larger
            total -= vals[c]                             # subtractive prefix
        else:
            total += vals[c]
    return total
# roman_to_int("MCMXCIV") -> 1994

Dry run

On s = "MCMXCIV":

The answer is 1994. Notice the running total dips (900, 1890, 1989) before the larger symbol makes up for it.

Complexity

• Time: O(n). One pass over the string, with O(1) dictionary lookups per character.
• Space: O(1). The table has seven fixed entries, and total is a single integer.

Edge cases and pitfalls

• Last character has no next symbol, so it is always added. The i + 1 < len(s) check prevents an index error.
• Equal neighbours add, as in III = 3 or XX = 20. Use strict <, not <=.
• Single symbol such as "M" returns its value directly.
• Scanning right to left is an equally good alternative: keep the previous value and subtract when the current symbol is smaller than it.
• Input is assumed valid. The rule does not reject malformed numerals like "IM"; say so if asked about validation.

Related problems

• Plus One (LeetCode 66): another number built and modified symbol by symbol.
• Reverse Integer (LeetCode 7): builds a value digit by digit, with an overflow twist.
• Evaluate Reverse Polish Notation (LeetCode 150): another left-to-right scan where each token’s role decides what you do with it.