NUHMAN.com

Introduction

LeetCode 12: Integer to Roman is a classic formatting and string manipulation problem. It tests your ability to break down numbers and build strings using the Roman numeral system.

In this article, we’ll explore a greedy approach to solve this problem efficiently and implement it cleanly in Go (Golang).

Problem Statement

Given an integer, convert it to a Roman numeral.

You must use standard Roman numeral symbols and follow conventional rules (no subtractive errors, correct combinations, etc.).

Roman Numeral Table

SymbolValueM1000CM900D500CD400C100XC90L50XL40X10IX9V5IV4I1

Examples

go

Input: num = 3
Output: "III"
go

Input: num = 58
Output: "LVIII" // L = 50, V = 5, III = 3
go

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

Approach: Greedy Algorithm

We use a greedy strategy — start from the largest Roman value and subtract as much as possible, appending the corresponding symbol each time.

Steps:

1. Create slices for Roman values and their corresponding symbols.
2. Iterate through the values from highest to lowest.
3. For each value:

• Subtract from num as many times as possible.
• Append the corresponding symbol each time.

Go Implementation

go

package main

import (
    "fmt"
)

func intToRoman(num int) string {
    values := []int{
        1000, 900, 500, 400,
        100, 90, 50, 40,
        10, 9, 5, 4, 1,
    }

    symbols := []string{
        "M", "CM", "D", "CD",
        "C", "XC", "L", "XL",
        "X", "IX", "V", "IV", "I",
    }

    result := ""

    for i := 0; i < len(values); i++ {
        for num >= values[i] {
            num -= values[i]
            result += symbols[i]
        }
    }

    return result
}

func main() {
    testCases := []int{3, 4, 9, 58, 1994, 2024}
    for _, num := range testCases {
        fmt.Printf("Input: %d -> Roman: %s\n", num, intToRoman(num))
    }
}

Example Walkthrough: 1994

• Start with num = 1994
• M = 1000 → subtract → result = "M", num = 994
• CM = 900 → subtract → result = "MCM", num = 94
• XC = 90 → subtract → result = "MCMXC", num = 4
• IV = 4 → subtract → result = "MCMXCIV", num = 0

Time and Space Complexity

• Time Complexity: O(1)
• There are only 13 symbols and a max input of 3999.
• Space Complexity: O(1)
• Constant space for symbol arrays and output string (up to 15 chars max).

Key Takeaways

• Greedy algorithms work well when there's a clear, ordered breakdown of values.
• Roman numerals require special subtractive symbols (like IV, CM) — always include them in your mappings.
• Efficient and readable solutions are more important than complex logic here.