13. Roman to Integer

Intuition

The problem requires converting a Roman numeral string to its integer equivalent. Roman numerals use seven symbols (I, V, X, L, C, D, M) with specific values, and follow a key rule: when a smaller symbol appears before a larger one, it represents subtraction (like IV = 4), otherwise it represents addition (like VI = 6). The key insight is to iterate through the string and compare each symbol with the next one to determine whether to add or subtract its value.

Approach

1. Create a hash map to store the integer value of each Roman symbol
2. Iterate through the string using an index pointer
3. For each character, compare its value with the next character (if it exists):
   • If current_value < next_value: this is a subtractive case (like IV, IX, XL, etc.)
     • Add (next_value - current_value) to the total
     • Skip both characters by incrementing index by 2
   • Otherwise: add current_value to the total and move to next character
4. Return the accumulated total

Code

def romanToInt(s: str) -> int:
    # Map Roman symbols to their integer values
    symbol_mapping = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }
 
    total_sum = 0
    i = 0  # Current index in the Roman numeral string
 
    # Loop through the string
    while i < len(s):
        current_value = symbol_mapping[s[i]]
 
        # Check if there's a next character and if it's a subtractive case
        # E.g., 'IV' where I (1) < V (5)
        if i + 1 < len(s) and current_value < symbol_mapping[s[i + 1]]:
            # Calculate value for subtractive pair (e.g., 5 - 1 = 4 for 'IV')
            total_sum += (symbol_mapping[s[i + 1]] - current_value)
            i += 2  # Skip both characters
        else:
            # Add the current symbol's value (normal case or last character)
            total_sum += current_value
            i += 1  # Move to the next character
 
    return total_sum

Time Complexity

• Time Complexity: O(n)

  • n: length of the string
  • We make one pass through the string, examining each character at most once

• Space Complexity: O(1)

  • We use a hash map with a fixed size of 7 entries for the Roman symbols
  • The space complexity is constant regardless of input size

The solution efficiently converts Roman numerals by using a hash map for symbol lookup and handling the subtractive cases through forward-looking comparison.