NUHMAN.com

Introduction

LeetCode 13: Roman to Integer is the reverse of the previous challenge (Integer to Roman). Here, you’re given a valid Roman numeral string, and your job is to convert it into an integer.

The key here is to handle subtractive combinations like IV (4), IX (9), XL (40), etc., where a smaller value comes before a larger one.

In this article, we’ll walk through a simple and effective greedy approach using a map in Go.

Problem Statement

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

All input strings are valid Roman numerals (no need to validate).

Roman Numeral Table

SymbolValueM1000D500C100L50X10V5I1

Subtractive Combinations

• IV = 4
• IX = 9
• XL = 40
• XC = 90
• CD = 400
• CM = 900

Examples

go

Input: "III"
Output: 3
go

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

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

Approach: Right-to-Left Traversal with Subtractive Rule

We go right to left, and at each character:

• If the current value is less than the previous value, subtract it (e.g., I before V = 4).
• Otherwise, add it normally.

Why it works:

Subtractive combinations always appear in decreasing order (e.g., I before V, X before L), so this reverse traversal simplifies the logic.

Go Implementation

go

package main

import (
    "fmt"
)

func romanToInt(s string) int {
    romanMap := map[byte]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    total := 0
    prev := 0

    for i := len(s) - 1; i >= 0; i-- {
        curr := romanMap[s[i]]
        if curr < prev {
            total -= curr
        } else {
            total += curr
        }
        prev = curr
    }

    return total
}

func main() {
    testCases := []string{
        "III", "IV", "IX", "LVIII", "MCMXCIV", "MMXXIV",
    }

    for _, roman := range testCases {
        fmt.Printf("Input: %s -> Integer: %d\n", roman, romanToInt(roman))
    }
}

Step-by-Step Example: MCMXCIV

Reverse traverse:

CharValuePrevActionTotalV50+55I15-14C1001+100104X10100-1094M100010+10001094C1001000-100994M1000100+10001994

Time and Space Complexity

• Time Complexity: O(n), where n is the length of the Roman numeral string.
• Space Complexity: O(1), constant space for the map.

Key Takeaways

• Use a hash map for symbol-to-value mapping.
• Reverse traversal simplifies the subtractive case logic.
• Clean and efficient logic in just a few lines of Go code.