Skip to main content
Talentd

Integer to Roman - Solution & Explanation

MediumHash TableMathString15 min readAsked at: Amazon, Microsoft, Goldman Sachs +28
Practice this problem

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): IV and 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.

Approach 1: Greedy Approach

This approach utilizes a greedy strategy by iterating over an ordered list of numeral values and corresponding symbols. Starting from the largest value, it repeatedly subtracts from the given number until the result is less, appending the equivalent symbol each time. This ensures the numeral is created with the fewest characters.

The C implementation defines an array of integer values and corresponding Roman symbols. A loop iterates through these values, subtracting the largest possible from the input number, and appends the associated Roman symbol to the result string.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) — The solution has a fixed iteration through a constant list of length 13, hence it's O(1).
Space Complexity: O(1) — Uses constant space for the result string and numeral arrays.

Try this approach in the editor →

Approach 2: Greedy

We can first list all possible symbols cs and their corresponding values vs, then enumerate each value vs[i] from large to small. Each time, we use as many symbols cs[i] corresponding to this value as possible, until the number num becomes 0.

The time complexity is O(m), and the space complexity is O(m). Here, m is the number of symbols.

Code

PythonJavaC++GoTypeScriptRustC#PHPC

Python

Java

C++

Go

TypeScript

Rust

C#

PHP

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(1) — The solution has a fixed iteration through a constant list of length 13, hence it's O(1).
Space Complexity: O(1) — Uses constant space for the result string and numeral arrays.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Repeated Subtraction with MappingO(n)O(1)Good for understanding how Roman numerals are constructed step by step
Greedy Value-Symbol MatchingO(1)O(1)Preferred interview solution using ordered value-symbol pairs including subtractive cases

Video Solution

Integer to Roman - Leetcode 12 - Python • NeetCode • 115,510 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Integer to Roman easy or hard?
The problem is typically classified as Medium difficulty. The implementation is short, but candidates must remember subtractive numeral rules such as IV, IX, XL, XC, CD, and CM and apply a greedy strategy to generate the correct sequence.
Integer to Roman Python/Java solution
In Python or Java, define arrays or lists containing Roman numeral values and their symbols. Iterate through the values from largest to smallest, append symbols while subtracting from the number, and build the result string. The same greedy logic works across C++, JavaScript, C#, and other languages.
How to solve Integer to Roman in O(1)?
Store ordered value-symbol pairs such as (1000, M), (900, CM), (500, D), and so on. Iterate through the list, determine how many times each value fits into the number using division, append the symbol that many times, and reduce the number with modulus. Since the list size is constant, the algorithm runs in O(1).
What is the best approach for Integer to Roman?
The greedy value-symbol mapping approach is the best solution. Maintain a list of Roman numeral values including subtractive pairs like 900 (CM), 400 (CD), 90 (XC), and 4 (IV). Iterate from the largest value to the smallest, append the corresponding symbol, and subtract the value from the number. This produces the correct Roman numeral in constant time.
Is Integer to Roman asked at Google/Amazon/Meta?
Integer to Roman appears frequently in coding interviews and practice sets used by companies like Amazon, Google, and Meta. It tests understanding of greedy algorithms, number decomposition, and string construction rather than complex data structures.
What data structure is used in Integer to Roman?
Most implementations use a small array or list of value-symbol pairs to represent Roman numeral mappings. Some variants use a hash table or dictionary for quick lookups, but a simple ordered array works best for the greedy iteration.
What is the time complexity of Integer to Roman?
The optimal greedy solution runs in O(1) time and O(1) space because the Roman numeral system has a fixed set of symbols and the input range is bounded (typically 1 to 3999). The algorithm iterates through a constant list of value-symbol pairs.

Ready to solve this problem?

Practice Integer to Roman with our built-in code editor and test cases.

Practice on FleetCode
Previous

Integer to English Words

Next

Roman to Integer