LeetCode 13 – Roman to Integer

Roman to Integer is the inverse of Integer to Roman, and the trick that solved that one does not transfer. Going the other way, the six subtractive pairs are handled by a single comparison: if a symbol is smaller than the one after it, subtract it instead of adding it. One rule, no table of pairs, no lookahead bookkeeping.

The problem

Convert a Roman numeral in the range 1 to 3999 to an integer.

"III"     -> 3
"LVIII"   -> 58     50 + 5 + 1 + 1 + 1
"MCMXCIV" -> 1994   1000 + (1000 - 100) + (100 - 10) + (5 - 1)

The idea: one comparison replaces six special cases

Start from the naive version — look up each character and add them all. That gives IV = 1 + 5 = 6 where the answer is 4. Every subtractive pair is overcounted by exactly twice the smaller symbol, and one repair is to count the pairs and subtract the difference back out.

That works and it is more machinery than the problem needs. The better observation is that a subtractive pair is not really an exception — it is just the general rule that a symbol placed before a larger symbol is negative. Roman numerals are otherwise written in descending order, so "smaller than its right-hand neighbour" happens if and only if you are looking at the first half of one of the six pairs. Nothing else in a well-formed numeral can trigger it.

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

So you never need to recognise CM as a unit at all. Walk the string one character at a time, peek at the next one, and choose the sign. The last character has no neighbour, so it is always added — which the bounds check handles for free.

Java

class Solution {
    public int romanToInt(String s) {
        int sum = 0;

        for (int i = 0; i < s.length(); i++) {
            int value = valueOf(s.charAt(i));

            // Smaller before larger is subtractive: IV IX XL XC CD CM.
            // The final character has no neighbour, so it always adds.
            if (i + 1 < s.length() && value < valueOf(s.charAt(i + 1))) {
                sum -= value;
            } else {
                sum += value;
            }
        }

        return sum;
    }

    private int valueOf(char c) {
        return switch (c) {
            case 'I' -> 1;
            case 'V' -> 5;
            case 'X' -> 10;
            case 'L' -> 50;
            case 'C' -> 100;
            case 'D' -> 500;
            case 'M' -> 1000;
            default  -> 0;
        };
    }
}

The arrow switch expression needs Java 14 or later. On an older codebase use a classic switch with break, or a Map<Character, Integer> — but prefer the switch: it compiles to a jump table, avoids boxing every character, and allocates nothing per call. A HashMap rebuilt inside romanToInt is a common and needless cost; if you use one, make it static final.

Python

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

    def romanToInt(self, s: str) -> int:
        total = 0

        for i, c in enumerate(s):
            value = self.VALUES[c]

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

        return total

The dictionary is a class attribute, so it is built once at import rather than on every call.

Complexity

O(n) time in the length of the numeral, O(1) space. Since the input is capped at 3999 the string is at most fifteen characters, so this is constant in practice — but state it as O(n), because the algorithm itself has no such bound.

What the interviewer is checking

• That you find the single comparison rather than enumerating the six pairs. Both work; only one shows you saw the structure.
• That the last character does not read past the end of the string.
• "MCMXCIV" — three subtractive pairs in one input.
• That you do not rebuild a hash map on every call.
• Whether you ask about malformed input. The problem guarantees a valid numeral; validating "IIII" or "VX" is a much larger problem, and knowing to ask is the point.