DSA problem
Roman to Integer
Roman numerals are written using seven symbols — I, V, X, L, C, D, and M — whose values are 1, 5, 10, 50, 100, 500, and 1000 respectively. Given a Roman numeral string, convert it to an integer.
In the vast majority of positions the numeral is simply additive: you read left to right and accumulate the values of every symbol. For example, III is 1 + 1 + 1 = 3, and LVIII is 50 + 5 + 1 + 1 + 1 = 58. The interesting wrinkle is subtractive notation, used in six specific cases where a smaller numeral appears just before a larger one — IV, IX, XL, XC, CD, CM — meaning 4, 9, 40, 90, 400, and 900.
A natural way to handle both rules in a single pass is to compare each character with the one that follows it. If the current symbol's value is strictly less than the next symbol's value, we are in a subtractive pair: subtract the current value from the running total. Otherwise add it. The last character has nothing to its right, so it is always added.
This approach scans the string exactly once, performs O(1) work per character, and uses only a small fixed lookup table from symbol to integer. The total time complexity is O(n) where n is the length of the input (at most 15 for valid Roman numerals in the range 1 to 3999), and the extra space is O(1).
Examples
s = "III"3s = "LVIII"58s = "MCMXCIV"1994Constraints
- 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].
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.