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:

1. Key Insight:

   • Roman numerals follow a pattern where smaller values before larger ones indicate subtraction

   • All other cases are simple addition

2. Implementation Strategy:

   • Use map for O(1) value lookups

   • Look ahead one character when possible

   • Handle subtraction cases proactively

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

result

Leetcode: link