13. Roman to Integer

Roman numeral conversion is a classic string manipulation problem frequently asked in technical interviews at companies like Google, Amazon, and Microsoft. This problem tests your ability to recognize patterns, work with mappings, and handle edge cases involving the subtractive notation used in Roman numerals.

Problem statement

You are given a string s representing a valid Roman numeral. Your task is to convert this Roman numeral into its equivalent integer value.

Roman numerals use seven distinct symbols with fixed values:

Typically, Roman numerals are written with symbols arranged from largest to smallest, left to right, and their values are added together. For instance, XII equals 12 (10 + 1 + 1), and XXVII equals 27 (10 + 10 + 5 + 1 + 1).

However, Roman numerals also employ a subtractive principle in specific cases to avoid repetition. When a smaller symbol appears immediately before a larger one, we subtract the smaller value instead of adding it. There are exactly six such subtractive combinations:

• I before V (5) or X (10) forms 4 or 9
• X before L (50) or C (100) forms 40 or 90
• C before D (500) or M (1000) forms 400 or 900

Your goal is to parse the given Roman numeral string and return the corresponding integer.

Constraints

• 1 <= s.length <= 15
• s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
• It is guaranteed that s is a valid roman numeral in the range [1, 3999].

Examples

Why the character-by-character approach falls short

A naive way to approach this problem would be to scan the string character by character and apply the additive or subtractive rule at each position by comparing the current symbol’s value with the next symbol’s value. For every character, we’d need to check if it forms part of a subtractive pair by examining whether its value is less than the symbol that follows it. If so, we subtract it; otherwise, we add it.

While this works with O(n) time and O(1) space complexity, it has downsides: repeated conditional checks, look-ahead logic for every character, and manual edge case handling (like the last character having no successor). This makes the code harder to read and maintain, and more prone to off-by-one errors. The approach also ignores that only six subtractive cases exist, which could be precomputed for cleaner, more efficient lookups.

Optimized approach using HashMap

The key insight here is that Roman numeral conversion follows only two patterns: additive and subtractive. Instead of repeatedly comparing adjacent characters during traversal, we can precompute all possible symbol values, both single characters and the six subtractive pairs, and store them in a dictionary. This transforms the problem from a comparison-heavy scan into a simple lookup-and-sum operation.

By including both individual symbols (I, V, X, etc.) and subtractive combinations (IV, IX, XL, XC, CD, CM) in our mapping, we can process the string in a single left-to-right pass. At each step, we check whether the next two characters form a subtractive pair. If they do, we consume both characters at once and add the pair’s value to our result. If not, we process just the current character and move forward by one position.

This approach works universally because the problem guarantees valid input. We never encounter ambiguous or malformed patterns. Even if the string contains complex combinations like MCMXCIV (1994), the dictionary allows us to recognize CM and XC as single logical units, simplifying the parsing logic dramatically.

Step-by-step algorithm

1. Create a dictionary, value_map, that maps every standard Roman symbol (I, V, X, L, C, D, M) and every valid subtractive pair (IV, IX, XL, XC, CD, CM) to their integer equivalents.
2. Initialize a variable int_val to 0. This will accumulate the final integer result.
3. Initialize a pointer i to 0 to traverse the string s from left to right.
4. While i is less than the length of s:
   1. Extract the two-character substring starting at position i (i.e., s[i:i+2]).
   2. Check if this substring exists in value_map.
   3. If it does, add its value to int_val and increment i by 2 (since we’ve processed two characters).
   4. If it doesn’t, add the value of the single character s[i] to int_val and increment i by 1.
5. After the loop completes, return int_val as the integer representation of the Roman numeral.

1 / 9

Code implementation

def roman_to_int(s):
    # Dictionary storing individual symbols and subtractive pairs
    value_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000,
        'IV': 4, 'IX': 9, 'XL': 40, 'XC': 90,
        'CD': 400, 'CM': 900
    }
    
    int_val = 0  # Accumulator for the final integer
    i = 0        # Pointer to traverse the string
    
    while i < len(s):
        # Check if the next two characters form a subtractive pair
        if i + 1 < len(s) and s[i:i+2] in value_map:
            int_val += value_map[s[i:i+2]]
            i += 2  # Move forward by two characters
        else:
            # Process single character
            int_val += value_map[s[i]]
            i += 1  # Move forward by one character
    
    return int_val


def main():
    # Test cases covering various patterns
    test_cases = [
        "III",        # Simple addition
        "LVIII",      # Mixed symbols
        "MCMXCIV",    # Multiple subtractive pairs
        "CDXLIV",     # Complex subtractive combinations
        "MMMCMXCIX"   # Maximum range value (3999)
    ]
    
    for idx, test in enumerate(test_cases, 1):
        result = roman_to_int(test)
        print(f"Test {idx}: roman_to_int(\"{test}\") = {result}")


if __name__ == "__main__":
    main()

Time complexity

The time complexity of this algorithm is O(n), where n is the length of the input string s. We traverse the string exactly once from left to right, and at each position, we perform a constant-time dictionary lookup to either process one or two characters.

Space complexity

The space complexity is O(1). Although we use a dictionary to store the mappings, its size is fixed at 13 entries (seven individual symbols and six subtractive pairs) and does not grow with the input size.

Common pitfalls and interview tips

1. Forgetting to handle the last character: When checking for subtractive pairs, always ensure i + 1 < len(s) before accessing s[i:i+2]. Without this guard, you might try to read beyond the string boundary and cause an index error.
2. Overlooking all six subtractive cases: Some candidates only remember IV and IX but forget about XL, XC, CD, and CM. Make sure your dictionary includes all six pairs to handle inputs like CDXLIV correctly.
3. Assuming all inputs are minimal: Even though the problem guarantees valid Roman numerals, interviewers might ask what happens if the string contains invalid patterns like IIII or VV. Be prepared to discuss validation, even if it’s not required in this problem.