Roman to Integer

Difficulty: Easy | Acceptance: 65.34% | Paid: No

Topics: Hash Table, Math, String

• Examples
• Constraints
• Brute Force Approach
• Optimal One-Pass Approach
• Reverse Iteration Approach

Examples

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

Brute Force Approach

Intuition

We can sum up all values directly and then correct for subtraction cases. First pass to add all normal values, then second pass to subtract 2x the smaller value for each special case (because we counted it once too many in the first pass).

Steps

• Iterate through the string and add the value of each character based on a lookup table.
• Then iterate again to check for the special subtraction cases and adjust the total accordingly.
• For each subtraction case, we must subtract twice the value of the smaller character (since it was already added once).

def romanToInt(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    
    # First pass: Add all values
    for char in s:
        total += roman_map[char]
    
    # Second pass: Adjust for subtraction cases
    for i in range(len(s) - 1):
        if s[i] == 'I' and (s[i+1] == 'V' or s[i+1] == 'X'):
            total -= 2
        elif s[i] == 'X' and (s[i+1] == 'L' or s[i+1] == 'C'):
            total -= 20
        elif s[i] == 'C' and (s[i+1] == 'D' or s[i+1] == 'M'):
            total -= 200
            
    return total

Complexity

• Time: O(n) where n is the length of the string, as we iterate through the string twice
• Space: O(1) as we only use a fixed-size map and a few variables

Optimal One-Pass Approach

Intuition

Instead of two passes, we can process the string left to right in a single pass. When we encounter a character that is smaller than the next character, we subtract its value; otherwise, we add it. This directly handles the subtraction cases.

Steps

• Iterate through the string from left to right.
• At each step, compare the current character’s value with the next character’s value.
• If the current value is less than the next value, subtract the current value from the total (this handles cases like IV, IX, etc.).
• Otherwise, add the current value to the total.
• Handle the last character separately since there’s no next character to compare with.

def romanToInt(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    
    for i in range(len(s)):
        if i < len(s) - 1 and roman_map[s[i]] < roman_map[s[i+1]]:
            total -= roman_map[s[i]]
        else:
            total += roman_map[s[i]]
            
    return total

Complexity

• Time: O(n) where n is the length of the string, as we iterate through the string once
• Space: O(1) as we only use a fixed-size map and a few variables

Reverse Iteration Approach

Intuition

We can iterate from right to left. When we see a character that is smaller than the previous character (the one we just processed), we subtract its value. This is another way to naturally handle subtraction cases.

Steps

• Start from the rightmost character and move left.
• Keep track of the value of the previously processed character.
• If the current character’s value is less than the previous one, subtract it from the total.
• Otherwise, add it to the total.
• Update the previous character’s value after each iteration.

def romanToInt(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    prev_value = 0
    
    for i in range(len(s) - 1, -1, -1):
        current_value = roman_map[s[i]]
        if current_value < prev_value:
            total -= current_value
        else:
            total += current_value
        prev_value = current_value
            
    return total

Complexity

• Time: O(n) where n is the length of the string, as we iterate through the string once
• Space: O(1) as we only use a fixed-size map and a few variables