Roman to Integer

How it works

Roman numerals normally add values from left to right. The key insight is handling subtractive notation, where a smaller value before a larger one means subtraction (like IV = 4, not 6). As we scan left to right, if the current symbol is smaller than the next one, we subtract its value; otherwise, we add it. This single rule handles both regular addition and subtractive cases elegantly.

Steps

1. Create a hash map storing each Roman numeral character and its integer value.
2. Initialize the result to 0.
3. Iterate through each character in the string:
   • If the current character's value is less than the next character's value, subtract it from the result.
   • Otherwise, add it to the result.
4. Return the final result.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) since we have 7 characters in the hash map.

Things to watch for

Always Adding Instead of Subtracting

A common mistake is to always add the value of each Roman numeral without checking for subtractive notation. For example, treating IV as I + V = 6 instead of V - I = 4. The fix is to compare the current character's value with the next character's value and subtract when the current is smaller.

Off-by-One Error When Comparing Adjacent Characters

When checking if the current numeral is smaller than the next, forgetting to verify that i + 1 is within bounds causes an index out of bounds error. Always ensure the comparison i + 1 < len(s) is checked before accessing s[i + 1].

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

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> roman = {
            {'I', 1}, {'V', 5}, {'X', 10},
            {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
        };

        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (i + 1 < s.size() && roman[s[i]] < roman[s[i + 1]]) {
                res -= roman[s[i]];
            } else {
                res += roman[s[i]];
            }
        }
        return res;
    }
};