LeetCode Problem #12: Integer to Roman - Explanation and Solutions in Python and JavaScript

Introduction

The Integer to Roman problem is a classic problem that tests your understanding of number manipulation and string building. It is frequently asked in coding interviews to assess your problem-solving skills. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

Given an integer num, convert it to a Roman numeral.

Example:

Input: num = 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.
    

Approach

The problem can be solved efficiently using a **greedy algorithm**. Here's the step-by-step approach:

1. Create two lists: one for Roman numerals and one for their corresponding integer values, ordered from largest to smallest.
2. Iterate through the lists, subtracting the largest possible value from num and appending the corresponding Roman numeral to the result.
3. Repeat the process until num is reduced to 0.

Solution in Python

def intToRoman(num):
    val = [
        1000, 900, 500, 400,
        100, 90, 50, 40,
        10, 9, 5, 4,
        1
    ]
    syms = [
        "M", "CM", "D", "CD",
        "C", "XC", "L", "XL",
        "X", "IX", "V", "IV",
        "I"
    ]
    roman_num = ""
    i = 0
    while num > 0:
        for _ in range(num // val[i]):
            roman_num += syms[i]
            num -= val[i]
        i += 1
    return roman_num
        

Explanation: We use a greedy algorithm to subtract the largest possible value from num and append the corresponding Roman numeral to the result. We repeat this process until num is reduced to 0.

Solution in JavaScript

function intToRoman(num) {
    const val = [
        1000, 900, 500, 400,
        100, 90, 50, 40,
        10, 9, 5, 4,
        1
    ];
    const syms = [
        "M", "CM", "D", "CD",
        "C", "XC", "L", "XL",
        "X", "IX", "V", "IV",
        "I"
    ];
    let romanNum = "";
    let i = 0;
    while (num > 0) {
        for (let j = 0; j < Math.floor(num / val[i]); j++) {
            romanNum += syms[i];
            num -= val[i];
        }
        i++;
    }
    return romanNum;
}
        

Explanation: Similar to the Python solution, we use a greedy algorithm to subtract the largest possible value from num and append the corresponding Roman numeral to the result. We repeat this process until num is reduced to 0.

Time and Space Complexity

Time Complexity: O(1) - The number of iterations is constant because the maximum value of num is 3999.
Space Complexity: O(1) - The space used is constant as we only store the Roman numerals and their values.

Edge Cases

• num = 1 (smallest input).
• num = 3999 (largest input).
• num with multiple repeated digits (e.g., 333).

Conclusion

The Integer to Roman problem is a great way to practice number manipulation and string building. By understanding this approach, you can solve similar problems like Roman to Integer or other numeral system conversions. Try solving it on your own and explore related problems on LeetCode!