Integer to Roman: The Greedy Mapping That Always Shows Up in Interviews
Breaking down the integer to Roman numeral conversion problem — from basic Roman numeral rules, the subtractive notation pitfalls (IV, IX, XL...), to a clean, interview-ready greedy O(1) solution. Complete with mapping table, step-by-step visualization, and why this approach is optimal given the 1-3999 constraint.
Faisal Affan
[!TIP] When you see a problem involving "conversion with priority rules," greedy almost always works — as long as symbols are sorted from largest to smallest.
Problem Statement
Given an integer num, convert it to a Roman numeral string. Roman numerals are formed from seven base symbols:
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Important rule — subtractive notation. Numbers like 4 are not written as IIII, but as IV (5 - 1). Similarly:
| Combination | Value | Logic |
|---|---|---|
| IV | 4 | 5 - 1 |
| IX | 9 | 10 - 1 |
| XL | 40 | 50 - 10 |
| XC | 90 | 100 - 10 |
| CD | 400 | 500 - 100 |
| CM | 900 | 1000 - 100 |
Constraints: 1 <= num <= 3999
Examples:
Input: num = 3749
Output: "MMMDCCXLIX"Input: num = 58
Output: "LVIII"Intuition — Greedy
Roman numerals are always built from the largest symbol that fits. This is not a coincidence — it is inherent to the Roman numeral system.
Take 58: the largest symbol ≤ 58 is L (50). Remainder 8. Largest symbol ≤ 8 is V (5). Remainder 3. Three Is. Result: "LVIII".
Take 3749: start with M (1000) three times → "MMM", remainder 749. Next D (500) → "MMMD", remainder 249. Next C (100) twice → "MMMDCC", remainder 49. Next XL (40) → "MMMDCCXL", remainder 9. Next IX (9) → "MMMDCCXLIX".
The pattern is always the same: pick the largest symbol ≤ remaining value, subtract, repeat.
The Right Mapping
We need all possible symbols — including subtractive cases — sorted from largest to smallest:
mapping := []struct {
value int
symbol string
}{
{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"},
}Thirteen symbols. Descending order. Why 13? Because we include the 6 subtractive cases as atomic symbols in the mapping. This makes the algorithm pure greedy — no special logic needed to detect 4 or 9.
Solution — Greedy O(1)
func intToRoman(num int) string {
mapping := []struct {
value int
symbol string
}{
{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"},
}
var result strings.Builder
for _, pair := range mapping {
for num >= pair.value {
result.WriteString(pair.symbol)
num -= pair.value
}
}
return result.String()
}Visualization
num = 3749
value=1000 (M): num=3749 → "M", num=2749 → "M", num=1749 → "M", num=749 → stop (749 < 1000)
result = ["M","M","M"], num = 749
value=900 (CM): 749 < 900 → skip
value=500 (D): 749 ≥ 500 → "D", num = 249
result = ["M","M","M","D"], num = 249
value=400 (CD): 249 < 400 → skip
value=100 (C): 249 ≥ 100 → "C", num = 149 → "C", num = 49 → stop (49 < 100)
result = ["M","M","M","D","C","C"], num = 49
value=90 (XC): 49 < 90 → skip
value=50 (L): 49 < 50 → skip
value=40 (XL): 49 ≥ 40 → "XL", num = 9
result = ["M","M","M","D","C","C","XL"], num = 9
value=10 (X): 9 < 10 → skip
value=9 (IX): 9 ≥ 9 → "IX", num = 0
result = ["M","M","M","D","C","C","XL","IX"], num = 0
Join → "MMMDCCXLIX"Why Greedy Works
Some problems cannot be solved with a greedy approach (e.g., coin change with certain denominations). But this problem is always greedy-optimal because:
- Roman symbols form a canonical coin system — each time we take the largest symbol that fits, we will never end up in a situation where a combination of smaller symbols could produce a shorter representation.
- The 1-3999 constraint guarantees we don't need symbols beyond
MMM(3000) or special cases beyond thousands.
Complexity
| Aspect | Value |
|---|---|
| Time | O(1) — outer loop runs 13 iterations (fixed), inner while depends on value but maxes at ~15 appends (for 3888 = MMMDCCCLXXXVIII) |
| Space | O(1) — only a result list of bounded length (max ~15 characters) |
Since num ≤ 3999, complexity is constant. For the general case (any integer), it remains O(log n) since the number of symbols per digit is bounded.
Alternate Approach — Divide by Place Value
An alternative is processing per digit (thousands/hundreds/tens/ones):
func intToRoman(num int) string {
thousands := []string{"", "M", "MM", "MMM"}
hundreds := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
tens := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
ones := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
return thousands[num/1000] +
hundreds[(num%1000)/100] +
tens[(num%100)/10] +
ones[num%10]
}Also O(1) and more explicit, but the greedy version is more flexible if the rules ever change.
Key Takeaway
Sort symbols descending. While the number is large enough for a symbol, append it and subtract. Repeat.
This problem tests whether you can recognize the greedy choice property — that picking the largest symbol that fits will never invalidate the optimal solution. Once you realize that, the implementation is trivial.