C# LeetCode 13: Roman To Integer - (Easy)

This solution beat 99.94% of submissions for time
This solution beat 77.21% of submissions for memory usage
at time of writing.

Problem Description:

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

There are six instances where subtraction is used:
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Code:

public class Solution
{
    private static readonly Dictionary<char, int> RomanMap = new()
    {
        ['I'] = 1,
        ['V'] = 5,
        ['X'] = 10,
        ['L'] = 50,
        ['C'] = 100,
        ['D'] = 500,
        ['M'] = 1000
    };

    public int RomanToInt(string s)
    {
        int sum = 0;
        int maxValueFromRight = 0;
        for (int i = s.Length - 1; i >= 0; i--)
        {
            int value = RomanMap[s[i]];

            if (value >= maxValueFromRight)
            {
                sum += value;
                maxValueFromRight = value;
            }
            else
            {
                sum -= value;
            }
        }

        return sum;
    }
}

Approach

The approach may look tricky at first, but it’s straightforward once you break it down. Let’s step through it.

Firstly create a Dictionary to map the Roman Numerals to an integer value. We can then use this as a lookup directory for our string to integer conversion.

 int sum = 0;
 var maxValueFromRight = 0;

sum stores the running total.
maxValueFromRight stores the largest value seen so far as we iterate from right to left.

This tells us whether to add or subtract the current value.

Roman numeral subtraction rule

Roman numerals follow this key rule:

If a smaller value appears before a larger value, it should be subtracted. Otherwise it is added.

For example:
VI → 5 + 1 = 6 (I smaller, but comes after V → add)
IV → 5 − 1 = 4 (I is smaller and comes before V → subtract)

XL → 50 - 10 = 40 (X is smaller and comes before L → subtract)

Scanning right to left:

Compare the current numeral value to maxValueFromRight.

If it’s at least as big, add it to the sum and update maxValueFromRight.

If it’s smaller, subtract it from the sum. This automatically handles all subtraction cases in Roman numerals.

Scanning from right to left simplifies logic because:

The largest value on the right becomes the baseline for subtraction.

No need to peek ahead in the string; we only compare to maxValueFromRight.

Example

String is 1994 -> "MCMXCIV"

So the iterations would look something like this:

Step	Current Char	Value	maxValueFromRight	Action	Sum
1	V	5	0	+5	5
2	I	1	5	−1	4
3	C	100	5	+100	104
4	X	10	100	−10	94
5	M	1000	100	+1000	1094
6	C	100	1000	−100	994
7	M	1000	1000	+1000	1994

As you can see we can easily adjust the sum, using a combination of the right to left , and keeping track of the previous number technique.

Returning the sum

It's then just a simple case of returning the summed value at the end of traversing through all the digits, and you've got a O(n) time and O(1) extra space complexity

It's worth noting though this solution adds no validation of the input string, and assumes (as per LeetCode's instructions) all input strings are valid Roman Numerals.

Final Thoughts

Take a look at this code, and perhaps look at how you could refactor to add in validation ?

Drop a follow via DevTo, or on twitter to hear about more articles in this series.