Skip to main content
CodePeetCodePeet
CodePeet 250

Roman to Integer

EASYProblemSolveExternal Links

Description

Roman numerals use seven symbols to represent numbers:

SymbolValue
I1
V5
X10
L50
C100
D500
M1000

Numbers are typically formed by writing symbols from largest to smallest, left to right, and summing their values. For example, XII = 10 + 1 + 1 = 12, and XXVII = 10 + 10 + 5 + 1 + 1 = 27.

However, there are six special cases where a smaller symbol placed immediately before a larger one indicates subtraction:

  • I before V or X makes 4 (IV) and 9 (IX)
  • X before L or C makes 40 (XL) and 90 (XC)
  • C before D or M makes 400 (CD) and 900 (CM)

Given a string s representing a valid Roman numeral, convert it to its corresponding integer value.

Examples

Example 1

Input: s = "III"

Output: 3

Explanation: Each 'I' represents 1. Since all three symbols are the same, there are no subtraction cases. We simply add: I + I + I = 1 + 1 + 1 = 3.

Example 2

Input: s = "LVIII"

Output: 58

Explanation: Reading left to right: L = 50, V = 5, I = 1, I = 1, I = 1. Every symbol is greater than or equal to the one that follows it, so no subtraction is needed. The sum is 50 + 5 + 1 + 1 + 1 = 58.

Example 3

Input: s = "MCMXCIV"

Output: 1994

Explanation: This Roman numeral contains three subtraction pairs. Breaking it down: M = 1000, CM = 900 (1000 − 100), XC = 90 (100 − 10), IV = 4 (5 − 1). Adding these groups: 1000 + 900 + 90 + 4 = 1994. The subtraction pairs are identified whenever a smaller-valued symbol appears directly before a larger-valued one.

Constraints

  • 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]

Editorial

Brute Force

Intuition

The most straightforward way to convert a Roman numeral is to recognize that there are exactly 13 distinct "tokens" in the Roman numeral system: the 7 single-character symbols (I, V, X, L, C, D, M) and the 6 two-character subtraction pairs (IV, IX, XL, XC, CD, CM).

We can store all 13 tokens and their values in a lookup map. Then, we scan the string from left to right. At each position, we first check whether the two characters starting at the current position form one of the 6 subtraction pairs. If they do, we add that pair's value and skip forward by two characters. If not, we treat the current character as a single symbol, add its value, and advance by one.

Think of it like reading a book where some words are two letters and some are one letter. At each position, you try the two-letter word first. If it matches a known word, great — consume both letters. Otherwise, read just the one letter and move on.

Step-by-Step Explanation

Let's trace through with s = "MCMXCIV".

Step 1: Initialize result = 0 and pointer i = 0. Our map has 13 entries: 7 singles + 6 pairs.

Step 2: At i=0, check two-character substring "MC". Is "MC" in our pair map? No — "MC" is not a valid subtraction pair. Fall back to single character "M" = 1000. Add 1000. result = 1000. Advance i to 1.

Step 3: At i=1, check two-character substring "CM". Is "CM" in our pair map? Yes! CM = 900. Add 900. result = 1900. Advance i by 2 to i=3.

Step 4: At i=3, check two-character substring "XC". Is "XC" in our pair map? Yes! XC = 90. Add 90. result = 1990. Advance i by 2 to i=5.

Step 5: At i=5, check two-character substring "IV". Is "IV" in our pair map? Yes! IV = 4. Add 4. result = 1994. Advance i by 2 to i=7.

Step 6: i=7 is beyond the string length (7 characters, indices 0-6). We're done. Return 1994.

Two-Character Pair Matching — Scanning MCMXCIV — Watch how we check for two-character subtraction pairs first at each position, falling back to single characters when no pair is found.

Algorithm

  1. Build a lookup map containing all 13 Roman tokens:
    • 7 single symbols: I=1, V=5, X=10, L=50, C=100, D=500, M=1000
    • 6 subtraction pairs: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900
  2. Initialize result = 0 and pointer i = 0
  3. While i < length of string:
    • If i+1 is within bounds and the two-character substring s[i..i+2] is in the map:
      • Add the pair's value to result
      • Advance i by 2
    • Otherwise:
      • Add the single character's value to result
      • Advance i by 1
  4. Return result

Code

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<string, int> values = {
            {"I", 1}, {"V", 5}, {"X", 10}, {"L", 50},
            {"C", 100}, {"D", 500}, {"M", 1000},
            {"IV", 4}, {"IX", 9}, {"XL", 40},
            {"XC", 90}, {"CD", 400}, {"CM", 900}
        };
        
        int result = 0;
        int i = 0;
        
        while (i < s.length()) {
            if (i + 1 < s.length() && values.count(s.substr(i, 2))) {
                result += values[s.substr(i, 2)];
                i += 2;
            } else {
                result += values[s.substr(i, 1)];
                i += 1;
            }
        }
        
        return result;
    }
};
class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            "I": 1, "V": 5, "X": 10, "L": 50,
            "C": 100, "D": 500, "M": 1000,
            "IV": 4, "IX": 9, "XL": 40,
            "XC": 90, "CD": 400, "CM": 900
        }
        
        result = 0
        i = 0
        
        while i < len(s):
            if i + 1 < len(s) and s[i:i+2] in values:
                result += values[s[i:i+2]]
                i += 2
            else:
                result += values[s[i]]
                i += 1
        
        return result
class Solution {
    public int romanToInt(String s) {
        Map<String, Integer> values = new HashMap<>();
        values.put("I", 1); values.put("V", 5); values.put("X", 10);
        values.put("L", 50); values.put("C", 100); values.put("D", 500);
        values.put("M", 1000); values.put("IV", 4); values.put("IX", 9);
        values.put("XL", 40); values.put("XC", 90); values.put("CD", 400);
        values.put("CM", 900);
        
        int result = 0;
        int i = 0;
        
        while (i < s.length()) {
            if (i + 1 < s.length() && values.containsKey(s.substring(i, i + 2))) {
                result += values.get(s.substring(i, i + 2));
                i += 2;
            } else {
                result += values.get(s.substring(i, i + 1));
                i += 1;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the string once from left to right. At each position, we perform a constant-time hash map lookup (either for a two-character key or a one-character key). Since the string has at most 15 characters (constraint: 1 ≤ s.length ≤ 15), the number of iterations is at most 15. In general terms, for a string of length n, the time is O(n).

Space Complexity: O(1)

The hash map stores exactly 13 entries regardless of input size — this is a fixed constant. We use a few integer variables (result, i). No space grows with the input, so the auxiliary space is O(1).

Why This Approach Is Not Efficient

The two-character pair matching approach correctly converts any Roman numeral in O(n) time. However, it has several practical drawbacks:

1. Enlarged Lookup Map: We maintain 13 entries in the map — 7 single symbols plus 6 subtraction pairs. This is nearly double the fundamental set of symbols. If the Roman numeral system had more subtraction rules, the map would grow combinatorially, making the approach harder to scale or modify.

2. Substring Creation Overhead: At every position, we create a two-character substring (s.substr(i, 2) in C++, s[i:i+2] in Python, s.substring(i, i+2) in Java) to look up in the map. Even when no pair is found, we've already allocated a temporary string. This adds memory allocation overhead at each step.

3. Missed Pattern: The approach treats subtraction pairs as arbitrary special cases that must be enumerated one by one. But there is an elegant mathematical pattern hiding in the rules: whenever a smaller-valued symbol appears immediately before a larger-valued symbol, subtract the smaller instead of adding it. This single observation eliminates the need for all 6 pair entries and the two-character lookahead logic entirely.

The next approach exploits this subtraction rule to achieve the same result with a simpler map (only 7 entries), no substring creation, and more readable code.

Optimal Approach - Subtraction Rule

Intuition

Instead of memorizing all 13 tokens, we can observe a simple pattern: in a valid Roman numeral, symbols are generally arranged from largest to smallest (left to right). The only exception is subtraction pairs, where a smaller symbol appears immediately before a larger one.

This gives us a one-line rule: if the current symbol's value is less than the next symbol's value, subtract it; otherwise, add it.

Why does this work? Consider CM = 900. When we see 'C' (100) followed by 'M' (1000), the subtraction rule makes us subtract 100, then on the next step add 1000. The net effect is −100 + 1000 = 900, which is exactly the value of CM. This pattern works for all six subtraction cases.

For non-subtraction cases like 'XV' (15), 'X' (10) is followed by 'V' (5). Since 10 ≥ 5, we add 10, then add 5, giving 15 — correct.

By using only the 7 single-character values and one comparison per character, we eliminate the need for pair entries, substring creation, and branching between one-character and two-character modes.

Step-by-Step Explanation

Let's trace through with s = "MCMXCIV".

Step 1: Initialize result = 0. Our map has just 7 entries: I=1, V=5, X=10, L=50, C=100, D=500, M=1000.

Step 2: i=0, s[0]='M' (1000). Compare with s[1]='C' (100). Since 1000 ≥ 100, add M. result = 0 + 1000 = 1000.

Step 3: i=1, s[1]='C' (100). Compare with s[2]='M' (1000). Since 100 < 1000, subtract C. result = 1000 − 100 = 900. The subtraction rule detected the CM pair automatically.

Step 4: i=2, s[2]='M' (1000). Compare with s[3]='X' (10). Since 1000 ≥ 10, add M. result = 900 + 1000 = 1900. Combined with step 3, CM contributed −100 + 1000 = 900.

Step 5: i=3, s[3]='X' (10). Compare with s[4]='C' (100). Since 10 < 100, subtract X. result = 1900 − 10 = 1890. The subtraction rule detected the XC pair.

Step 6: i=4, s[4]='C' (100). Compare with s[5]='I' (1). Since 100 ≥ 1, add C. result = 1890 + 100 = 1990. Combined with step 5, XC contributed −10 + 100 = 90.

Step 7: i=5, s[5]='I' (1). Compare with s[6]='V' (5). Since 1 < 5, subtract I. result = 1990 − 1 = 1989. The subtraction rule detected the IV pair.

Step 8: i=6, s[6]='V' (5). This is the last character — no next character to compare. Always add the last character. result = 1989 + 5 = 1994. Combined with step 7, IV contributed −1 + 5 = 4.

Step 9: Return 1994.

Subtraction Rule — Compare Adjacent Values in MCMXCIV — Watch how comparing each character's value with the next character's value automatically detects subtraction pairs — subtracting when smaller precedes larger, adding otherwise.

Algorithm

  1. Build a map of the 7 single Roman symbols to their integer values:
    • I → 1, V → 5, X → 10, L → 50, C → 100, D → 500, M → 1000
  2. Initialize result = 0
  3. For each index i from 0 to length-1:
    • Look up the value of s[i]
    • If i+1 is within bounds and value(s[i]) < value(s[i+1]):
      • Subtract value(s[i]) from result
    • Otherwise:
      • Add value(s[i]) to result
  4. Return result

Code

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> values = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        
        int result = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 < s.length() && values[s[i]] < values[s[i + 1]]) {
                result -= values[s[i]];
            } else {
                result += values[s[i]];
            }
        }
        
        return result;
    }
};
class Solution:
    def romanToInt(self, s: str) -> int:
        values = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000
        }
        
        result = 0
        
        for i in range(len(s)):
            if i + 1 < len(s) and values[s[i]] < values[s[i + 1]]:
                result -= values[s[i]]
            else:
                result += values[s[i]]
        
        return result
class Solution {
    public int romanToInt(String s) {
        Map<Character, Integer> values = new HashMap<>();
        values.put('I', 1); values.put('V', 5); values.put('X', 10);
        values.put('L', 50); values.put('C', 100); values.put('D', 500);
        values.put('M', 1000);
        
        int result = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 < s.length() && values.get(s.charAt(i)) < values.get(s.charAt(i + 1))) {
                result -= values.get(s.charAt(i));
            } else {
                result += values.get(s.charAt(i));
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once, processing each character with a constant-time map lookup and a single comparison. For a string of length n (at most 15 per constraints), the total work is O(n). Compared to the brute force, we avoid substring creation at each step, making this approach faster in practice despite the same asymptotic complexity.

Space Complexity: O(1)

The map stores exactly 7 entries — a fixed constant independent of the input. We use a single integer variable for the result. No additional space grows with the input size.

This approach is optimal for this problem. The time complexity cannot be improved below O(n) because we must examine every character at least once to determine the total value. The space complexity is already O(1). The subtraction rule reduces both the code complexity and the constant factors compared to the pair-matching approach.