Roman Numeral Algorithms: Python, JavaScript & Java Implementation

Converting between Roman numerals and integers is a classic programming problem that appears in coding interviews, competitive programming, and real-world applications. This guide provides optimized implementations in Python, JavaScript, and Java, along with explanations of the underlying algorithms.

Understanding the Problem

We need to solve two related problems:

1. Integer to Roman: Convert an Arabic number (e.g., 1994) to Roman numerals (MCMXCIV)
2. Roman to Integer: Convert Roman numerals (e.g., MCMXCIV) to an Arabic number (1994)

Constraints

• Input range: 1 to 3999 (standard Roman numeral range)
• Use standard subtractive notation (IV, IX, XL, XC, CD, CM)
• Handle all valid Roman numeral combinations

The Greedy Algorithm Approach

Both conversions use a greedy algorithm strategy:

Integer to Roman (Greedy)

1. Create a mapping of values to Roman numerals in descending order
2. For each value-numeral pair:
   • Use as many of that numeral as possible
   • Subtract the value from the remaining number
3. Repeat until the number reaches zero

Roman to Integer (Greedy)

1. Scan the Roman numeral string from left to right
2. For each symbol:
   • If it's smaller than the next symbol, subtract it (subtractive notation)
   • Otherwise, add it
3. Return the accumulated sum

Python Implementation

Integer to Roman

def int_to_roman(num: int) -> str:
    """
    Convert an integer to Roman numerals.

    Args:
        num: Integer between 1 and 3999

    Returns:
        Roman numeral string

    Time Complexity: O(1) - fixed number of iterations (13)
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping in descending order (including subtractive combinations)
    values = [
        (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')
    ]

    result = []

    for value, numeral in values:
        # How many times does this value fit?
        count = num // value
        if count:
            result.append(numeral * count)
            num -= value * count

    return ''.join(result)


# Examples
print(int_to_roman(1994))   # MCMXCIV
print(int_to_roman(58))     # LVIII
print(int_to_roman(3999))   # MMMCMXCIX

Roman to Integer

def roman_to_int(s: str) -> int:
    """
    Convert Roman numerals to an integer.

    Args:
        s: Roman numeral string

    Returns:
        Integer value

    Time Complexity: O(n) where n is length of string
    Space Complexity: O(1) - fixed size mapping
    """
    # Mapping of Roman numerals to values
    roman_map = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }

    result = 0
    prev_value = 0

    # Scan from right to left
    for char in reversed(s):
        value = roman_map[char]

        # If current value is less than previous, subtract (subtractive notation)
        if value < prev_value:
            result -= value
        else:
            result += value

        prev_value = value

    return result


# Examples
print(roman_to_int('MCMXCIV'))  # 1994
print(roman_to_int('LVIII'))    # 58
print(roman_to_int('IX'))       # 9

Alternative: Left-to-Right Scan

def roman_to_int_v2(s: str) -> int:
    """
    Alternative implementation scanning left to right.
    """
    roman_map = {
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000
    }

    result = 0

    for i in range(len(s)):
        current = roman_map[s[i]]

        # Look ahead: if next symbol is larger, subtract current
        if i + 1 < len(s) and current < roman_map[s[i + 1]]:
            result -= current
        else:
            result += current

    return result

JavaScript Implementation

Integer to Roman

/**
 * Convert an integer to Roman numerals
 * @param {number} num - Integer between 1 and 3999
 * @returns {string} Roman numeral string
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
function intToRoman(num) {
    const values = [
        [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']
    ];

    let result = '';

    for (const [value, numeral] of values) {
        while (num >= value) {
            result += numeral;
            num -= value;
        }
    }

    return result;
}

// Examples
console.log(intToRoman(1994));  // MCMXCIV
console.log(intToRoman(58));    // LVIII
console.log(intToRoman(3999));  // MMMCMXCIX

Roman to Integer

/**
 * Convert Roman numerals to an integer
 * @param {string} s - Roman numeral string
 * @returns {number} Integer value
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
function romanToInt(s) {
    const romanMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    };

    let result = 0;

    for (let i = 0; i < s.length; i++) {
        const current = romanMap[s[i]];
        const next = romanMap[s[i + 1]];

        // If current is less than next, subtract (subtractive notation)
        if (next && current < next) {
            result -= current;
        } else {
            result += current;
        }
    }

    return result;
}

// Examples
console.log(romanToInt('MCMXCIV'));  // 1994
console.log(romanToInt('LVIII'));    // 58
console.log(romanToInt('IX'));       // 9

ES6+ Version with Reduce

/**
 * Functional approach using reduce
 */
const romanToIntFunctional = (s) => {
    const map = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };

    return s.split('').reduce((acc, char, i, arr) => {
        const current = map[char];
        const next = map[arr[i + 1]];
        return acc + (next && current < next ? -current : current);
    }, 0);
};

Java Implementation

Integer to Roman

/**
 * Convert an integer to Roman numerals
 *
 * Time Complexity: O(1)
 * Space Complexity: O(1)
 */
public class RomanConverter {

    public String intToRoman(int num) {
        // Parallel arrays for values and numerals
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] numerals = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        StringBuilder result = new StringBuilder();

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

        return result.toString();
    }

    // Examples
    public static void main(String[] args) {
        RomanConverter converter = new RomanConverter();
        System.out.println(converter.intToRoman(1994));  // MCMXCIV
        System.out.println(converter.intToRoman(58));    // LVIII
        System.out.println(converter.intToRoman(3999));  // MMMCMXCIX
    }
}

Roman to Integer

/**
 * Convert Roman numerals to an integer
 *
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
public class RomanConverter {

    public int romanToInt(String s) {
        // Create mapping
        Map<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);

        int result = 0;
        int prevValue = 0;

        // Scan from right to left
        for (int i = s.length() - 1; i >= 0; i--) {
            int currentValue = romanMap.get(s.charAt(i));

            // Subtractive notation check
            if (currentValue < prevValue) {
                result -= currentValue;
            } else {
                result += currentValue;
            }

            prevValue = currentValue;
        }

        return result;
    }

    // Examples
    public static void main(String[] args) {
        RomanConverter converter = new RomanConverter();
        System.out.println(converter.romanToInt("MCMXCIV"));  // 1994
        System.out.println(converter.romanToInt("LVIII"));    // 58
        System.out.println(converter.romanToInt("IX"));       // 9
    }
}

Algorithm Analysis

Time Complexity

Integer to Roman:

• O(1) - Constant time
• Always iterates through exactly 13 value-numeral pairs
• Independent of input size

Roman to Integer:

• O(n) - Linear time
• Where n is the length of the Roman numeral string
• Must examine each character once

Space Complexity

Both algorithms:

• O(1) - Constant space
• Fixed-size mappings regardless of input
• Result string/number size is bounded

Why the Greedy Algorithm Works

The greedy algorithm works for Roman numerals because:

1. Optimal Substructure: The optimal solution contains optimal solutions to subproblems
2. Greedy Choice Property: Locally optimal choices lead to globally optimal solution
3. No Overlapping Subproblems: Each value is used independently

The key insight: Always using the largest possible value first guarantees the shortest Roman numeral representation.

Edge Cases and Validation

Input Validation

def int_to_roman_safe(num: int) -> str:
    """Integer to Roman with validation"""
    if not isinstance(num, int):
        raise TypeError("Input must be an integer")
    if num < 1 or num > 3999:
        raise ValueError("Input must be between 1 and 3999")

    return int_to_roman(num)


def roman_to_int_safe(s: str) -> int:
    """Roman to Integer with validation"""
    if not isinstance(s, str):
        raise TypeError("Input must be a string")
    if not s:
        raise ValueError("Input cannot be empty")

    # Validate characters
    valid_chars = set('IVXLCDM')
    if not all(c in valid_chars for c in s.upper()):
        raise ValueError("Invalid Roman numeral characters")

    return roman_to_int(s.upper())

Test Cases

# Test Integer to Roman
assert int_to_roman(1) == 'I'
assert int_to_roman(4) == 'IV'
assert int_to_roman(9) == 'IX'
assert int_to_roman(58) == 'LVIII'
assert int_to_roman(1994) == 'MCMXCIV'
assert int_to_roman(3999) == 'MMMCMXCIX'

# Test Roman to Integer
assert roman_to_int('I') == 1
assert roman_to_int('IV') == 4
assert roman_to_int('IX') == 9
assert roman_to_int('LVIII') == 58
assert roman_to_int('MCMXCIV') == 1994
assert roman_to_int('MMMCMXCIX') == 3999

# Test round-trip conversion
for num in range(1, 4000):
    assert roman_to_int(int_to_roman(num)) == num

Performance Optimization

Memoization (For Repeated Conversions)

from functools import lru_cache

@lru_cache(maxsize=4000)
def int_to_roman_cached(num: int) -> str:
    """Cached version for repeated conversions"""
    return int_to_roman(num)

Batch Conversion

def batch_int_to_roman(numbers: list[int]) -> list[str]:
    """Convert multiple numbers efficiently"""
    return [int_to_roman(num) for num in numbers]


def batch_roman_to_int(numerals: list[str]) -> list[int]:
    """Convert multiple Roman numerals efficiently"""
    return [roman_to_int(s) for s in numerals]

Common Interview Questions

LeetCode Problems

1. Integer to Roman (LeetCode #12)

   • Difficulty: Medium
   • Use the greedy algorithm shown above

2. Roman to Integer (LeetCode #13)

   • Difficulty: Easy
   • Use the left-to-right or right-to-left scan

Follow-up Questions

Q: How would you handle numbers larger than 3999?

A: Implement vinculum notation (overline for ×1000):

def int_to_roman_extended(num: int) -> str:
    """Support numbers up to 3,999,999 using vinculum"""
    if num >= 4000:
        thousands = num // 1000
        remainder = num % 1000
        return f"{int_to_roman(thousands)}̅{int_to_roman(remainder)}"
    return int_to_roman(num)

Q: How would you validate a Roman numeral string?

A: Check for invalid patterns:

def is_valid_roman(s: str) -> bool:
    """Validate Roman numeral string"""
    # Convert and convert back
    try:
        num = roman_to_int(s)
        return int_to_roman(num) == s.upper()
    except:
        return False

Practical Applications

1. Document Generation

def format_chapter(num: int, title: str) -> str:
    """Format chapter heading with Roman numerals"""
    return f"Chapter {int_to_roman(num)}: {title}"

2. Copyright Years

function copyrightYear(year) {
    return `©${intToRoman(year)}`;
}

3. List Numbering

public String formatListItem(int index, String content) {
    return String.format("%s. %s", intToRoman(index), content);
}

Conclusion

Roman numeral conversion algorithms demonstrate the power of the greedy approach for problems with optimal substructure. The implementations provided here are:

• Efficient: O(1) for integer-to-Roman, O(n) for Roman-to-integer
• Readable: Clear logic that matches the mathematical rules
• Robust: Handle all valid inputs in the standard range
• Tested: Work for all numbers 1-3999

Whether you're preparing for coding interviews, building a document generator, or just curious about algorithms, these implementations provide a solid foundation.

For a user-friendly interface without writing code, try our online Roman numeral converter with instant results and support for extended notation.

---

Want to learn more? Explore our complete guide to Roman numerals or see how to use Roman numerals in Excel.