13. Roman to Integer

🟩 Easy

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

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. There are six instances where subtraction is used:

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.

Given a roman numeral, convert it to an integer.

Example 1

Input: s = "III" Output: 3 Explanation: III = 3.

Example 2

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

Example 3

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

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].

Solution

My Solution

func romanToInt(s string) int {
    sum := 0

    rim := map[string]int{
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }

    for i, v := range s {
        sum += rim[string(v)]
        if i != 0 {
            if rim[string(s[i-1])] < rim[string(v)] {
                sum -= 2 * rim[string(s[i-1])]
            }
        }
    }

    return sum
}

Approach

This solution uses a single pass with lookahead to convert Roman numerals:

Key Insight:
- Roman numerals follow a pattern where smaller values before larger ones indicate subtraction
- All other cases are simple addition
Implementation Strategy:
- Use map for O(1) value lookups
- Look ahead one character when possible
- Handle subtraction cases proactively
Processing Rules:
- If current value < next value: subtract current
- Otherwise: add current value
- Last digit always adds (no lookahead needed)

Complexity Analysis

Time Complexity: O(n)

Single pass through the string
Each character processed exactly once
Map lookups are O(1)
String length is bounded by constraint (≤ 15)

Space Complexity: O(1)

Fixed-size map for Roman numeral values
Only constant extra space used:
- Two integer variables (result, length)
- Loop counter
- Map with 7 entries (fixed size)

Why it works

Roman Numeral Properties:
- Left-to-right processing matches natural reading order
- Subtraction cases are always pairs of characters
- Valid input guaranteed (no error handling needed)
Optimization Details:
- Uses byte map instead of string map (more efficient)
- Lookahead prevents need for backtracking
- No string conversions needed during processing
Key Improvements over Original:
- No string conversions in loop
- No double subtraction needed
- Cleaner logic flow
- More efficient memory usage
Handling Special Cases:
- IV (4) = -1 + 5
- IX (9) = -1 + 10
- XL (40) = -10 + 50
- XC (90) = -10 + 100
- CD (400) = -100 + 500
- CM (900) = -100 + 1000

Previous12. Integer to Roman Next14. Longest Common Prefix

Last updated 5 months ago

Was this helpful?

Solution

My Solution

func romanToInt(s string) int {
    sum := 0

    rim := map[string]int{
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }

    for i, v := range s {
        sum += rim[string(v)]
        if i != 0 {
            if rim[string(s[i-1])] < rim[string(v)] {
                sum -= 2 * rim[string(s[i-1])]
            }
        }
    }

    return sum
}

Approach

This solution uses a single pass with lookahead to convert Roman numerals:

Key Insight:

Roman numerals follow a pattern where smaller values before larger ones indicate subtraction
All other cases are simple addition

Implementation Strategy:

Use map for O(1) value lookups
Look ahead one character when possible
Handle subtraction cases proactively

Processing Rules:

If current value < next value: subtract current
Otherwise: add current value
Last digit always adds (no lookahead needed)

Complexity Analysis

Time Complexity: O(n)

Single pass through the string

Each character processed exactly once

Map lookups are O(1)

String length is bounded by constraint (≤ 15)

Space Complexity: O(1)

Fixed-size map for Roman numeral values

Only constant extra space used:

Two integer variables (result, length)
Loop counter
Map with 7 entries (fixed size)

Why it works

Roman Numeral Properties:

Left-to-right processing matches natural reading order
Subtraction cases are always pairs of characters
Valid input guaranteed (no error handling needed)

Optimization Details:

Uses byte map instead of string map (more efficient)
Lookahead prevents need for backtracking
No string conversions needed during processing

Key Improvements over Original:

No string conversions in loop
No double subtraction needed
Cleaner logic flow
More efficient memory usage

Handling Special Cases:

IV (4) = -1 + 5
IX (9) = -1 + 10
XL (40) = -10 + 50
XC (90) = -10 + 100
CD (400) = -100 + 500
CM (900) = -100 + 1000

Leetcode: