LeetCode 13: Roman to Integer

Problem Statement

Given a Roman numeral string s, convert it to an integer. Roman numerals use seven symbols—I (1), V (5), X (10), L (50), C (100), D (500), M (1000)—with subtractive notation (e.g., IV = 4) for certain pairs. The input is guaranteed to be a valid Roman numeral between 1 and 3999.

Constraints

• 1 <= s.length <= 15
• s contains only 'I', 'V', 'X', 'L', 'C', 'D', 'M'
• Result is in range [1, 3999]

Example

Copy codeInput: s = "III"
Output: 3
Explanation: Three I’s = 3.

Input: s = "LVIII"
Output: 58
Explanation: L (50) + V (5) + III (3) = 58.

Input: s = "MCMXCIV"
Output: 1994
Explanation: M (1000) + CM (900) + XC (90) + IV (4) = 1994.

Understanding the Problem

We need to turn a Roman numeral like "MCMXCIV" into 1994. In Roman numerals, symbols are usually added from left to right, but if a smaller value precedes a larger one (e.g., IV), subtract the smaller from the larger. We’ll use a right-to-left scan to simplify this logic.

Solution: Right-to-Left Scan

Explanation

Scan the string from right to left, adding each symbol’s value unless it’s less than the next symbol, then subtract it. This handles subtractive pairs naturally.

1. Define a mapping of Roman symbols to their integer values.

2. Start with the last symbol’s value as the initial result.

3. Move right to left, comparing each symbol with the next:

• If current value is less than the next, subtract it.
• Otherwise, add it.

4. Return the final sum.

Step-by-Step Example

Example 1: s = "LVIII"

We have "LVIII" and want 58.

• Goal: Convert "LVIII" to an integer.
• Result for reference: 50 + 5 + 3 = 58.
• Start: Map symbols—I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000. Result at 0.
• Step 1: Last character "I" (position 4).
• Value = 1, no next symbol, add 1.
• Result = 1, move to 3.
• Step 2: "I" (position 3).
• Value = 1, next is 1, 1 ≥ 1, add 1.
• Result = 2, move to 2.
• Step 3: "I" (position 2).
• Value = 1, next is 1, 1 ≥ 1, add 1.
• Result = 3, move to 1.
• Step 4: "V" (position 1).
• Value = 5, next is 1, 5 ≥ 1, add 5.
• Result = 8, move to 0.
• Step 5: "L" (position 0).
• Value = 50, next is 5, 50 ≥ 5, add 50.
• Result = 58, end of string.
• Finish: Return 58.
• Matches 50 + 5 + 3.

Example 2: s = "MCMXCIV"

Now, "MCMXCIV" to 1994.

• Goal: Convert "MCMXCIV" to an integer.
• Result for reference: 1000 + 900 + 90 + 4 = 1994.
• Start: Result at 0.
• Step 1: "V" (position 6).
• Value = 5, add 5.
• Result = 5, move to 5.
• Step 2: "I" (position 5).
• Value = 1, next is 5, 1 < 5, subtract 1.
• Result = 4, move to 4.
• Step 3: "C" (position 4).
• Value = 100, next is 1, 100 ≥ 1, add 100.
• Result = 104, move to 3.
• Step 4: "X" (position 3).
• Value = 10, next is 100, 10 < 100, subtract 10.
• Result = 94, move to 2.
• Step 5: "M" (position 2).
• Value = 1000, next is 10, 1000 ≥ 10, add 1000.
• Result = 1094, move to 1.
• Step 6: "C" (position 1).
• Value = 100, next is 1000, 100 < 1000, subtract 100.
• Result = 994, move to 0.
• Step 7: "M" (position 0).
• Value = 1000, next is 100, 1000 ≥ 100, add 1000.
• Result = 1994, end.
• Finish: Return 1994.
• Matches 1000 + 900 + 90 + 4.

Code

Here’s the Python code to solve LeetCode 13. It’s fast and works in Python 3.6+. Try it on Replit!

Copy codedef romanToInt(s: str) -> int:
    roman_values = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }

    result = 0
    for i in range(len(s) - 1, -1, -1):
        curr_value = roman_values[s[i]]
        if i + 1 < len(s) and curr_value < roman_values[s[i + 1]]:
            result -= curr_value
        else:
            result += curr_value

    return result

Note: Explore Python’s dictionaries in the official docs.

Complexity

• Time Complexity: O(n) – One pass through the string, where n is its length.
• Space Complexity: O(1) – Fixed-size dictionary and a single variable.

Efficiency Notes

This right-to-left scan is efficient and intuitive, handling subtractive notation seamlessly with a single pass.

Key Insights

Tips to master LeetCode 13:

• Right-to-Left Rocks: Going backward simplifies subtraction logic—no need to peek ahead twice.
• Know the Symbols: Memorize I, V, X, L, C, D, M values—it’s the foundation.
• Spot Subtraction: If a smaller value comes before a larger one, subtract it—key to Roman rules.

These tips make conversion a breeze!

Alternative: Left-to-Right (Brief Mention)

You could scan left to right, adding values and adjusting for subtractive pairs by checking the next character, but it’s slightly trickier than right-to-left.

Additional Example

For s = "IX":

• Goal: Convert to integer.
• Reference: 9 (10 - 1).
• Steps: X (10), I (1 < 10, subtract), 10 - 1 = 9.
• Result: 9.

Edge Cases

• Minimum: s = "I" – Returns 1.
• Maximum: s = "MMMCMXCIX" (3999) – Returns 3999.
• Single Pair: s = "IV" – Returns 4.