Roman to Integer
Understanding the Problem
We're given a string of Roman numeral characters and need to return the integer it represents. Mapping each symbol to its value is direct. The work is in the subtraction cases: when a smaller value appears before a larger one, those two characters combine into a single subtracted amount.
Take MCMXCIV. Reading left to right, most characters add their value. But CM means 900 (1000 - 100), XC means 90 (100 - 10), and IV means 4 (5 - 1). The question is how to decide, at each character, whether to add or subtract.
One comparison settles it. If a character's value is smaller than the value of the character to its right, subtract it. Otherwise, add it. That rule covers all six subtraction patterns and every additive character.
Key Constraints:
1 <= s.length <= 15→ The string is at most 15 characters, so even repeated scans of it are negligible. The approach choice here is about clarity, not speed.sis a valid Roman numeral in range[1, 3999]→ The input always follows proper Roman numeral rules, so there are no invalid or unknown characters to guard against, and no malformed sequences likeIIIIorIC. The largest possible result, 3999, fits comfortably in a 32-bit integer, so there is no overflow risk.
Approach 1: Replace Subtraction Pairs Then Sum
Intuition
One way to sidestep the add-or-subtract decision is to remove the subtraction cases before doing any addition. Each of the six subtraction pairs (IV, IX, XL, XC, CD, CM) stands for a fixed value, so we can find each pair, add its value, and delete it from the string. After that, every remaining character is purely additive, and we sum them with a plain lookup.
This relies on a property of the [1, 3999] range: each subtraction pair appears at most once in any valid numeral. For example, a numeral can contain IV only once, since two fours would never be written that way. That is why removing a single occurrence of each pair is enough.
Algorithm
- Initialize
result = 0. - For each of the six subtraction pairs (CM, CD, XC, XL, IX, IV), check if it exists in the string. If it does, add its combined value to
resultand remove it from the string. - Iterate through the remaining characters. For each one, look up its value and add it to
result. - Return
result.
Example Walkthrough
Code
- Time Complexity: O(n). We scan for each of the 6 subtraction pairs (each scan is O(n)), then iterate through the remaining characters. Since there are only 6 pairs, this is effectively O(n).
- Space Complexity: O(n). String replacement creates new strings. The pairs array is O(1) since it's always 6 elements.
This makes several passes over the string and allocates a new string on each replacement. A single left-to-right pass can make the add-or-subtract decision per character without any of that.
Approach 2: Left-to-Right with Lookahead (Optimal)
Intuition
In a valid Roman numeral, a smaller-valued symbol placed before a larger-valued symbol means subtraction. In every other position, a symbol adds its value. That distinction can be read off a single comparison between a character and the one to its right.
The algorithm walks the string left to right. At each position, it compares the current symbol's value to the next symbol's value. If the current value is smaller, it subtracts the current value; otherwise it adds it. This is one pass with no string manipulation and no need to enumerate the subtraction pairs.
Subtracting the smaller value and then adding the larger one on the next iteration produces the correct pair total. For IV, the I contributes -1 and the V contributes +5, summing to 4. For CM, the C contributes -100 and the M contributes +1000, summing to 900. A character that is not part of a subtractive pair is always greater than or equal to its right neighbor, so it is added. The [1, 3999] validity guarantee rules out sequences like IC, where the rule would still compute a value but the numeral itself is illegal.
Algorithm
- Create a map from each Roman numeral character to its integer value.
- Initialize
result = 0. - Iterate through the string from index
0ton - 1. - At each index
i, get the current character's value. - If
i < n - 1and the current value is less than the next character's value, subtract it fromresult. - Otherwise, add it to
result. - Return
result.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the string exactly once, doing O(1) work per character (a map lookup and a comparison).
- Space Complexity: O(1). The value map has exactly 7 entries regardless of input size. The only other variables are
result,n, andcurrent.