Loading…

mediumStringsLC #12Sometimes asked

Integer to Roman

Q: How do you solve Integer to Roman using the Digit-by-Digit Lookup Table approach?

When to use it: Offer as an alternative when asked for another angle, or to show you can decompose by decimal place. Roman numerals are positional in a loose sense: the thousands place, hundreds place, tens place, and ones place each translate independently. `1994` = thousands digit `1` → 'M', hundreds digit `9` → 'CM', tens digit `9` → 'XC', ones digit `4` → 'IV', giving 'MCMXCIV'. This approach precomputes, for each place, the ten possible Roman strings for digits 0–9. **Why this works.** Because num ≤ 3999, there are only four places and the thousands digit is at most 3. Each place's mapping is fixed and small, so we can hard-code it. For example, the ones table is `["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]` — index `4` is exactly 'IV', so the subtractive forms are baked into the table rather than computed. **Trade-off versus the greedy loop.** This version arguably executes fewer operations (no inner `while`), and some find it clearer because each decimal place is explicit. The cost is four ten-element tables to write out and get right, and it is rigidly tied to the four-place structure (it would need rework if the range grew). The greedy table version is more compact, more general, and the one most interviewers expect to see, so prefer it as your primary answer and keep this as a 'here's another way' aside. **Why it's still canonical.** Just like the greedy version, every subtractive form lives inside the precomputed strings, so there is no risk of emitting 'IIII' — the lookup at index 4 already returns 'IV'. Time complexity: O(1). Space complexity: O(1).

LCPractice

Arrays & Hashing · 19 of 83 · 9 min

Roman numerals are represented by seven symbols: I, V, X, L, C, D and M, with values 1, 5, 10, 50, 100, 500, 1000.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII but IV — the smaller I placed before the larger V and subtracted. The same subtractive principle applies in six cases: IV (4), IX (9), XL (40), XC (90), CD (400), and CM (900).

Given an integer, convert it to a Roman numeral.

In plain English

We always emit symbols from the largest value that fits down to the smallest. The only wrinkle is the six subtractive pairs; if we treat each pair as just another 'denomination' worth 900/400/90/40/9/4, the conversion becomes a plain greedy loop with no special cases.

Examples

Example 1

Input: num = 3
Output: "III"
Note: 3 is three 1's. The greedy loop peels I three times.

Example 2

Input: num = 58
Output: "LVIII"
Note: 50 = L, 5 = V, then 3 = III. So L + V + III = LVIII.

Example 3

Input: num = 1994
Output: "MCMXCIV"
Note: 1000 = M, 900 = CM, 90 = XC, 4 = IV. Each subtractive pair is a single table row.

Constraints

1 ≤ num ≤ 3999

Clarifying questions4First question: What's the range of the input?Explore questions

Q1.What's the range of the input?
1 to 3999. That guarantees we never need a symbol larger than M and never need four of a base symbol, so the standard table fully covers it.
Q2.Can the input be zero or negative?
No — Roman numerals have no representation for zero or negatives, and the constraints exclude them.
Q3.Do you want the canonical (minimal) Roman form?
Yes. 4 must be IV, not IIII. Including the subtractive pairs in the table produces the canonical form automatically.
Q4.Is greedy actually safe here?
Yes — for this specific denomination set, always taking the largest symbol that fits is provably optimal, unlike arbitrary coin systems.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Build a descending table of value→symbol that INCLUDES the six subtractive pairs (900=CM, 400=CD, 90=XC, 40=XL, 9=IX, 4=IV). Walk the table from largest to smallest; while the current value fits in the remaining number, append its symbol and subtract. This greedy peel-off is O(1) — at most 13 symbol kinds, ≤ 3 of each.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize Roman numerals as a greedy 'make change' problem and whether you handle the subtractive forms (4, 9, 40, 90, 400, 900) cleanly instead of with a tangle of special cases.

Where candidates slip

Hard-coding only the 'pure' symbols (I, V, X, L, C, D, M) and then trying to patch 4 and 9 with conditionals — producing IIII instead of IV, or an explosion of edge-case branches.

How to stand out

State up front: 'Roman numerals are greedy if I include the subtractive pairs in my denomination table.' Then write a single clean loop. Mention the digit-by-digit table variant as an alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Greedy Descending Table (Optimal)Optimal	`O(1)`	`O(1)`	Lead with this. Frame it as 'make change with Roman denominations, including the subtractive pairs as denominations'.	Read
2	Digit-by-Digit Lookup Table	`O(1)`	`O(1)`	Offer as an alternative when asked for another angle, or to show you can decompose by decimal place.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewnum, result = ''num >= value?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Greedy Descending Table (Optimal)

TimeO(1)SpaceO(1)

Lead with this. Frame it as 'make change with Roman denominations, including the subtractive pairs as denominations'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Roman numerals are written largest symbol first. What greedy rule does that suggest — and what classic problem (making change with coins) does it resemble?

2Hint 2Explore hint

The annoying cases are 4, 9, 40, 90, 400, 900. What if you stopped treating them as exceptions and instead listed them as their own 'denominations' worth 4, 9, 40, ... in your value table?

3Hint 3Explore hint

Build two parallel arrays: values [1000, 900, 500, 400, ...] and symbols ["M", "CM", "D", "CD", ...]. For each value top-down, while num >= value, append the symbol and subtract.

A · Core idea

The key reframing is to stop thinking of Roman numerals as a system with awkward exceptions and start thinking of it as a greedy 'make change' problem. In make-change, you repeatedly take the largest coin that doesn't overshoot the remaining amount. Roman numerals work identically: write the largest-valued symbol whose value doesn't exceed what's left, subtract it, repeat.

Why we fold the subtractive pairs into the table. The naive instinct is to list only the seven 'real' symbols (I=1, V=5, X=10, L=50, C=100, D=500, M=1000) and then bolt on special handling for 4 (IV), 9 (IX), 40 (XL), and so on. That path leads to a thicket of if statements. The elegant move is to notice that CM is just a token worth 900, IV is just a token worth 4. So we extend the denomination list with these six compound tokens and place each one immediately above the base symbol it borrows from. Now 900 is a denomination exactly like 1000 or 500, and the greedy loop handles it with zero special cases.

Why the table must be strictly descending and why greedy is correct here. Greedy 'largest coin first' is not universally optimal for arbitrary coin sets — for coins {1, 3, 4} making 6, greedy gives 4+1+1 (three coins) while 3+3 (two coins) is better. Roman denominations are special: each value is structured so that you can never represent it more economically by skipping the largest fitting symbol. Because the table is sorted descending and includes the subtractive pairs, the first symbol that fits is always part of the canonical answer, so peeling it off greedily is safe.

Why `while` instead of `if` on each denomination. A number like 3000 needs three M's, and 300 needs three C's. After appending one symbol we must check the same denomination again, because the remaining number may still be ≥ that value. A while loop peels as many copies as fit (never more than three, since four of a base symbol would have been written as a subtractive pair). We subtract the value on every append so the remaining num always reflects exactly what is still left to encode — forget the subtraction and the loop never terminates.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

num = 1994

Interactive diagram

Why subtractive pairs belong in the table

value=1000 (M)

Active call / nodeSupporting contextReturned stateNot active

Each compound token sits directly above the base symbol it borrows from, so greedy never produces IIII.

Final result"MCMXCIV"

C · Code with teaching comments

solution.javaJava

Greedy Descending Table (Optimal) — optimal

4 teaching notes

1
public String intToRoman(int num) {
2
    // Descending denominations — note the subtractive pairs 900/400/90/40/9/4 sit
3
    // between the base symbols.
4
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
5
    // Symbols aligned by index with values — symbols[i] is worth values[i].
6
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
7
    StringBuilder sb = new StringBuilder();
8
    for (int i = 0; i < values.length; i++) {
9
        // while, not if — 3000 needs three M's, so peel the same denomination
10
        // repeatedly.
11
        while (num >= values[i]) {
12
            sb.append(symbols[i]);
13
            // Subtract on every append so num always reflects what's left to encode.
14
            num -= values[i];
15
        }
16
    }
17
    return sb.toString();
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

Encoding the six subtractive exceptions as ordinary denominations is the entire intellectual content of the problem. It converts 'a special rule for 4s and 9s' into 'one more row in the table', which is the difference between a 10-line clean solution and a 40-line branchy one.

ComplexityO(1) time, O(1) space — The table has a fixed 13 entries and the output is at most ~15 characters (e.g. 3888 = MMMDCCCLXXXVIII). Both bounds are constants independent of the input magnitude, so time and extra space (beyond the output string) are O(1).

E · Edge cases and pitfalls7num = 1 — Only the last denomination (1, I) fits once → "I".Explore edge cases

Edge cases handled

num = 1Only the last denomination (1, I) fits once → "I".
num = 4Skips 5 (V doesn't fit alone correctly here), hits the 4=IV row → "IV", never "IIII".
num = 3999Largest input: MMM + CM + XC + IX → "MMMCMXCIX". Tests three repeats plus three subtractive pairs.

Pitfalls

Listing only the seven base symbols and trying to patch 4/9 with if-statements — produces IIII or a branch explosion.
Using if instead of while — fails on 3000 (only emits one M).
Forgetting to subtract values[i] — infinite loop.
Putting the table in ascending order — greedy then takes the smallest symbol first and breaks.

03.2

Approach 2 of 2

Digit-by-Digit Lookup Table

TimeO(1)SpaceO(1)

Offer as an alternative when asked for another angle, or to show you can decompose by decimal place.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A Roman numeral is really four independent pieces: thousands, hundreds, tens, ones. Each decimal digit maps to a fixed short string.

2Hint 2Explore hint

Precompute four tables of ten strings each: ones[0..9], tens[0..9], hundreds[0..9], thousands[0..3]. Index by the corresponding digit.

3Hint 3Explore hint

Concatenate thousands[num/1000] + hundreds[num/100 % 10] + tens[num/10 % 10] + ones[num % 10].

A · Core idea

Roman numerals are positional in a loose sense: the thousands place, hundreds place, tens place, and ones place each translate independently. 1994 = thousands digit 1 → 'M', hundreds digit 9 → 'CM', tens digit 9 → 'XC', ones digit 4 → 'IV', giving 'MCMXCIV'. This approach precomputes, for each place, the ten possible Roman strings for digits 0–9.

Why this works. Because num ≤ 3999, there are only four places and the thousands digit is at most 3. Each place's mapping is fixed and small, so we can hard-code it. For example, the ones table is ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"] — index 4 is exactly 'IV', so the subtractive forms are baked into the table rather than computed.

Trade-off versus the greedy loop. This version arguably executes fewer operations (no inner while), and some find it clearer because each decimal place is explicit. The cost is four ten-element tables to write out and get right, and it is rigidly tied to the four-place structure (it would need rework if the range grew). The greedy table version is more compact, more general, and the one most interviewers expect to see, so prefer it as your primary answer and keep this as a 'here's another way' aside.

Why it's still canonical. Just like the greedy version, every subtractive form lives inside the precomputed strings, so there is no risk of emitting 'IIII' — the lookup at index 4 already returns 'IV'.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

num = 1994

thousands

1994 / 1000 = 1 → thousands[1]

State"M"

Final result"MCMXCIV"

C · Code with teaching comments

Reference implementation previewpublic String intToRoman(int num) { String[] thousands = {"", "M", "MM", "MMM"}; String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}; String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}; String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};Explore the full code

solution.javaJava

Digit-by-Digit Lookup Table — reference

3 teaching notes

1
public String intToRoman(int num) {
2
    String[] thousands = {"", "M", "MM", "MMM"};
3
    String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
4
    String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
5
    // Index 4 is 'IV' and index 9 is 'IX' — subtractive forms baked directly into the
6
    // table.
7
    String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
8
    // Thousands digit, 0–3 since num ≤ 3999; integer division extracts it.
9
    return thousands[num / 1000]
10
         // Drop the lower two digits then mod 10 to isolate the hundreds digit.
11
         + hundreds[(num / 100) % 10]
12
         + tens[(num / 10) % 10]
13
         + ones[num % 10];
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

Decomposing by decimal place turns the problem into four parallel constant-time lookups. It's the same 'bake the exceptions into the data' philosophy as the greedy table, just sliced by digit position instead of by denomination.

ComplexityO(1) time, O(1) space — Four constant-size lookups and one concatenation. No loops over the magnitude of num, so O(1) time and O(1) extra space.

E · Edge cases and pitfalls5num = 9 — thousands/hundreds/tens index 0 → ""; ones[9] = "IX". Result "IX".Explore edge cases

Edge cases handled

num = 9thousands/hundreds/tens index 0 → ""; ones[9] = "IX". Result "IX".
num = 3888thousands[3]=MMM, hundreds[8]=DCCC, tens[8]=LXXX, ones[8]=VIII → longest output "MMMDCCCLXXXVIII".

Pitfalls

Off-by-one in digit extraction — forgetting the % 10 after dividing leaves higher digits in.
Sizing the thousands table only up to index 3 but indexing with a larger value if the input range were violated.
Mistyping one of the 40 table strings — easy to get hundreds[4]=CD vs CDC wrong.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic 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++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Special-casing 4 and 9 instead of tabling them

Without rows for 4/9/40/90/400/900, greedy on base symbols emits IIII for 4. Bolting on if-checks for every place value is fragile and long.

Explore the code comparison

Don't write this

int[] values = {1000, 500, 100, 50, 10, 5, 1};
String[] symbols = {"M", "D", "C", "L", "X", "V", "I"};
// 4 now becomes "IIII", 9 becomes "VIIII" — wrong

Write this instead

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"};
// 4 -> IV, 9 -> IX, handled by the table

Using if instead of while

A single if appends one symbol and moves on, so 3000 produces only 'M' instead of 'MMM'. You must peel the same denomination until it no longer fits.

Explore the code comparison

Don't write this

for value, symbol in zip(values, symbols):
    if num >= value:
        result.append(symbol)
        num -= value

Write this instead

for value, symbol in zip(values, symbols):
    while num >= value:
        result.append(symbol)
        num -= value

Forgetting to subtract after appending

If you append the symbol but never reduce num, the while condition stays true forever and the program hangs.

Explore the code comparison

Don't write this

while num >= value:
    result.append(symbol)
    # num never changes -> infinite loop

Write this instead

while num >= value:
    result.append(symbol)
    num -= value

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy descending value/symbol table

Code pattern to memorize

vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
for v, s in zip(vals, syms):
    while num >= v: append s; num -= v

Rules to remember

1Include the subtractive pairs as first-class table entries (900, 400, 90, 40, 9, 4). This is the whole trick — it turns 'special cases' into ordinary greedy steps.
2Iterate the table strictly largest → smallest. Greedy only stays correct because each Roman value is large enough that you can never do better by skipping it.
3Use `while`, not `if`, on each value. 3000 needs MMM — three M's — so you must peel the same symbol repeatedly.
4Subtract as you append so the remaining number always reflects what's left to encode. Forgetting the subtraction loops forever.
5Numbers are 1–3999, so you never need a symbol above M and never need four of any base symbol — the table guarantees valid Roman output.

Use this pattern when

Converting a number into a positional symbol system with a fixed, finite set of denominations
The denominations are 'coin-like' — greedy from largest always wins (Roman, certain currency systems)
You can pre-list every legal token (including compound ones) in a constant-size table
Output length is bounded by a constant, so the loop is effectively O(1)

Choose another pattern when

Parsing Roman → integer instead (that's the reverse problem, Roman to Integer, LC 13)
A coin system where greedy is NOT optimal (e.g. coins [1, 3, 4] making 6) → needs DP, not this table
Arbitrary-precision or numbers outside 1–3999 → the fixed table no longer covers the input
Symbols can repeat unboundedly with no subtractive rule → it's just base conversion

Interview takeaway

The elegant move is encoding the six subtractive exceptions (CM, CD, XC, XL, IX, IV) directly into the value table. Once they're ordinary rows, the algorithm collapses to a textbook greedy 'make change' loop — no if-ladders, no special handling for 4s and 9s.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternGreedy 'make change' over a fixed descending denomination table, with the subtractive exceptions folded in as ordinary denominations. The same 'bake the special cases into the data' trick appears in Roman to Integer and Integer to English Words.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Roman to Integer
The reverse direction — scan left to right, subtract when a smaller symbol precedes a larger one.
Integer to English Words
Coming soon
Same 'chunk by place value and map via tables' idea, but grouped in threes for thousand/million/billion.
Make Change (Greedy vs DP)
Coming soon
Shows where greedy 'largest first' fails — motivates why Roman's fixed denominations make greedy safe here.

Same pattern

←

Find the Index of the First Occurrence in a String

Continue · Next problem

Is Subsequence

mediumStringsLC #12Sometimes asked

Integer to Roman

LCPractice

Arrays & Hashing · 19 of 83 · 9 min

Roman numerals are represented by seven symbols: I, V, X, L, C, D and M, with values 1, 5, 10, 50, 100, 500, 1000.

Given an integer, convert it to a Roman numeral.

In plain English

Examples

Example 1

Input: num = 3
Output: "III"
Note: 3 is three 1's. The greedy loop peels I three times.

Example 2

Input: num = 58
Output: "LVIII"
Note: 50 = L, 5 = V, then 3 = III. So L + V + III = LVIII.

Example 3

Input: num = 1994
Output: "MCMXCIV"
Note: 1000 = M, 900 = CM, 90 = XC, 4 = IV. Each subtractive pair is a single table row.

Constraints

1 ≤ num ≤ 3999

Clarifying questions4First question: What's the range of the input?Explore questions

Q1.What's the range of the input?
1 to 3999. That guarantees we never need a symbol larger than M and never need four of a base symbol, so the standard table fully covers it.
Q2.Can the input be zero or negative?
No — Roman numerals have no representation for zero or negatives, and the constraints exclude them.
Q3.Do you want the canonical (minimal) Roman form?
Yes. 4 must be IV, not IIII. Including the subtractive pairs in the table produces the canonical form automatically.
Q4.Is greedy actually safe here?
Yes — for this specific denomination set, always taking the largest symbol that fits is provably optimal, unlike arbitrary coin systems.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize Roman numerals as a greedy 'make change' problem and whether you handle the subtractive forms (4, 9, 40, 90, 400, 900) cleanly instead of with a tangle of special cases.

Where candidates slip

Hard-coding only the 'pure' symbols (I, V, X, L, C, D, M) and then trying to patch 4 and 9 with conditionals — producing IIII instead of IV, or an explosion of edge-case branches.

How to stand out

State up front: 'Roman numerals are greedy if I include the subtractive pairs in my denomination table.' Then write a single clean loop. Mention the digit-by-digit table variant as an alternative.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Greedy Descending Table (Optimal)Optimal	`O(1)`	`O(1)`	Lead with this. Frame it as 'make change with Roman denominations, including the subtractive pairs as denominations'.	Read
2	Digit-by-Digit Lookup Table	`O(1)`	`O(1)`	Offer as an alternative when asked for another angle, or to show you can decompose by decimal place.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Greedy Descending Table (Optimal)

TimeO(1)SpaceO(1)

Lead with this. Frame it as 'make change with Roman denominations, including the subtractive pairs as denominations'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Roman numerals are written largest symbol first. What greedy rule does that suggest — and what classic problem (making change with coins) does it resemble?

2Hint 2Explore hint

The annoying cases are 4, 9, 40, 90, 400, 900. What if you stopped treating them as exceptions and instead listed them as their own 'denominations' worth 4, 9, 40, ... in your value table?

3Hint 3Explore hint

Build two parallel arrays: values [1000, 900, 500, 400, ...] and symbols ["M", "CM", "D", "CD", ...]. For each value top-down, while num >= value, append the symbol and subtract.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

num = 1994

Interactive diagram

Why subtractive pairs belong in the table

value=1000 (M)

Active call / nodeSupporting contextReturned stateNot active

Each compound token sits directly above the base symbol it borrows from, so greedy never produces IIII.

Final result"MCMXCIV"

C · Code with teaching comments

solution.javaJava

Greedy Descending Table (Optimal) — optimal

4 teaching notes

1
public String intToRoman(int num) {
2
    // Descending denominations — note the subtractive pairs 900/400/90/40/9/4 sit
3
    // between the base symbols.
4
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
5
    // Symbols aligned by index with values — symbols[i] is worth values[i].
6
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
7
    StringBuilder sb = new StringBuilder();
8
    for (int i = 0; i < values.length; i++) {
9
        // while, not if — 3000 needs three M's, so peel the same denomination
10
        // repeatedly.
11
        while (num >= values[i]) {
12
            sb.append(symbols[i]);
13
            // Subtract on every append so num always reflects what's left to encode.
14
            num -= values[i];
15
        }
16
    }
17
    return sb.toString();
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7num = 1 — Only the last denomination (1, I) fits once → "I".Explore edge cases

Edge cases handled

num = 1Only the last denomination (1, I) fits once → "I".
num = 4Skips 5 (V doesn't fit alone correctly here), hits the 4=IV row → "IV", never "IIII".
num = 3999Largest input: MMM + CM + XC + IX → "MMMCMXCIX". Tests three repeats plus three subtractive pairs.

Pitfalls

Listing only the seven base symbols and trying to patch 4/9 with if-statements — produces IIII or a branch explosion.
Using if instead of while — fails on 3000 (only emits one M).
Forgetting to subtract values[i] — infinite loop.
Putting the table in ascending order — greedy then takes the smallest symbol first and breaks.

03.2

Approach 2 of 2

Digit-by-Digit Lookup Table

TimeO(1)SpaceO(1)

Offer as an alternative when asked for another angle, or to show you can decompose by decimal place.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A Roman numeral is really four independent pieces: thousands, hundreds, tens, ones. Each decimal digit maps to a fixed short string.

2Hint 2Explore hint

Precompute four tables of ten strings each: ones[0..9], tens[0..9], hundreds[0..9], thousands[0..3]. Index by the corresponding digit.

3Hint 3Explore hint

Concatenate thousands[num/1000] + hundreds[num/100 % 10] + tens[num/10 % 10] + ones[num % 10].

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

num = 1994

thousands

1994 / 1000 = 1 → thousands[1]

State"M"

Final result"MCMXCIV"

C · Code with teaching comments

solution.javaJava

Digit-by-Digit Lookup Table — reference

3 teaching notes

1
public String intToRoman(int num) {
2
    String[] thousands = {"", "M", "MM", "MMM"};
3
    String[] hundreds = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
4
    String[] tens = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
5
    // Index 4 is 'IV' and index 9 is 'IX' — subtractive forms baked directly into the
6
    // table.
7
    String[] ones = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
8
    // Thousands digit, 0–3 since num ≤ 3999; integer division extracts it.
9
    return thousands[num / 1000]
10
         // Drop the lower two digits then mod 10 to isolate the hundreds digit.
11
         + hundreds[(num / 100) % 10]
12
         + tens[(num / 10) % 10]
13
         + ones[num % 10];
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(1) time, O(1) space — Four constant-size lookups and one concatenation. No loops over the magnitude of num, so O(1) time and O(1) extra space.

E · Edge cases and pitfalls5num = 9 — thousands/hundreds/tens index 0 → ""; ones[9] = "IX". Result "IX".Explore edge cases

Edge cases handled

num = 9thousands/hundreds/tens index 0 → ""; ones[9] = "IX". Result "IX".
num = 3888thousands[3]=MMM, hundreds[8]=DCCC, tens[8]=LXXX, ones[8]=VIII → longest output "MMMDCCCLXXXVIII".

Pitfalls

Off-by-one in digit extraction — forgetting the % 10 after dividing leaves higher digits in.
Sizing the thousands table only up to index 3 but indexing with a larger value if the input range were violated.
Mistyping one of the 40 table strings — easy to get hundreds[4]=CD vs CDC wrong.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Special-casing 4 and 9 instead of tabling them

Without rows for 4/9/40/90/400/900, greedy on base symbols emits IIII for 4. Bolting on if-checks for every place value is fragile and long.

Explore the code comparison

Don't write this

int[] values = {1000, 500, 100, 50, 10, 5, 1};
String[] symbols = {"M", "D", "C", "L", "X", "V", "I"};
// 4 now becomes "IIII", 9 becomes "VIIII" — wrong

Write this instead

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"};
// 4 -> IV, 9 -> IX, handled by the table

Using if instead of while

A single if appends one symbol and moves on, so 3000 produces only 'M' instead of 'MMM'. You must peel the same denomination until it no longer fits.

Explore the code comparison

Don't write this

for value, symbol in zip(values, symbols):
    if num >= value:
        result.append(symbol)
        num -= value

Write this instead

for value, symbol in zip(values, symbols):
    while num >= value:
        result.append(symbol)
        num -= value

Forgetting to subtract after appending

If you append the symbol but never reduce num, the while condition stays true forever and the program hangs.

Explore the code comparison

Don't write this

while num >= value:
    result.append(symbol)
    # num never changes -> infinite loop

Write this instead

while num >= value:
    result.append(symbol)
    num -= value

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Greedy descending value/symbol table

Code pattern to memorize

vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
for v, s in zip(vals, syms):
    while num >= v: append s; num -= v

Rules to remember

1Include the subtractive pairs as first-class table entries (900, 400, 90, 40, 9, 4). This is the whole trick — it turns 'special cases' into ordinary greedy steps.
2Iterate the table strictly largest → smallest. Greedy only stays correct because each Roman value is large enough that you can never do better by skipping it.
3Use `while`, not `if`, on each value. 3000 needs MMM — three M's — so you must peel the same symbol repeatedly.
4Subtract as you append so the remaining number always reflects what's left to encode. Forgetting the subtraction loops forever.
5Numbers are 1–3999, so you never need a symbol above M and never need four of any base symbol — the table guarantees valid Roman output.

Use this pattern when

Converting a number into a positional symbol system with a fixed, finite set of denominations
The denominations are 'coin-like' — greedy from largest always wins (Roman, certain currency systems)
You can pre-list every legal token (including compound ones) in a constant-size table
Output length is bounded by a constant, so the loop is effectively O(1)

Choose another pattern when

Parsing Roman → integer instead (that's the reverse problem, Roman to Integer, LC 13)
A coin system where greedy is NOT optimal (e.g. coins [1, 3, 4] making 6) → needs DP, not this table
Arbitrary-precision or numbers outside 1–3999 → the fixed table no longer covers the input
Symbols can repeat unboundedly with no subtractive rule → it's just base conversion

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Roman to Integer
The reverse direction — scan left to right, subtract when a smaller symbol precedes a larger one.
Integer to English Words
Coming soon
Same 'chunk by place value and map via tables' idea, but grouped in threes for thousand/million/billion.
Make Change (Greedy vs DP)
Coming soon
Shows where greedy 'largest first' fails — motivates why Roman's fixed denominations make greedy safe here.

Same pattern

←

Find the Index of the First Occurrence in a String

Continue · Next problem

Is Subsequence