Roman to Integer

Easy Arrays & Hashing Right to Left Traversal Original on LeetCode

Roman to Integer is a easy arrays & hashing problem solved with the right to left traversal pattern. The best approach, optimal (right-to-left scan), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (match the six pairs first) up.

Problem

Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Symbols are usually written from largest to smallest and their values are added, so XVI is 16.

Six combinations use subtraction instead: IV (4), IX (9), XL (40), XC (90), CD (400) and CM (900). A smaller symbol placed directly before a larger one is subtracted from it.

Given a valid Roman numeral s, return the integer it represents.

Examples

Example 1

Input
s = "XXVII"
Output
27
Why
X + X + V + I + I = 10 + 10 + 5 + 1 + 1 = 27.

Example 2

Input
s = "CDXLIV"
Output
444
Why
CD = 400, XL = 40 and IV = 4: each smaller symbol in front of a larger one is subtracted.

Example 3

Input
s = "MCMXCIX"
Output
1999
Why
M = 1000, CM = 900, XC = 90, IX = 9.

Constraints

  • 1 <= s.length <= 15
  • s contains only the symbols I V X L C D M.
  • s is a valid Roman numeral for a value in [1, 3999].

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 17 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (match the six pairs first)O(n)O(1)
Optimal (right-to-left scan)O(n)O(1)

1Brute force (match the six pairs first)

TimeO(n)Each position is looked at once, with one substring lookup of length 2.
SpaceO(1)The token map has a fixed 13 entries.

List all thirteen tokens a numeral can be built from: the seven single symbols and the six subtractive pairs (IV, IX, XL, XC, CD, CM). Scan left to right; at each position try the two-letter token first, and fall back to the single letter.

  1. Store a map from token to value for the 13 tokens.
  2. At index i, if i + 1 < n and s[i..i+1] is a pair token, add its value and jump by 2.
  3. Otherwise add the value of s[i] and move by 1.
class Solution {
    public int romanToInt(String s) {
        Map<String, Integer> value = new HashMap<>();
        String[] tokens = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        int[] vals = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        for (int k = 0; k < tokens.length; k++) value.put(tokens[k], vals[k]);
        int total = 0, i = 0, n = s.length();
        while (i < n) {
            if (i + 1 < n && value.containsKey(s.substring(i, i + 2))) {
                total += value.get(s.substring(i, i + 2));
                i += 2;
            } else {
                total += value.get(s.substring(i, i + 1));
                i += 1;
            }
        }
        return total;
    }
}

2Optimal (right-to-left scan)

TimeO(n)One pass over the string with an O(1) lookup per symbol.
SpaceO(1)A fixed seven-entry lookup and two integers.

Walk from the last symbol to the first, remembering the value of the symbol just processed. If the current symbol is smaller than that one, it is the left half of a subtractive pair, so subtract it; otherwise add it. No pair table is needed.

  1. Map each of the seven letters to its value.
  2. total = 0, prev = 0.
  3. For i from n - 1 down to 0: v = value(s[i]); if v < prev subtract v, else add v; set prev = v.
  4. Return total.
class Solution {
    public int romanToInt(String s) {
        int total = 0, prev = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int v = valueOf(s.charAt(i));
            if (v < prev) total -= v;
            else total += v;
            prev = v;
        }
        return total;
    }

    private int valueOf(char c) {
        switch (c) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            default: return 1000;
        }
    }
}

Edge cases to test

  • A single symbol such as "I" or "M"
  • Several subtractive pairs in a row, like "CMXCIX"
  • Repeated symbols, like "III" or "MMM"
  • The longest numeral, "MMMDCCCLXXXVIII" (3888)

Hints

Hint 1

Normally symbols are written from largest to smallest and simply added.

Hint 2

When a symbol is smaller than the one right after it, it is subtracted instead of added.

Hint 3

Scanning from right to left, you only need to remember the previous symbol's value.

FAQ

What is the best time complexity for Roman to Integer?

Optimal (right-to-left scan) runs in O(n) time and O(1) extra space. One pass over the string with an O(1) lookup per symbol.

Which pattern does Roman to Integer use?

It is a arrays & hashing problem that uses the right to left traversal pattern. Other problems with the same pattern: Array Leaders, Product of Array Except Self, Next Permutation.

Is there a brute force solution for Roman to Integer?

Yes. Brute force (match the six pairs first) takes O(n) time and O(1) space. List all thirteen tokens a numeral can be built from: the seven single symbols and the six subtractive pairs (IV, IX, XL, XC, CD, CM).

Which edge cases should I test for Roman to Integer?

A single symbol such as "I" or "M"; Several subtractive pairs in a row, like "CMXCIX"; Repeated symbols, like "III" or "MMM"; The longest numeral, "MMMDCCCLXXXVIII" (3888).