Domain 1EasyCORE

Roman to Integer

The problem requires converting a Roman numeral string into its corresponding integer value. The input is a string `s` containing only valid Roman numeral characters (`I`, `V`, `X`, `L`, `C`, `D`, `M`). The output should be an integer representing the numeric value of the Roman numeral.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math#String

13. Roman to Integer

Model: qwen2.5-coder:14b
Topics: Math,String
FAANG asked: 1
Acceptance rate: 57.0%


Problem Breakdown

The problem requires converting a Roman numeral string into its corresponding integer value. The input is a string s containing only valid Roman numeral characters (I, V, X, L, C, D, M). The output should be an integer representing the numeric value of the Roman numeral.

Inputs:

  • A string s (1 <= s.length <= 15) containing Roman numerals.

Outputs:

  • An integer representing the numeric value of the Roman numeral.

Implicit Constraints and Edge Cases:

  • The input is guaranteed to be a valid Roman numeral.
  • The Roman numeral will always represent a number between 1 and 3999.
  • There are specific cases where subtraction is used (e.g., IV for 4, IX for 9).

Intuition

The brute-force approach would involve checking each possible combination of Roman numerals to determine their values. However, this approach is inefficient due to its high time complexity and unnecessary checks.

A better approach involves recognizing that in a valid Roman numeral:

  • If a smaller numeral appears before a larger numeral (e.g., IV), it indicates subtraction.
  • Otherwise, the numerals are added together.

The key insight is to iterate through the string from left to right. This allows us to easily determine whether to add or subtract each numeral based on its position relative to the next numeral.

Approach

  1. Mapping Roman Numerals to Values:

    • Create a dictionary that maps each Roman numeral character to its corresponding integer value.
  2. Iterate Through the String from Left to Right:

    • Initialize a variable total to store the resulting integer.
    • Iterate through the string s from left to right.
    • For each character, check if its value is less than the next numeral’s value:
      • If true, subtract its value from total.
      • If false, add its value to total.
  3. Return the Result:

    • After processing all characters, return the total as the integer representation of the Roman numeral.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string s. We iterate through the string once.
  • Space Complexity: O(1). The space used does not depend on the size of the input, only a fixed amount of extra space for variables and the dictionary.

Solution

def romanToInt(s: str) -> int:
    # Mapping of Roman numerals to their integer values
    roman_to_value = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    
    total = 0
    prev_value = 0
    
    # Iterate through the string from left to right
    for char in s:
        current_value = roman_to_value[char]
        
        if current_value > prev_value:
            total -= prev_value * 2
        total += current_value
        
        prev_value = current_value
    
    return total

Edge Cases Handled

  • Single Character Roman Numerals: The algorithm correctly handles single-character inputs like I, V, etc.
  • Subtractive Combinations: The algorithm correctly processes subtractive combinations such as IV (4), IX (9), XL (40), XC (90), CD (400), and CM (900).
  • Maximum Value: The algorithm can handle the maximum possible Roman numeral, MMMCMXCIX, which equals 3999.