Integer to Roman - Leetcode 12 - Python
Integer to Roman - Video Solution
Watch 10 video solutions for Integer to Roman, a medium level problem involving Hash Table, Math, String. This walkthrough by NeetCode has 115,510 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Seven different symbols represent Roman numerals with the following values:
| Symbol | Value |
|---|---|
| I | 1 |
| V | 5 |
| X | 10 |
| L | 50 |
| C | 100 |
| D | 500 |
| M | 1000 |
Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:
- If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
- If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (
I) less than 5 (V):IVand 9 is 1 (I) less than 10 (X):IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM). - Only powers of 10 (
I,X,C,M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
Given an integer, convert it to a Roman numeral.
Example 1:
Input: num = 3749
Output: "MMMDCCXLIX"
Explanation:
3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M) 700 = DCC as 500 (D) + 100 (C) + 100 (C) 40 = XL as 10 (X) less of 50 (L) 9 = IX as 1 (I) less of 10 (X) Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places
Example 2:
Input: num = 58
Output: "LVIII"
Explanation:
50 = L 8 = VIII
Example 3:
Input: num = 1994
Output: "MCMXCIV"
Explanation:
1000 = M 900 = CM 90 = XC 4 = IV
Constraints:
1 <= num <= 3999
Approach Overview
Problem Overview: Convert a given integer into its Roman numeral representation. Roman numerals use specific symbols such as I, V, X, L, C, D, and M, combined using additive and subtractive rules (for example, IV for 4 and IX for 9).
Approach 1: Repeated Subtraction with Symbol Mapping (O(n) time, O(1) space)
Start with two parallel arrays: one holding Roman numeral values and another holding their corresponding symbols. Iterate from the largest value (1000 → M) down to the smallest (1 → I). For each value, repeatedly subtract it from the input number while appending the associated symbol to the result string. This approach directly mirrors how Roman numerals are constructed. The loop performs multiple subtractions for each symbol, so the time complexity depends on how many characters end up in the output, typically treated as O(n) relative to the result length.
Approach 2: Greedy Value Selection (O(1) time, O(1) space)
The optimal solution uses a greedy strategy. Maintain an ordered list of value-symbol pairs including subtractive cases such as 900 (CM), 400 (CD), 90 (XC), 40 (XL), 9 (IX), and 4 (IV). Iterate through this list from largest to smallest. At each step, compute how many times the value fits into the current number, append the symbol that many times, and reduce the number using modulus. The key insight is that Roman numerals always prefer the largest valid symbol first, which makes greedy selection correct.
Because the Roman numeral system only supports values up to 3999, the number of iterations is bounded by a small constant. That makes both time and space effectively O(1). The algorithm mostly performs integer division, modulus operations, and string concatenation.
The implementation is straightforward and portable across languages such as Python, Java, C++, C#, C, and JavaScript. The logic relies on simple iteration and string building rather than complex data structures, though the mapping of values to symbols can be stored in an array or a small hash table. The reasoning behind subtractive notation comes from the structure of Roman numerals, which fits naturally into greedy algorithms often discussed in math and string manipulation problems.
Recommended for interviews: Interviewers expect the greedy value-symbol mapping solution. It demonstrates that you understand Roman numeral rules and can encode them efficiently. Starting with a simple repeated subtraction idea shows reasoning, but the greedy list with subtractive pairs is the clean, production-ready solution most candidates are evaluated on.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Repeated Subtraction with Mapping | O(n) | O(1) | Good for understanding how Roman numerals are constructed step by step |
| Greedy Value-Symbol Matching | O(1) | O(1) | Preferred interview solution using ordered value-symbol pairs including subtractive cases |