LeetCode Solutions Blog

Integer to Roman

Number: 12

Difficulty: Medium

Paid? No

Problem Description

Given an integer between 1 and 3999, convert it to its corresponding Roman numeral representation following the traditional rules of Roman numeral notation.

Key Insights

Use a greedy strategy by iterating through predefined numeral mappings ordered from highest to lowest.
Include subtractive notation pairs (e.g., IV, IX, XL, XC, CD, CM) in the mapping to handle cases where a numeral should not be repeated more than three times.
Append the symbol while subtracting its value from the input integer until the number becomes zero.
The solution operates in constant time since the value range is fixed and the mapping list is constant.

Space and Time Complexity

Time Complexity: O(1) – The algorithm processes a fixed number of numeral mappings regardless of the input. Space Complexity: O(1) – Uses a small, constant extra space for the mapping and result string.

Solution

The approach uses a greedy algorithm where we maintain a list of tuples containing numeral values and their corresponding symbols arranged in descending order. For the given integer, we iterate through this list, repeatedly subtracting the numeral value from the integer and appending the corresponding symbol to the result string. This efficiently converts the integer to its Roman numeral form while correctly handling both standard and subtractive cases.

Code Solutions

# Define a function to convert integer to Roman numeral
def intToRoman(num):
    # List of tuples mapping integer values to their Roman numeral symbols in descending order,
    # including subtractive pairs.
    value_symbols = [
        (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 the result Roman numeral string.
    result = ""
    
    # Iterate over the numeral mapping.
    for value, symbol in value_symbols:
        # While the current number is at least the current value,
        # subtract the value and append the corresponding symbol.
        while num >= value:
            result += symbol  # Append symbol
            num -= value      # Reduce the number
    return result

# Example usage
print(intToRoman(1994))  # Expected output: MCMXCIV