LeetCode 13 - Roman to Integer

The problem gives a Roman numeral string and asks us to convert it into its corresponding integer value. Roman numerals use seven symbols: Symbol Value --- --- I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Most Roman numerals follow a simple additive rule.

leetcodeeasyhash-tablemathstring

LeetCode Problem 13

Difficulty: 🟢 Easy
Topics: Hash Table, Math, String

Solution

Problem Understanding

The problem gives a Roman numeral string and asks us to convert it into its corresponding integer value.

Roman numerals use seven symbols:

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

Most Roman numerals follow a simple additive rule. Symbols are written from largest to smallest, and we add their values together. For example:

  • "III" = 1 + 1 + 1 = 3
  • "XII" = 10 + 1 + 1 = 12

The tricky part is the subtraction rule. Sometimes a smaller symbol appears before a larger symbol, meaning we subtract instead of add:

  • "IV" = 5 - 1 = 4
  • "IX" = 10 - 1 = 9
  • "XL" = 50 - 10 = 40

Only six subtraction combinations are valid:

  • I before V or X
  • X before L or C
  • C before D or M

The input is guaranteed to be a valid Roman numeral between 1 and 3999. This guarantee is important because it means we do not need to validate malformed inputs like "IC" or "IIII".

The maximum string length is only 15, so performance is not a major concern. Even an O(n) or O(n^2) solution would easily pass. Still, the goal is to write a clean and correct algorithm that properly handles subtraction cases.

Important edge cases include:

  • A numeral with only additive symbols, like "III"
  • A numeral with multiple subtraction pairs, like "MCMXCIV"
  • A numeral ending with small values, like "LVIII"
  • Single-character inputs such as "I" or "V"

Approaches

Brute Force Approach

A brute-force solution could explicitly check every possible subtraction pair while scanning the string. At each position, we could look ahead two characters and compare against all known special cases:

  • "IV" → 4
  • "IX" → 9
  • "XL" → 40
  • "XC" → 90
  • "CD" → 400
  • "CM" → 900

If a special pair is found, we add its value and skip two characters. Otherwise, we add the value of the current single symbol and move one step forward.

This works because Roman numerals have only six valid subtraction patterns. However, it creates extra branching logic and duplicated handling between single symbols and pairs.

Optimal Approach

The key observation is that subtraction always occurs when a smaller value appears before a larger value.

For example:

  • "IV" → 1 < 5
  • "XC" → 10 < 100

Instead of hardcoding all subtraction pairs, we can process characters one by one:

  • If the current symbol is smaller than the next symbol, subtract it.
  • Otherwise, add it.

This rule naturally handles both additive and subtractive cases with a single pass through the string.

For "MCMXCIV":

  • M = +1000
  • C before M → -100
  • M = +1000
  • X before C → -10
  • C = +100
  • I before V → -1
  • V = +5

Total = 1994.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Explicitly checks all subtraction pairs
Optimal O(n) O(1) Uses value comparison between adjacent symbols

Algorithm Walkthrough

  1. Create a hash map that stores the integer value for each Roman numeral character.
  2. Initialize a variable called total to store the final answer.
  3. Iterate through the string from left to right.
  4. For each character, get its numeric value from the hash map.
  5. Check whether there is a next character in the string.
  6. If the current value is smaller than the next value, subtract the current value from total.

This handles subtraction patterns like:

  • IV
  • IX
  • XL
  • XC
  • CD
  • CM
  1. Otherwise, add the current value to total.
  2. Continue until the entire string has been processed.
  3. Return total.

Why it works

Roman numerals are constructed so that subtraction only occurs when a smaller numeral appears immediately before a larger numeral. By comparing adjacent values, we can determine whether a symbol contributes positively or negatively to the total. Every symbol is processed exactly once, and each contribution matches the Roman numeral rules, so the final sum is correct.

Python Solution

class Solution:
    def romanToInt(self, s: str) -> int:
        roman_values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }

        total = 0

        for i in range(len(s)):
            current_value = roman_values[s[i]]

            if i + 1 < len(s):
                next_value = roman_values[s[i + 1]]

                if current_value < next_value:
                    total -= current_value
                else:
                    total += current_value
            else:
                total += current_value

        return total

The solution starts by creating a dictionary that maps Roman numeral symbols to integer values. This allows constant-time lookup for every character.

The variable total stores the running result.

The loop processes each character one at a time. For every position, the algorithm compares the current symbol with the next symbol when possible.

If the current value is smaller than the next value, the current numeral is part of a subtraction pair, so we subtract it from the total.

Otherwise, we add it normally.

The final character is always added because there is no next symbol to compare against.

This implementation directly follows the Roman numeral rules while remaining compact and easy to read.

Go Solution

func romanToInt(s string) int {
    romanValues := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    total := 0

    for i := 0; i < len(s); i++ {
        currentValue := romanValues[s[i]]

        if i+1 < len(s) {
            nextValue := romanValues[s[i+1]]

            if currentValue < nextValue {
                total -= currentValue
            } else {
                total += currentValue
            }
        } else {
            total += currentValue
        }
    }

    return total
}

The Go implementation follows the same logic as the Python version. The main difference is that Go uses a map[byte]int instead of a Python dictionary.

Since Roman numeral characters are ASCII characters, indexing the string as bytes is safe and efficient.

Go integers easily handle the maximum possible answer of 3999, so overflow is not a concern.

Worked Examples

Example 1: "III"

Expected output: 3

Index Character Value Next Value Action Total
0 I 1 1 Add 1
1 I 1 1 Add 2
2 I 1 N/A Add 3

Final result: 3

Example 2: "LVIII"

Expected output: 58

Index Character Value Next Value Action Total
0 L 50 5 Add 50
1 V 5 1 Add 55
2 I 1 1 Add 56
3 I 1 1 Add 57
4 I 1 N/A Add 58

Final result: 58

Example 3: "MCMXCIV"

Expected output: 1994

Index Character Value Next Value Action Total
0 M 1000 100 Add 1000
1 C 100 1000 Subtract 900
2 M 1000 10 Add 1900
3 X 10 100 Subtract 1890
4 C 100 1 Add 1990
5 I 1 5 Subtract 1989
6 V 5 N/A Add 1994

Final result: 1994

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed exactly once
Space O(1) The hash map size is constant

The algorithm scans the string one time from left to right. Every operation inside the loop is constant time, so the total runtime grows linearly with the input length.

The auxiliary space remains constant because the Roman numeral mapping always contains exactly seven entries regardless of input size.

Test Cases

solution = Solution()

assert solution.romanToInt("III") == 3          # simple additive case
assert solution.romanToInt("LVIII") == 58       # mixed additive values
assert solution.romanToInt("MCMXCIV") == 1994   # multiple subtraction pairs

assert solution.romanToInt("I") == 1            # minimum valid input
assert solution.romanToInt("V") == 5            # single non-I symbol
assert solution.romanToInt("IV") == 4           # subtraction with I before V
assert solution.romanToInt("IX") == 9           # subtraction with I before X
assert solution.romanToInt("XL") == 40          # subtraction with X before L
assert solution.romanToInt("XC") == 90          # subtraction with X before C
assert solution.romanToInt("CD") == 400         # subtraction with C before D
assert solution.romanToInt("CM") == 900         # subtraction with C before M

assert solution.romanToInt("XXVII") == 27       # repeated additive numerals
assert solution.romanToInt("MMMCMXCIX") == 3999 # maximum valid Roman numeral
assert solution.romanToInt("MDCLXVI") == 1666   # descending additive sequence
Test Why
"III" Verifies simple addition
"LVIII" Verifies mixed numeral handling
"MCMXCIV" Verifies multiple subtraction pairs
"I" Smallest valid input
"V" Single-character non-additive case
"IV" Basic subtraction rule
"IX" Another subtraction variation
"XL" Tens subtraction rule
"XC" Tens before hundreds
"CD" Hundreds before five hundreds
"CM" Hundreds before thousands
"XXVII" Repeated additive numerals
"MMMCMXCIX" Maximum valid value
"MDCLXVI" Fully descending additive sequence

Edge Cases

A single-character Roman numeral is an important edge case because there is no next symbol to compare against. A careless implementation might access an out-of-bounds index when checking the next value. The solution avoids this by verifying i + 1 < len(s) before reading the next character.

Subtraction pairs such as "IV" and "CM" are another common source of bugs. A naive implementation that always adds values would incorrectly compute "IV" as 6 instead of 4. The algorithm correctly detects subtraction by comparing the current symbol with the next symbol.

Large numerals with multiple subtraction patterns, such as "MCMXCIV", can also expose logical mistakes. Some incorrect implementations only handle one subtraction pair or skip characters incorrectly. This solution processes every character independently and applies the same comparison rule consistently, so multiple subtraction pairs work naturally without special handling.