LeetCode 12 – Integer to Roman | Love Me Some Coding

Integer to Roman looks like it needs a pile of special cases — four is IV, nine is IX, forty is XL, and so on through six irregular pairs. It does not. Put those six pairs into the symbol table as if they were symbols in their own right, and the whole problem collapses into a plain greedy loop.

The problem

Convert an integer between 1 and 3999 to a Roman numeral. Seven symbols:

I = 1     V = 5     X = 10    L = 50
C = 100   D = 500   M = 1000

3    -> "III"
4    -> "IV"        not "IIII"
58   -> "LVIII"     50 + 5 + 1 + 1 + 1
1994 -> "MCMXCIV"   1000 + 900 + 90 + 4

Numerals are written largest to smallest, left to right — except in six places where a smaller symbol sits before a larger one and is subtracted from it:

IV = 4     IX = 9
XL = 40    XC = 90
CD = 400   CM = 900

The idea: make the exceptions part of the table

The instinct is to write the greedy loop over the seven real symbols and then bolt on if branches for the six subtractive cases. That is the version that ends up four times longer than it needs to be and gets MCMXCIV wrong.

Instead, notice that CM behaves in every respect like a symbol worth 900. It is two characters instead of one, but nothing in the algorithm cares about that. So build a table of thirteen entries, sorted descending, with the six pairs interleaved among the seven singles:

1000  900  500  400  100   90   50   40   10    9    5    4    1
  M   CM     D   CD     C   XC    L   XL     X   IX    V   IV    I

Now the algorithm is one sentence: walk the table from largest to smallest, and while the number is at least the current value, subtract it and append the symbol. No special cases at all.

Greedy is provably correct here because the six pairs plug exactly the gaps where plain greedy over the seven singles would have gone wrong. Without CM in the table, 900 would emit DCCCC; with it, the largest fitting entry is CM and the remainder is zero. Every value from 1 to 3999 has exactly one representation reachable this way.

Java

class Solution {
    // Descending, with the six subtractive pairs treated as ordinary symbols.
    private static final int[] VALUES =
        { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    private static final String[] SYMBOLS =
        { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < VALUES.length && num > 0; i++) {
            while (num >= VALUES[i]) {
                num -= VALUES[i];
                sb.append(SYMBOLS[i]);
            }
        }

        return sb.toString();
    }
}

Two parallel arrays rather than a LinkedHashMap: the table is fixed, tiny and ordered, and the index is the only thing tying the halves together. Keep them static final so the table is built once, not on every call.

Python

class Solution:
    VALUES = [
        (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"),
        (100, "C"), (90, "XC"), (50, "L"), (40, "XL"),
        (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I"),
    ]

    def intToRoman(self, num: int) -> str:
        out = []

        for value, symbol in self.VALUES:
            if num == 0:
                break
            count, num = divmod(num, value)     # how many of this symbol fit
            out.append(symbol * count)

        return "".join(out)

divmod replaces the inner while outright: it answers "how many fit" and "what is left" in one step, and symbol * count emits them all at once. The M row is the one that benefits — 3000 becomes "MMM" without three loop iterations.

Complexity

O(1) time and space. The table has thirteen fixed entries and the input is capped at 3999, so the output is at most fifteen characters — MMMDCCCLXXXVIII, which is 3888. Nothing here scales with an input size, and saying so is better than reciting O(n).

Building strings, and the thing not to do

Use StringBuilder, not String +=. Java strings are immutable, so result += symbol allocates a fresh string and copies the whole prefix every time, turning a linear loop into a quadratic one. It does not matter at fifteen characters, and it matters enormously in the version of this problem where the bound is not 3999 — which is exactly why an interviewer watches for it.

The Python equivalent is appending to a list and calling "".join() once, for the same reason.

What the interviewer is checking

That you fold the six subtractive pairs into the table instead of special-casing them. This is the entire problem.
That the table is descending, and that you understand why greedy is safe once it is.
1994 — it exercises CM, XC and IV in one input, and it is the case a special-cased solution fails.
That you accumulate into a StringBuilder rather than concatenating.
That you can do the inverse, Roman to Integer, which is usually the follow-up and needs a different insight entirely.