Integer to Roman

Medium Arrays & Hashing Greedy Original on LeetCode

Integer to Roman is a medium arrays & hashing problem solved with the greedy pattern. The best approach, optimal (one lookup per decimal digit), runs in O(1) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (greedy over 13 symbols) up.

Problem

Roman numerals use seven symbols: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. A number is normally written from the largest symbol to the smallest and the values are added, so 27 is XXVII.

Six values use a subtractive form instead, where a smaller symbol placed before a larger one is subtracted: 4 = IV, 9 = IX, 40 = XL, 90 = XC, 400 = CD, 900 = CM. No other subtractive pairs exist, and I, X, C, M may appear at most three times in a row.

Given an integer num, return its Roman numeral as a string.

Examples

Example 1

Input
num = 2024
Output
"MMXXIV"
Why
2000 = MM, 20 = XX, 4 = IV.

Example 2

Input
num = 49
Output
"XLIX"
Why
40 = XL and 9 = IX. Writing IL for 49 is not allowed.

Example 3

Input
num = 3888
Output
"MMMDCCCLXXXVIII"
Why
Every place uses the longest additive form: MMM, DCCC, LXXX, VIII.

Constraints

  • 1 <= num <= 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 15 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 (greedy over 13 symbols)O(1)O(1)
Optimal (one lookup per decimal digit)O(1)O(1)

1Brute force (greedy over 13 symbols)

TimeO(1)num is at most 3999, so at most 15 symbols are appended over 13 table entries.
SpaceO(1)Two fixed tables; the output has at most 15 characters.

List the 13 values that have their own spelling, from 1000 (M) down to 1 (I), including the subtractive pairs like 900 (CM) and 4 (IV). Walk the list and, while the current value fits into what is left of num, append its symbol and subtract it.

  1. values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] with matching symbols.
  2. For each index i: while num >= values[i], append symbols[i] and num -= values[i].
  3. Return the built string.
class Solution {
    public String intToRoman(int num) {
        int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
        String[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                sb.append(symbols[i]);
                num -= values[i];
            }
        }
        return sb.toString();
    }
}

2Optimal (one lookup per decimal digit)

TimeO(1)Exactly four table lookups and one concatenation.
SpaceO(1)The four fixed tables hold 33 short strings.

Each decimal place is spelled independently, and each digit 0–9 has one fixed spelling for its place. Precompute four small tables (thousands, hundreds, tens, ones) and concatenate the entries picked by the four digits of num. No loops over symbols at all.

  1. thousands = ["", "M", "MM", "MMM"].
  2. hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]; tens and ones follow the same shape with X/L/C and I/V/X.
  3. Return thousands[num / 1000] + hundreds[num / 100 % 10] + tens[num / 10 % 10] + ones[num % 10].
class Solution {
    private static final String[] THOUSANDS = { "", "M", "MM", "MMM" };
    private static final String[] HUNDREDS = { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" };
    private static final String[] TENS = { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" };
    private static final String[] ONES = { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" };

    public String intToRoman(int num) {
        return THOUSANDS[num / 1000] + HUNDREDS[num / 100 % 10] + TENS[num / 10 % 10] + ONES[num % 10];
    }
}

Edge cases to test

  • The six subtractive forms: 4, 9, 40, 90, 400, 900
  • Zeros in the middle, like 1009 = MIX
  • The smallest value 1 and the largest value 3999 = MMMCMXCIX
  • Repeated symbols, like 3 = III and 300 = CCC

Hints

Hint 1

Treat the six subtractive pairs (CM, CD, XC, XL, IX, IV) as extra symbols with their own values.

Hint 2

With those 13 symbols sorted from largest to smallest, always take the largest one that still fits.

Hint 3

Alternatively, each decimal digit maps to a fixed string for its place: thousands, hundreds, tens, ones.

FAQ

What is the best time complexity for Integer to Roman?

Optimal (one lookup per decimal digit) runs in O(1) time and O(1) extra space. Exactly four table lookups and one concatenation.

Which pattern does Integer to Roman use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Jump Game II, Jump Game, Can Place Flowers.

Is there a brute force solution for Integer to Roman?

Yes. Brute force (greedy over 13 symbols) takes O(1) time and O(1) space. List the 13 values that have their own spelling, from 1000 (M) down to 1 (I), including the subtractive pairs like 900 (CM) and 4 (IV).

Which edge cases should I test for Integer to Roman?

The six subtractive forms: 4, 9, 40, 90, 400, 900; Zeros in the middle, like 1009 = MIX; The smallest value 1 and the largest value 3999 = MMMCMXCIX; Repeated symbols, like 3 = III and 300 = CCC.