Integer to Roman - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Integer to Roman" Problem in Go

Difficulty: Medium | Tags: Hash Table, Math, String

Introduction

Converting integers to Roman numerals is a classic problem that tests understanding of numeral systems and efficient mapping techniques. The challenge lies in handling subtractive combinations and ensuring correct symbol placement.

Problem Analysis

Roman numerals follow specific rules where symbols are combined or subtracted to represent values. The key challenge is handling edge cases like 4 (IV), 9 (IX), and similar subtractive forms. The problem requires converting integers (1-3999) to their Roman numeral equivalents.

Solution Approach

We use a greedy algorithm with predefined value-symbol pairs. By iterating from the largest to smallest values, we repeatedly subtract the largest possible Roman numeral value and append the corresponding symbol to the result. This ensures optimal symbol selection and handles subtractive cases naturally.

Go Implementation


func intToRoman(num int) string {
    symbols := []struct {
        value  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 _, pair := range symbols {
        for num >= pair.value {
            result.WriteString(pair.symbol)
            num -= pair.value
        }
    }
    return result.String()
}

Complexity Analysis

Time Complexity: O(1) - The loop runs a fixed number of times (13 iterations) regardless of input size, as Roman numerals have a limited set of symbols.

Space Complexity: O(1) - The space used is constant for the symbol-value pairs and the result string builder.

Testing and Examples

Test cases validate correctness:

  • Input: 3749 → Output: "MMMDCCXLIX"
  • Input: 58 → Output: "LVIII"
  • Input: 1994 → Output: "MCMXCIV"
  • Edge Case: 1 → Output: "I"
  • Edge Case: 3999 → Output: "MMMCMXCIX"

Best Practices and Tips

Key takeaways:

  • Predefine symbol-value pairs in descending order for efficient greedy selection.
  • Use a string builder for efficient concatenation.
  • Ensure all subtractive cases (4, 9, etc.) are included in the predefined pairs.
  • Test edge cases, especially minimum (1) and maximum (3999) values.

Read more