Integer to Roman LeetCode 12 Guide

LeetCode 12 Integer to Roman asks you to convert a positive integer in the range 1 to 3999 into its Roman numeral representation. Roman numerals are built from seven standard symbols: I (1), V (5), X (10), L (50), C (100), D (500), and M (1000).

In addition to the seven base symbols, Roman numerals use six subtractive forms to avoid four-character repetition: IV (4), IX (9), XL (40), XC (90), CD (400), and CM (900). These subtractive pairs are where most naïve implementations introduce brittle conditional logic that can be replaced with a cleaner table-driven approach.

The problem guarantees the input is between 1 and 3999, so you never need to handle zero, negative numbers, or numbers requiring more than three M symbols. This bounded domain is the reason the algorithm runs in O(1) time regardless of implementation style.

The key insight is to build a table of 13 entries that includes all six subtractive forms alongside the seven base symbols, sorted in descending order by value: [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]. With this table, a single greedy loop handles everything.

The algorithm iterates through the table from largest to smallest. For each entry, it repeatedly appends the symbol to the result string and subtracts the value from the number as long as the number is still greater than or equal to that value. When the number can no longer be reduced by the current entry, it moves to the next smaller entry.

This approach produces the correct Roman numeral string for any integer in 1–3999 without any if-else branches inside the loop. The 13-entry table has already encoded all the special cases as regular greedy steps.

The algorithm is straightforward once the 13-entry table is in place. Initialize an empty result string, then for each (value, symbol) pair in the table from largest to smallest, use a while loop to consume as much of the remaining number as the current value allows.

Each while-loop iteration appends the current symbol once and subtracts the current value once. This continues until the number drops below the current value, at which point the outer for loop advances to the next smaller (value, symbol) pair.

After all 13 entries have been processed, the number is guaranteed to be exactly 0 because the smallest entry is (1, I) which covers any remaining unit. Return the accumulated result string.

Roman numerals are fundamentally a greedy representation: the largest symbol that fits into the remaining value always goes first. This is why starting from M (1000) and working down to I (1) always produces the canonical Roman numeral — there is no benefit to saving a larger symbol for later.

The subtractive forms IV, IX, XL, XC, CD, and CM are treated as atomic units in the extended table. When the greedy algorithm reaches the entry (4, "IV"), it handles "4" exactly as it handles "5" with V or "10" with X — by appending the symbol and subtracting the value. No special branching is needed because the table already encodes the intended symbol for each breakpoint.

Correctness also depends on the fact that the table covers every reachable remainder. After consuming all M, CM, D, and CD entries, the remaining number is at most 99. After consuming C, XC, L, and XL, the remainder is at most 9. Each level perfectly drains to the next level's range, so the greedy never gets stuck.

Consider num=1994. The greedy starts at 1000: 1994 >= 1000, append M, num becomes 994. 994 < 1000, move to next entry.

At 900 (CM): 994 >= 900, append CM, num becomes 94. 94 < 900, advance. At 500, 400, 100: all too large, skip. At 90 (XC): 94 >= 90, append XC, num becomes 4. At 50, 40, 10, 9, 5: all too large, skip. At 4 (IV): 4 >= 4, append IV, num becomes 0.

Result = "MCMXCIV". This is the correct Roman numeral for 1994. Notice that CM (900) and XC (90) and IV (4) were each consumed in a single while-loop iteration — no special cases, just the table driving the greedy.

In Python: define the table as a list of tuples — table = [(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")]. Initialize result = "". For value, symbol in table: while num >= value: result += symbol; num -= value. Return result. The entire solution is about 10 lines.

In Java: define two parallel arrays — int[] values = {1000,900,500,400,100,90,50,40,10,9,5,4,1} and String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}. Use a StringBuilder for efficiency. For (int i=0; i<values.length; i++): while (num >= values[i]): sb.append(symbols[i]); num -= values[i]. Return sb.toString().

Time complexity is O(1) because the input is bounded by 3999, which means the total number of symbol appends across all iterations is bounded by a constant (the maximum is 3+1+3+1+3+1+3 = 15 characters for 3888 = "MMMDCCCLXXXVIII"). Space complexity is O(1) for the fixed-size table and O(1) for the bounded output.

Roman to Integer (LeetCode 13) is the direct inverse: parse a Roman numeral string back to an integer. The key rule is that if a smaller value appears before a larger value, subtract it instead of adding it. Both problems share the same value-symbol table and reward a clean table-driven approach over brittle conditional chains.

Reverse Integer (LeetCode 7) and Palindrome Number (LeetCode 9) are neighbors in the math problem family. Reverse Integer tests careful digit extraction and overflow handling. Palindrome Number extends that thinking to check symmetry without string conversion. All three problems reward clear digit-by-digit or symbol-by-symbol thinking.

The broader numeral conversion family includes problems like Excel Sheet Column Title (LeetCode 168) and Excel Sheet Column Number (LeetCode 171), which use a base-26 system with its own quirks around zero. Mastering Integer to Roman builds intuition for any positional or symbolic numeral system conversion.