Integer to Roman

Concept

LeetCode #12.
Problem: Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. For example, 2 is written as II, 12 is written as XII. The number 27 is written as XXVII, which is XX + V + II. Given an integer, convert it to a Roman numeral.

The trick to this problem is the “Subtractive Notation” rule.
4 is not IIII. It is IV (One less than Five).
9 is not VIIII. It is IX (One less than Ten).

If we map out all the standard symbols, AND explicitly map out all 6 subtractive anomalies, we create a perfectly ordered dictionary of exact mathematical thresholds.

The Dictionary

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

The Greedy Strategy

This is fundamentally a Greedy Algorithm.
We start at the absolute highest threshold (1000 / M).
We look at our input number num.
We ask: “Is num greater than or equal to 1000?”

• If YES: We greedily attach an M to our string! We mathematically subtract 1000 from num. We ask the exact same question again (because there might be another 1000 in there!).
• If NO: num is smaller than 1000. We move to the next threshold (900).

Because our dictionary explicitly includes the subtractive anomalies (900, 400), the greedy algorithm will naturally absorb them perfectly before it ever has a chance to incorrectly print four 100s (CCCC).

Implementation

In JavaScript, standard Objects {} do NOT guarantee strict descending numerical order when iterating over their keys. To ensure our loops strictly start at 1000 and go down to 1, we must use an Array of Arrays (or a Map).

// Time Complexity: O(1) (The max roman numeral is 3999, so the loop runs a fixed max number of times)
// Space Complexity: O(1)

function intToRoman(num: number): string {
    // A strictly ordered Array of Tuples
    const thresholds = [
        [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"]
    ] as const; // 'as const' ensures TypeScript knows these are fixed tuples

    let result = "";

    // Iterate through the thresholds from largest to smallest
    for (const [val, symbol] of thresholds) {
        
        // GREEDY: While our number is big enough to absorb this threshold...
        while (num >= val) {
            
            // Attach the symbol!
            result += symbol;
            
            // Mathematically chop off the value!
            num -= val;
        }
    }

    return result;
}

Let’s trace num = 14:

1. Loop hits 10 (X). 14 >= 10.
   • result is "X". num becomes 4.
   • While loop checks 4 >= 10. False. Break.
2. Loop hits 9 (IX). 4 >= 9. False.
3. Loop hits 5 (V). 4 >= 5. False.
4. Loop hits 4 (IV). 4 >= 4. True!
   • result becomes "XIV". num becomes 0.
5. Loop finishes. Answer: "XIV".

Interview Questions

Q: Roman to Integer (LeetCode 13) is the reverse problem. Do we use the same dictionary?
A: You can, but it’s simpler. You only need the 7 base symbols (M, D, C, L, X, V, I).
You iterate the string left-to-right.
You check the current letter (I = 1) and the next letter (V = 5).
If the current letter is smaller than the next letter, it proves you hit a subtractive anomaly! You mathematically subtract the current letter’s value from the total (total -= 1). Otherwise, you just add it (total += 1).
This flawlessly parses "IV" as -1 + 5 = 4 without needing a massive dictionary!