Roman to Integer (Leetcode 13)

Roman numerals are represented by seven different symbols: I, V, X, L, C, D, M. Converting a Roman Numeral string back to a standard integer is a classic interview question that tests your ability to parse strings and handle edge case rules.

The Problem Statement

Given a roman numeral string s, convert it to an integer.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX.

Subtraction Rules:

• I can be placed before V (5) and X (10) to make 4 and 9.
• X can be placed before L (50) and C (100) to make 40 and 90.
• C can be placed before D (500) and M (1000) to make 400 and 900.

Examples

Input: s = "III"
Output: 3

Input: s = "LVIII"
Output: 58

Input: s = "MCMXCIV"
Output: 1994 // M = 1000, CM = 900, XC = 90, IV = 4

The Intuition: Looking Ahead

The basic logic is simple: read the string from left to right, and add the value of each symbol to a total sum.

The twist is the subtraction rule. If a smaller symbol appears before a larger symbol, it means we are dealing with a subtraction case (like IV or CM).

Therefore, for any character s[i]:

• If value(s[i]) < value(s[i+1]), we subtract its value.
• If value(s[i]) >= value(s[i+1]), we add its value.

Visualization of "MCMXCIV"

Let's trace MCMXCIV (1994):

Map: M=1000, D=500, C=100, L=50, X=10, V=5, I=1

[ M CMA X C I V ]
  1000   100  1000  10   100   1    5

Is M < C? No.  Sum = 1000
Is C < M? Yes. Sum = 1000 - 100 = 900
Is M < X? No.  Sum = 900 + 1000 = 1900
Is X < C? Yes. Sum = 1900 - 10 = 1890
Is C < I? No.  Sum = 1890 + 100 = 1990
Is I < V? Yes. Sum = 1990 - 1 = 1989
Is V < Null? No. Sum = 1989 + 5 = 1994

The Code (Constant Space Approach)

Here is a clean, readable implementation:

function romanToInt(s: string): number {
    const values: Record<string, number> = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    };
    
    let total = 0;
    
    for (let i = 0; i < s.length; i++) {
        const currentVal = values[s[i]];
        // Check if we need to subtract (is the next value larger?)
        if (i < s.length - 1 && currentVal < values[s[i + 1]]) {
            total -= currentVal;
        } else {
            total += currentVal;
        }
    }
    
    return total;
}

Complexity Analysis

Watch the video above for a detailed, slow-paced walkthrough of this exact algorithm solving Leetcode #13!