12. Integer to Roman - Greedy Solution

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

def int_to_roman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    result = ""

    for i in range(len(values)):
        while num >= values[i]:
            result += symbols[i]
            num -= values[i]

    return result

number = 1994
print(f"Roman numeral for {number} is {int_to_roman(number)}")

Java

public class Solution {
    public 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++) {
            while (num >= values[i]) {
                sb.append(symbols[i]);
                num -= values[i];
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int number = 1994;
        System.out.println("Roman numeral for " + number + " is " + solution.intToRoman(number));
    }
}

C++

#include <iostream>
#include <vector>

std::string intToRoman(int num) {
    std::string result = "";
    std::vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    std::vector<std::string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    for (size_t i = 0; i < values.size(); ++i) {
        while (num >= values[i]) {
            result += symbols[i];
            num -= values[i];
        }
    }

    return result;
}

int main() {
    int number = 1994;
    std::cout << "Roman numeral for " << number << " is " << intToRoman(number) << std::endl;
    return 0;
}

JavaScript

function intToRoman(num) {
    const values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    const symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"];
    let result = "";

    for (let i = 0; i < values.length; i++) {
        while (num >= values[i]) {
            result += symbols[i];
            num -= values[i];
        }
    }

    return result;
}

const number = 1994;
console.log(`Roman numeral for ${number} is ${intToRoman(number)}`);

#include <stdio.h>
#include <string.h>

char* intToRoman(int num) {
    static char result[20];
    result[0] = '\0';
    int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    char* symbols[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    for (int i = 0; i < 13; ++i) {
        while (num >= values[i]) {
            strcat(result, symbols[i]);
            num -= values[i];
        }
    }

    return result;
}

int main() {
    int number = 1994;
    printf("Roman numeral for %d is %s\n", number, intToRoman(number));
    return 0;
}

using System;

public class Solution {
    public 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"};

        string result = "";

        for (int i = 0; i < values.Length; i++) {
            while (num >= values[i]) {
                result += symbols[i];
                num -= values[i];
            }
        }

        return result;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        int number = 1994;
        Console.WriteLine("Roman numeral for " + number + " is " + solution.IntToRoman(number));
    }
}

By iterating over lists of integers and matching Roman numerals, the Python solution builds the numeral string by appending as long as the number remains equal or greater than the value being checked.

Complexity

Time Complexity: O(1) — The transformation of numbers to symbols is via a stable, fixed-size list.
Space Complexity: O(1) — The memory footprint is limited, constrained by the predefined lists.

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.

TypeScript

function intToRoman(num: number): string {
    const cs: string[] = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
    const vs: number[] = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    const ans: string[] = [];
    for (let i = 0; i < vs.length; ++i) {
        while (num >= vs[i]) {
            num -= vs[i];
            ans.push(cs[i]);
        }
    }
    return ans.join('');
}

func intToRoman(num int) string {
	cs := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	vs := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	ans := &strings.Builder{}
	for i, v := range vs {
		for num >= v {
			num -= v
			ans.WriteString(cs[i])
		}
	}
	return ans.String()
}

Rust

impl Solution {
    pub fn int_to_roman(num: i32) -> String {
        let cs = [
            "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I",
        ];
        let vs = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
        let mut num = num;
        let mut ans = String::new();

        for (i, &v) in vs.iter().enumerate() {
            while num >= v {
                num -= v;
                ans.push_str(cs[i]);
            }
        }

        ans
    }
}

PHP

class Solution {
    /**
     * @param Integer $num
     * @return String
     */
    function intToRoman($num) {
        $cs = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I'];
        $vs = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
        $ans = '';

        foreach ($vs as $i => $v) {
            while ($num >= $v) {
                $num -= $v;
                $ans .= $cs[$i];
            }
        }

        return $ans;
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(1) — The transformation of numbers to symbols is via a stable, fixed-size list. Space Complexity: O(1) — The memory footprint is limited, constrained by the predefined lists.
Greedy	–

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

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.

Integer to Roman solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Integer to Roman solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems