Roman to Integer
EasyPrompt
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 1000For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
Ican be placed beforeV(5) andX(10) to make 4 and 9.Xcan be placed beforeL(50) andC(100) to make 40 and 90.Ccan be placed beforeD(500) andM(1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.Example 2:
Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.Example 3:
Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints:
1 <= s.length <= 15scontains only the characters('I', 'V', 'X', 'L', 'C', 'D', 'M').- It is guaranteed that
sis a valid roman numeral in the range[1, 3999].
Approaches
3 approaches with complexity analysis and trade-offs.
This approach simplifies the problem by first transforming the Roman numeral string into a purely additive form. It identifies and replaces all subtractive combinations (like 'IV', 'IX') with their additive equivalents (like 'IIII', 'VIIII'). After all replacements, the string contains only symbols that are added together. The final step is to iterate through this modified string and sum the values of each individual Roman numeral symbol.
Algorithm
- Create a map to store the integer value for each Roman symbol ('I', 'V', 'X', etc.).
- Perform string replacements for all subtractive pairs in the input string
s:s = s.replace("IV", "IIII")s = s.replace("IX", "VIIII")s = s.replace("XL", "XXXX")s = s.replace("XC", "LXXXX")s = s.replace("CD", "CCCC")s = s.replace("CM", "DCCCC")
- Initialize a variable
totalto 0. - Iterate through each character of the modified string.
- For each character, look up its value in the map and add it to
total. - Return
total.
Walkthrough
The core idea is to eliminate the complexity of subtraction rules. We perform a series of string replacements to convert subtractive pairs into their longer, additive forms. For example, 'CM' (900) is replaced by 'DCCCC' (500 + 100*4). Once all such replacements are done, the Roman numeral follows a simple rule: the total value is the sum of all individual symbol values. We can then iterate through the transformed string once to calculate this sum. A map is used to store the value of each Roman symbol for easy lookup.
import java.util.Map;import java.util.HashMap; class Solution { public int romanToInt(String s) { Map<Character, Integer> map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); s = s.replace("IV", "IIII"); s = s.replace("IX", "VIIII"); s = s.replace("XL", "XXXX"); s = s.replace("XC", "LXXXX"); s = s.replace("CD", "CCCC"); s = s.replace("CM", "DCCCC"); int sum = 0; for (char c : s.toCharArray()) { sum += map.get(c); } return sum; }}Complexity
Time
O(N)
Space
O(N)
Trade-offs
Pros
The logic for the final summation is very simple, as it involves only addition.
Cons
Inefficient due to multiple string passes and creating new string objects for each replacement (especially in languages with immutable strings like Java).
The space complexity is O(N) because new strings are created, making it less memory-efficient than other approaches.
This approach processes the Roman numeral string from left to right in a single pass. For each symbol, it compares its value with the value of the symbol immediately to its right. If the current symbol's value is less than the next one, it signifies a subtractive case (like 'IV' or 'CM'), and its value is subtracted from the total. Otherwise, its value is added to the total. The value of the last symbol is always added.
Algorithm
- Create a map to store the integer value for each Roman symbol.
- Initialize
totalto 0. - Iterate through the string from
i = 0tos.length() - 2. - Get the value of the current symbol
s.charAt(i)and the next symbols.charAt(i+1). - If
value(current) < value(next), subtractvalue(current)fromtotal. - Otherwise, add
value(current)tototal. - After the loop, add the value of the last symbol (
s.charAt(s.length() - 1)) tototal. - Return
total.
Walkthrough
This method iterates through the string from left to right, which is a natural way to read. We maintain a running total. For each symbol, we check if it's part of a subtractive pair by looking at the next symbol. If the current symbol's value is less than the next symbol's value (e.g., 'I' before 'V' in "IV"), we subtract the current symbol's value from our total. Otherwise, we add it. The final symbol is always added, so the loop runs up to the second-to-last character, and the last character's value is added after the loop.
import java.util.Map;import java.util.HashMap; class Solution { public int romanToInt(String s) { Map<Character, Integer> map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); int total = 0; for (int i = 0; i < s.length() - 1; i++) { int currentVal = map.get(s.charAt(i)); int nextVal = map.get(s.charAt(i + 1)); if (currentVal < nextVal) { total -= currentVal; } else { total += currentVal; } } total += map.get(s.charAt(s.length() - 1)); return total; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Efficient with O(N) time complexity as it requires only a single pass through the string.
Space-efficient with O(1) space complexity (excluding the map which is constant size).
Cons
The logic is slightly more complex than a right-to-left pass due to the need for a lookahead and special handling of the last character.
This is the most efficient and elegant approach. It involves iterating through the Roman numeral string from right to left. The logic is based on the observation that when read from right to left, a symbol's value is added to the total unless it is smaller than the symbol to its right, in which case it is subtracted. This eliminates the need for complex lookaheads.
Algorithm
- Create a map to store the integer value for each Roman symbol.
- Initialize
totalwith the value of the last symbol in the string. - Iterate through the string backwards, from
i = s.length() - 2down to0. - Get the value of the current symbol
s.charAt(i)and the symbol to its rights.charAt(i+1). - If
value(current) < value(right), subtractvalue(current)fromtotal. - Otherwise, add
value(current)tototal. - Return
total.
Walkthrough
This approach is often considered the most clever and clean. By processing the string from right to left, the logic becomes very straightforward. We initialize our total with the value of the rightmost symbol. Then, we iterate backwards. For each symbol, we compare it with the one to its right (which we have already processed). If the current symbol's value is smaller (e.g., 'I' in "IV"), we subtract its value. Otherwise, we add it. This works because in Roman numerals, any smaller value preceding a larger value indicates subtraction; otherwise, it's always addition.
import java.util.Map;import java.util.HashMap; class Solution { public int romanToInt(String s) { Map<Character, Integer> map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); int total = map.get(s.charAt(s.length() - 1)); for (int i = s.length() - 2; i >= 0; i--) { if (map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) { total -= map.get(s.charAt(i)); } else { total += map.get(s.charAt(i)); } } return total; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Highly efficient with O(N) time and O(1) space complexity.
Features a very clean and simple implementation logic without special cases inside the loop.
Arguably the most elegant solution to the problem.
Cons
Iterating from right to left might be slightly less intuitive for some developers compared to a standard left-to-right pass.
Solutions
Solution
public class Solution { public int RomanToInt(string s) { Dictionary < char, int > d = new Dictionary < char, int > (); d.Add('I', 1); d.Add('V', 5); d.Add('X', 10); d.Add('L', 50); d.Add('C', 100); d.Add('D', 500); d.Add('M', 1000); int ans = d[s[s.Length - 1]]; for (int i = 0; i < s.Length - 1; ++i) { int sign = d[s[i]] < d[s[i + 1]] ? -1 : 1; ans += sign * d[s[i]]; } return ans; }}class Solution {public int romanToInt(String s) { String cs = "IVXLCDM"; int[] vs = {1, 5, 10, 50, 100, 500, 1000}; Map<Character, Integer> d = new HashMap<>(); for (int i = 0; i < vs.length; ++i) { d.put(cs.charAt(i), vs[i]); } int n = s.length(); int ans = d.get(s.charAt(n - 1)); for (int i = 0; i < n - 1; ++i) { int sign = d.get(s.charAt(i)) < d.get(s.charAt(i + 1)) ? -1 : 1; ans += sign * d.get(s.charAt(i)); } return ans; }}const romanToInt = function ( s ) { const d = { I : 1 , V : 5 , X : 10 , L : 50 , C : 100 , D : 500 , M : 1000 , }; let ans = d [ s [ s . length - 1 ]]; for ( let i = 0 ; i < s . length - 1 ; ++ i ) { const sign = d [ s [ i ]] < d [ s [ i + 1 ]] ? - 1 : 1 ; ans += sign * d [ s [ i ]]; } return ans ; };class Solution {public: int romanToInt(string s) { unordered_map<char, int> nums{ {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}, }; int ans = nums[s.back()]; for (int i = 0; i < s.size() - 1; ++i) { int sign = nums[s[i]] < nums[s[i + 1]] ? -1 : 1; ans += sign * nums[s[i]]; } return ans; }};class Solution: def romanToInt(self, s: str) -> int: d = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} return sum((- 1 if d[a] < d[b] else 1) * d[a] for a, b in pairwise(s)) + d[s[- 1]]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.