13. Roman to Integer

Time: O(n)

Space: O(1)

Intuition

In a valid Roman numeral, a smaller value before a larger value means subtraction; otherwise it means addition. Scan left to right: if the current symbol's value is less than the next symbol's value, subtract it; otherwise add it.

Algorithm

1Build a map: I->1, V->5, X->10, L->50, C->100, D->500, M->1000.
2Iterate i from 0 to n-1.
3If i < n-1 and map[s[i]] < map[s[i+1]]: subtract map[s[i]] from result.
4Else: add map[s[i]] to result.
5Return result.

Example Walkthrough

Input: "MCMXCIV"

1.M(1000): next is C(100). 1000 > 100 -> add. result=1000.
2.C(100): next is M(1000). 100 < 1000 -> subtract. result=900.
3.M(1000): next is X(10). add. result=1900.
4.X(10): next is C(100). 10 < 100 -> subtract. result=1890.
5.C(100): next is I(1). add. result=1990.
6.I(1): next is V(5). 1 < 5 -> subtract. result=1989.
7.V(5): last. add. result=1994.

Output: 1994

Common Pitfalls

•The last character always adds - the compare-with-next rule handles all subtractive cases automatically.

13.cs

// Approach: Map each symbol to its value. Subtract a symbol's value when
// a smaller value precedes a larger one; otherwise add it.
// Time: O(n) Space: O(1)

public class Solution
{
    public int RomanToInt(string s)
    {
        Dictionary<char, int> romanNumerals = new Dictionary<char, int>();
        romanNumerals.Add('I', 1);
        romanNumerals.Add('V', 5);
        romanNumerals.Add('X', 10);
        romanNumerals.Add('L', 50);
        romanNumerals.Add('C', 100);
        romanNumerals.Add('D', 500);
        romanNumerals.Add('M', 1000);

        int result = 0;
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == 'V' || s[i] == 'X')
            {
                if (i > 0 && s[i - 1] == 'I')
                {
                    result += romanNumerals[s[i]] - 2;
                    continue;
                }
            }
            else if (s[i] == 'L' || s[i] == 'C')
            {
                if (i > 0 && s[i - 1] == 'X')
                {
                    result += romanNumerals[s[i]] - 20;
                    continue;
                }
            }
            else if (s[i] == 'D' || s[i] == 'M')
            {
                if (i > 0 && s[i - 1] == 'C')
                {
                    result += romanNumerals[s[i]] - 200;
                    continue;
                }
            }
            result += romanNumerals[s[i]];
        }

        return result;
    }
}

Was this solution helpful?