12. Integer to Roman

🟧 Medium

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value I      1 V      5 X     10 L      50 C     100 D     500 M    1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.

• X can be placed before L (50) and C (100) to make 40 and 90.

• C can be placed before D (500) and M (1000) to make 400 and 900. Given an integer, convert it to a roman numeral.

Example 1

Input: num = 3 Output: "III" Explanation: 3 is represented as 3 ones.

Example 2

Input: num = 58 Output: "LVIII" Explanation: L = 50, V = 5, III = 3.

Example 3

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

Constraints

• 1 <= num <= 3999

Solution

My Solution

func intToRoman(num int) string {
    nums := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    romans := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
    
    str := strings.Builder{}
    i := 0

    for num > 0 {
        for num >= nums[i] {
            num -= nums[i]
            str.WriteString(romans[i])
        }
        i++
    }
    return str.String()
}

Optimal Solution (Greedy Approach)

func intToRoman(num int) string {
    values := []struct {
        val    int
        symbol string
    }{
        {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"},
    }
    
    var result strings.Builder
    
    for _, v := range values {
        for num >= v.val {
            result.WriteString(v.symbol)
            num -= v.val
        }
    }
    
    return result.String()
}

Approach

This solution uses a greedy approach to construct the Roman numeral:

1. Predefined Arrays:

   • nums: Contains all possible values in descending order

   • romans: Contains corresponding Roman numeral symbols

   • Includes both regular symbols (M, D, C...) and subtractive combinations (CM, CD...)

2. String Construction:

   • Uses strings.Builder for efficient string concatenation

   • Processes the number from largest to smallest value

   • Repeatedly subtracts the largest possible value

3. Key Insights:

   • Values are arranged in descending order

   • Special cases (like 4, 9, 40, 90, etc.) are handled as single units

   • Greedy choice always leads to optimal solution

Complexity Analysis

Time Complexity: O(1)

• The input is constrained to [1, 3999]

• Maximum number of iterations is bounded

• Each value can be used at most 3 times (except M)

• strings.Builder operations are O(1)

Space Complexity: O(1)

• Fixed-size arrays for values and symbols:

  • nums array: 13 integers

  • romans array: 13 strings

• Output string size is bounded

• No recursive calls or dynamic space

Why it works

• Greedy Approach is Valid:

  • Roman numerals follow a largest-to-smallest rule

  • Each step reduces the number by the largest possible value

  • No backtracking needed

• Special Cases Handled:

  • Subtractive combinations (IV, IX, XL, etc.) are treated as single units

  • Prevents invalid combinations like IIII for 4

• Complete Coverage:

  • Every integer in range can be uniquely represented

  • All possible combinations are included in the arrays

result

Leetcode: link